Proof that such a Turing machine cannot be constructed...

261 Views Asked by At

Prove there can be no Turing machine $M^*$ that takes input $n$ and:

i. halts printing 1 if $M_n$ halts on input 1

ii. halts printing 0 if $M_n$ doesn't halt on input 1

Intuitively I can see why such a machine can't be constructed, because in case ii. if the $M_n$ doesn't halt on input 1, we cannot determine whether it will ever halt or loop forever. However, I struggle with the construction of a formal/rigorous proof. I know problems of this nature generally work along the lines of: assume a machine can be constructed and show how it leads to a solution to the halting problem.

Any help is appreciated.

1

There are 1 best solutions below

7
On BEST ANSWER

If such a machine existed, where would it be on the list?