The aim of the following question is to prove that the language {M | M is the…
PYQ GATE 2002
The aim of the following question is to prove that the language {M | M is the code of a Turing Machine which, irrespective of the input, halts and outputs a 1}, is undecidable. This is to be done by reducing form 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 propery 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 that M must make? (c) What key property relates the behaviour of M on w to the behaviour of M ′ on x?
Sign up free to check your answer
Sign up freeLoading lesson…

