in Theory of Computation edited by
20 votes

The aim of the following question is to prove that the language $\{M \mid M$ $\text {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 \mid M'$ $\text{ 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$?
in Theory of Computation edited by

1 comment

This will help


1 Answer

11 votes
Best answer
  1. $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$)
  2. Give the description of $M$ - <$M$> to the TM that decides $L$. If TM accepts <$M$>, $M$ halts on all inputs $\rightarrow M'$ accept $x$. If TM rejects <$M$>, $M$ doesn't halt on some input $\rightarrow M'$ doesn't halt on $x$, due to our construction of $M$ in $1$st step. Thus we decide halting problem
  3. $M$ halting on all inputs $w$ is the key property relating to $M'$ which is halting on a given input $x$
edited by


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?
Hi Arjun,

Can you explain the part "b" of the question again and what does the symbol <M> means and  what is 'L' here?

Thank You

@Arjun sir , It is Kind of Reduction from Language L(Which we want to proof as Undecidable) to Halting problem ??

Related questions