1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ This is the classic halting problem (see the link for a sketch of the proof). $\endgroup$
    – Nathaniel
    Jul 5, 2022 at 22:24
  • $\begingroup$ @Nathaniel I would say this is a variation of the halting problem. $\endgroup$
    – John L.
    Jul 7, 2022 at 21:25
  • $\begingroup$ @Nathaniel Assume the access to such a universal Turing machine as an oracle, can you construct an oracle Turing machine that solves the halting problem? If you can, that would be an evidence that this is the halting problem. $\endgroup$
    – John L.
    Jul 7, 2022 at 22:12
  • 2
    $\begingroup$ @Nathaniel As I understand, there is no restriction on that UTM when $M$ does not halt on $w$. In this sense, the allowable behavior of that UTM is completely defined. $\endgroup$
    – John L.
    Jul 7, 2022 at 22:54
  • 1
    $\begingroup$ That's a good interpretation, I think you are right! $\endgroup$
    – Nathaniel
    Jul 7, 2022 at 23:04

1 Answer 1

0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Exercise: Prove that there does not exist a Turing machine that takes $\langle M\rangle$ as input, where $M$ is a Turing machine, and that always halts, returns $1$ if $M$ on empty input returns $1$, and returns $2$ if $M$ on empty input returns $2$. $\endgroup$
    – John L.
    Jul 6, 2022 at 3:34
  • $\begingroup$ Another way to prove is to decide the halting problem assuming the existence of such a universal Turing machine. It is similar to the proof for Rice's theorem $\endgroup$
    – John L.
    Jul 6, 2022 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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