Problem 1: Show that the following problems are undecidable by showing how if yo
ID: 3688047 • Letter: P
Question
Problem 1: Show that the following problems are undecidable by showing how if you could solve this problem, then you could solve the halting problem (although you may end up with a proof that is like the proof of Rice's Theorem, you should not simply invoke Rice's theorem).
A. Given a TM M and a state q, is there any input w that causes M to enter state q?
B. Given two Turing Machines, do they compute the same output on all inputs (i.e., for each input, they both do not halt, or they both halt and produce the same output).
Explanation / Answer
A. Given a TM M and a state q, is there any input w that causes M to enter state q?
ANS:
• There is a Turing machine M such that Halt(M ) € w { enter state q
• There is a Turing machine M' such that HaltM) ¢ w' { not enter in state q
This is paradoxical! So w cannot exist. Therefore w' cannot exist either.
HaltIn(w) :={ (M) | Halt(M) € w } is undecidable.
---------------------------------------------------------------------------------------------------------------------------------
B. Given two Turing Machines, do they compute the same output on all inputs (i.e., for each input, they both do not halt, or they both halt and produce the same output).
ANS:
Let M be an arbitrary Turing machine. Let M be a Turing machine that on set of input x , simulates M (on some predefined input) for |x| steps and accepts if (and only if) M halts within |x| steps (or, if you want to go with a TM computing a function, returns 1 if M halts within |x| steps and 0 otherwise).
If M doesn't halt then M accepts the empty input (or, computes the function f(x)=0 ). If M does halt then the input M accepts is non-empty (or, the function is non-constant).
So ATM is not decidable.