2
$\begingroup$

Suppose we have Turing machine $M^*$ that:

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

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

Show that you cannot construct $M^*$.

Suppose we run $M^*$ on itself so that:

i. $M^*$ halts printing 1 if $M^*$ halts on input 1

ii. $M^*$ halts printing 0 if $M^*$ doesn't halt on input 1

ii. is a contradiction, so it's impossible to construct $M^*$.

I'm not sure if this "proof" works or how I can proceed to show that $M^*$ is impossible. I know there is a way to show that it leads to making the halting problem decidable, but I don't know how to show that.

$\endgroup$
2
$\begingroup$

In your point, $i$ is not a contradiction. $ii$ is not either, because $M^*$ halts always, so it just print $1$ on itself. You have to use something stronger. (We note $M(x)\uparrow$ to say $M$ on input $x$ does not halt, and $\downarrow$ for halt)

So we suppose we have (a recursive) $M^*$ such that $$M^*(n)=\left\{\begin{array}cM_n(1)\downarrow \;\Rightarrow 1\\M_n(1)\uparrow\; \Rightarrow 0\\\end{array}\right.$$

From $M^*$, you can build (by composition) the program $P$ such that $$P(n,x)=\left\{\begin{array}cM^*(n)=1 \;\Rightarrow \;\uparrow\\M^*(n)=0\; \Rightarrow 0\\\end{array}\right.$$

By Kleene/Roger fixed point theorem, there is a $p$ such that $M_p(x)$ computes $P(p,x)$.

  1. If $P(p,1)\uparrow$, then $M^*(p)=1$, then $M_p(1)\downarrow$ but $P(p,1)=M_p(1)$ !
  2. If $P(p,1)=0$, then $M^*(p)=0$, then $M_p(1)\uparrow$, another contradiction.

Hence $P$ does not exist, nor $M^*$.

$\endgroup$

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.