a halting turing machine

Question

Prove that there does not exist a universal Turing machine that takes a pair $\langle M, w\rangle$ as input, where M is a Turing machine and w is a string, and that always halts, accepts if $M$ accepts $w$, and rejects if $M$ reject w.

I think assuming the existence of such a machine H could allow one to decide the halting problem. Assume the existence of such a machine. Suppose $\langle M, w\rangle$ is given as input. Then let $M'$ be the machine resulting from swapping the accept and reject states of $M$. If $H$ accepts $\langle M,w\rangle$ and $\langle M', w\rangle$ or if $H$ rejects both inputs, then either $M$ accepts w in the first case or $M$ rejects w in the second case. However, it's possible that $H$ accepts $\langle M,w\rangle$ and rejects $\langle M', w\rangle$ or vice versa, in which case $M$ can either accept or reject w. I'm not sure how to deal with this issue.

Answer 1

Proof of concept referenced by Nathaniel tells that the idea for a contradiction resulting from assuming a decider $\text{halts}$ that decides the halting problem is to construct a Turing machine $g$ that "does the opposite of what $\text{halts}$ says $g$ should do, so $\text{halts}(g)$ can not return a truth value that is consistent with whether $g$ halts.

We can adapt that idea to the current situation.

For the sake of contradiction, assume there exists such a universal Turing machine $U$.

Construct Turing machine $F$, which on input $w$, checks if $w=\langle M\rangle$ for some Turing machine $M$.

• If not, $F$ accepts. (In fact, it is OK for $F$ to accept or loop here. It does not matter what is $F$'s behavior here.)
• Otherwise, simulates $U$ on $\langle M, \langle M\rangle\rangle$.
  • If the simulated $U$ accepts, $F$ rejects.
  • Otherwise, the simulated $U$ must reject since $U$ always halts. $F$ Accepts.

Now let us run $F$ on input $\langle F\rangle$. So, $F$ will simulate $U$ on $\langle F, \langle F\rangle\rangle$. There are two cases.

1. The simulated $U$ will accept and $F$ will reject.
2. The simulated $U$ will reject and $F$ will accept.

Let us check case 1, where $F$ will end up with rejecting $\langle F\rangle$. By the specification of $U$, the simulated $U$ should also reject, which means we are not in case 1.

Let us check case 2, where $F$ will end up with accepting $\langle F\rangle$. By the specification of $U$, the simulated $U$ should also accept, which means we are not in case 2.

Since neither case can happen, there must be no such Turing machine $F$. That means there is no such Turing machine $U$.