Register

GATE CSE 2002 | Question: 14

• edited by
5,288 views
29 29 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$?

1 Answer

Best answer
19 19 votes
  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
Voting & Accepting an answer helps improve the community
← Previous · GATE CSE 2002 | Ques...Next → · GATE CSE 2002 | Ques...
← Previous in category · GATE CSE 2002 | Ques...Next in category → · GATE CSE 2002 | Ques...
Position:
Show:

Related questions

18 18 votes
2 answers 2 answers
3.6k
3.6k views
gatecse asked Aug 20, 2014
3,605 views
L(M) = Σ*
$L= \{\langle M \rangle\mid L(M) = \Sigma^*\} $A. $L$ is RE but $L'$ is not REB. Both $L$ and $L'$ are REC. $L$ is not RE but $L'$ is RED. Both $L$ and $L'$ are not RE
18 18 votes
4 answers 4 answers
9.9k
9.9k views
gatecse asked Aug 20, 2014
9,879 views
L(M) is infinite
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$$L$ is RE but $L'$ is not REBoth $L$ and $L'$ are RE$L$ is not RE but $L'$ is REBoth $L$ and $L'$ are not RE
38 38 votes
3 answers 3 answers
8.2k
8.2k views
Kathleen asked Sep 15, 2014
8,214 views
GATE CSE 2002 | Question: 21
We require a four state automaton to recognize the regular expression $(a\mid b)^*abb$Give an NFA for this purposeGive a DFA for this purpose
12 12 votes
4 4 answers
6.7k
6.7k views
go_editor asked Feb 28, 2018
6,719 views
GATE CSE 2002 | Question: 18-b
The functionality of atomic TEST-AND-SET assembly language instruction is given by the following C functionint TEST-AND-SET (int *x) { int y; A1: y=*x; A2: *x=1; A3: retu...