7
$\begingroup$

The book Computational Complexity: A Modern Approach by Arora/Barak provides the following:

Theorem 1.10 There exists a function $UC: \{0,1\}^* \to \{0,1\}$ that is not computable by any TM.

Theorem 1.11 HALT(The halting problem) is not computable by any TM.

Table 1.7 that shows how Theorem 1.10 can be proved using diagonalization. Essentially this table says that there exists an uncomputable function UC that can always reverse the output of any TM, therefore, function UC is uncomputable.

The proof of Theorem 1.11 essentially creates a TM $M_{UC}$ that computes UC by assuming that HALT is computable and also by using a universal TM to simulate $M_{UC}$ and thus contradicts Theorem 1.10 and concludes that HALT is uncomputable.

My question is this: Since $M_{UC}$ is a TM, it already exists as a part of Table 1.7. In this case (as explained by the note attached to this table), function UC will (by definition) reverse the output of $M_{UC}$. Thus the $M_{UC}$ does not compute function UC even if we assume that HALT is computable.

Also, it seems that $M_{UC}$ will go into a type of recursion when the input to $M_{UC}$ is a bit representation of $M_{UC}$, i.e., each simulation on a universal TM will lead to another call on the universal TM and thus lead to a type of loop. Perhaps this is the reason the proof of Theorem 1.11 invokes a call to the HALT function (which is assumed to be computable).

Improve this question
$\endgroup$
1
  • $\begingroup$ It is important to note that the statement here in Theorem 1.10 is actually too weak. What is established is a specific function $UC$ that later is used in Theorem 1.11 as you explain. Theorem 1.10 can be proved without giving any function at all: there are only countably many Turing machines and uncountably many such functions. $\endgroup$
    – Hendrik Jan
    Jun 19, 2014 at 9:33

1 Answer 1

Reset to default
5
+50
$\begingroup$

Since neither HALT nor UC is computable, the machine $M_{UC}$ actually does not exist. The proof by contradiction assumes that HALT is computable and then constructs a machine $M_{UC}$, which contradicts the preceding theorem. This machine is hypothetical, and the proof of Theorem 1.10 indeed shows that it doesn't exist. That's why HALT cannot be computable.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I think the logic of the book is wrong(For your convenience, I've quoted the part of the book in the next comment)? The book wants to use logic like this, he wants to show if HALT is computable, then UC is computable, and since UC is uncomputable which conflicts with theorem 1.10, so HALT is not computable. But he doesn't successfully build $M_{UC}$ from $M_{HALT}$, because $M_{UC}$ cannot compute itself! Am I right? I think I'm right but not sure, want to confirm, thanks! $\endgroup$
    – narip
    Nov 30, 2021 at 10:48
  • $\begingroup$ PROOF: Suppose, for the sake of contradiction, that there was a TM $M_{\text {HALT }}$ computing HALT. We will use $M_{\text {HALT }}$ to show a TM $M_{U C}$ computing UC, contradicting Theorem $1.10$. The TM $M_{\mathrm{UC}}$ is simple: On input $\alpha, M_{\mathrm{UC}}$ runs $M_{\mathrm{HALT}}(\alpha, \alpha)$. If the result is 0 (meaning that $M_{\alpha}$ does not halt on $\alpha$ ), then $M_{U C}$ outputs 1 . Otherwise, $M_{U C}$ uses the universal TM $\mathcal{U}$ to compute $b=M_{\alpha}(\alpha)$. If $b=1$, then $M_{\cup c}$ outputs 0 ; otherwise, it outputs $1 .$ $\endgroup$
    – narip
    Nov 30, 2021 at 10:50
  • $\begingroup$ Under the assumption that $M_{\mathrm{HALT}}(\alpha, \alpha)$ outputs HALT $(\alpha, \alpha)$ within a finite number of steps, the TM $M_{U C}(\alpha)$ will output UC $(\alpha)$. $\endgroup$
    – narip
    Nov 30, 2021 at 10:50
  • $\begingroup$ The book's logic appears impeccable. Indeed, you can compute UC using a Turing machine with access to an oracle for the halting problem. $\endgroup$
    – Yuval Filmus
    Nov 30, 2021 at 11:03
  • 3
    $\begingroup$ The proof shows that such a machine cannot exist, so your question is meaningless. This contradiction is the entire point of the argument - it implies that such a machine cannot exist, and so that the halting problem isn’t decidable, since if it were, then you could construct $M_{UC}$. This proof has been rehashed on dozens of questions on this site, answering many times the very same doubt that you raise. I suggest looking at some of them. $\endgroup$
    – Yuval Filmus
    Dec 1, 2021 at 8:19

Your Answer

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

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