1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What do you mean "the list?" $\endgroup$ – user1038665 Feb 26 '14 at 20:05
  • 1
    $\begingroup$ @user1038665: I think Cheyne is asking what would be the value of M* applied to Mn=M*. $\endgroup$ – Michael Feb 26 '14 at 20:07
  • $\begingroup$ So we would have (for i.) $M^*$ halt printing 1 if $M^*$ halts on input 1, which I guess is self-looping, right? $\endgroup$ – user1038665 Feb 26 '14 at 20:10
  • 1
    $\begingroup$ This hint is a bit oversimplified. $M^*$ halts on input $1$ iff $M_1$ halts on input $1$. This does not lead to a contradiction. $\endgroup$ – Erick Wong Feb 26 '14 at 20:29
  • $\begingroup$ So where do we arrive at a contradiction? $\endgroup$ – user1038665 Feb 26 '14 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.