+13 votes
625 views

The aim of the following question is to prove that the language {M | M is the code of the Turing Machine which, irrespective of the input, halts and outputs a 1}, is undecidable. This is to be done by reducing from the language {M', x | M' halts on x}, which is known to be undecidable. In parts (a) and (b) describe the 2 main steps in the construction of M. In part (c) describe the key property which relates the behaviour of M on its input w to the behaviour of M' on x.

1. On input w, what is the first step that M must make?
2. On input w, based on the outcome of the first step, what is the second step M must make?
3. What key property relates the behaviour of M on w to the behaviour of M' on x?
asked | 625 views

## 1 Answer

+4 votes
Best answer
(a) M erases its input w and simulate the moves of M' on x. Thus if M' halts on x, M accepts any input ($\Sigma^*$) and if M' doesn't halt on x, M accepts no string ($\phi$)

(b) Give the description of M - <M> to the TM that decides L. If TM accepts <M>, M halts on all inputs -> M' accept x. If TM rejects <M>, M doesn't halt on some input -> M' doesn't halt on x, due to our construction of M in 1st step. Thus we decide halting problem

(c) M halting on all inputs w is the key property relating to M' which is halting on a given input x
answered by Veteran (346k points)
selected by
@Arjun
Regarding the GATE, Is this okay,  if i am unable to understand such Turing Machine problems?
I tried hard i don't think i can solve any such new problems like this. though i can solve few decidable and undecidable problems based on the properties of TM or L(TM) but not all specially like this problem

This kind of question is rare in GATE nowadays as standard of questions are less. So, it is safe to avoid those problems which require a reduction. But you need to know how to apply Rice's theorem because it is easy and could be applied in most decidability problems.

is it not possible concatenate x after every string?
why need to erase M every time?

+4 votes
2 answers
1
+5 votes
3 answers
2
+17 votes
1 answer
3