Show that the Turing machine will solve the self-halting problem

Question

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.

Answer 1

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^*$.