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 at 22:24
  • $\begingroup$ @Nathaniel I would say this is a variation of the halting problem. $\endgroup$
    – John L.
    Jul 7 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 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 at 22:54
  • 1
    $\begingroup$ That's a good interpretation, I think you are right! $\endgroup$
    – Nathaniel
    Jul 7 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$
4
  • $\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 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 at 4:11
  • $\begingroup$ Thanks for the response! Could you check if I'm missing anything in this question? $\endgroup$ Jul 6 at 12:04
  • $\begingroup$ @FredJefferson I am checking that question... $\endgroup$
    – John L.
    Jul 6 at 15:22

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.