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

  • $\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 '14 at 9:33

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.


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.