# Clarification of Theorem 1.11 in the book Computational Complexity by Arora/Barak

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

• 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. – 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.