The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+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 in Theory of Computation by Veteran (69k points) | 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?


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

33,687 questions
40,230 answers
114,268 comments
38,795 users