The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
676 views

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$?
asked in Theory of Computation by Veteran (59.4k points)
edited by | 676 views

1 Answer

+4 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$
answered by Veteran (342k points)
edited by
0
@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
+2

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.

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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,499 questions
42,765 answers
121,498 comments
42,150 users