GATE CSE 2002 | Question: 14

Question

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$.

• A. On input $w$, what is the first step that $M$ must make?
• B. On input $w$, based on the outcome of the first step, what is the second step $M$ must make?
• C. What key property relates the behaviour of $M$ on $w$ to the behaviour of $M'$ on $x$?

Comments

https://www.youtube.com/watch?v=FGyAr_MRbV0

This will help

---

Rice Theorem nptel

https://www.youtube.com/watch?v=NhJ0QZxrz9I

Answer 1

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$

Comments

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

Anubhav

---

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

---

Blackcode00

yes.