20. Uncomputable Functions

The Power of Encoding

The basic object that we consider in the study of computability is a function \(f \colon \sigma^* \to \sigma^*\) which maps strings of symbols from some finite alphabet \(\sigma\) to other strings over the same alphabet. We already saw that even the simple binary alphabet \(\sigma = \{0,1\}\) suffices to let us encode natural numbers (using their natural binary representation) as strings so that this model lets us study the computability of functions on natural numbers.

We can also represent many, many other types of mathematical objects with strings.

• Integers. We can use an additional sign bit at the beginning of the string to represent all integers using strings over the alphabet \(\{0,1\}\). Alternatively, with the alphabet \(\{0,1,2,\ldots,9,-\}\), we can write integers directly in their usual decimal representation.

• Rationals. We can also represent all rational numbers using symbols from \(\{0,1,2,\ldots,9,-,/\}\). For example, the fraction \(-\frac{20}{33}\) is represented by the string \(-20/33\).

• Vectors. An alternative representation for rational numbers is as a list of two integers. We can write this list explicitly as \((-20,33)\), for example, by simply adding the parentheses and comma symbols to our alphabet. And with those symbols, we can now write arbitrarily long lists of symbols. This immediately gives us a way to write any tuples of representable elements or any vectors.

• Matrices. Matrices might seem a bit more tricky to write as strings since their usual representation is 2-dimensional. But we can simply add another symbol to our alphabet to denote the end of a line in a matrix. This approach gives us a direct way to encode matrices, as in this example:

• Graphs. Graphs can be represented as matrices (for example by writing down their adjacency matrix) so they too can also be encoded into strings.

• Functions. A function \(f \colon \mathcal{X} \to \mathcal{Y}\) with finite domain \(\mathcal{X}\) and finite range \(\mathcal{Y}\) can also be encoded since it can be represented as a list of \(|\mathcal{X}|\) elements in \(\mathcal{Y}\). For example, the \(\wedge\) binary function that we defined in propositional logic can be encoded as follows:

But the most interesting mathematical object to encode as a string in the study of computability is none of the above examples: it is Turing machines.

Big Idea. We can encode many different mathematical objects as strings, even Turing machines.

To see why Turing machines can be encoded as strings, we can go back to their definition in the last lecture. We can specify a Turing machine by fixing the number of internal states it contains, the number of symbols in the tape alphabet, and the transition function. And combining the observations above, we see that we can encode these three elements in a string.

Functions on Turing Machines

Once we know we can encode Turing machines as strings, the next natural question to ask is: what kind of functions whose inputs contain Turing machines might we want to consider? There are tons of natural problems about Turing machines that we can consider:

• Does the Turing machine \(M\) halt on every input?
• Does \(M\) halt on input \(x\)?
• Does \(M\) halt after at most \(t\) steps on input \(x\)?
• What is the smallest Turing machine \(M'\) that computes the same function as \(M\)?
• Do \(M_1\) and \(M_2\) compute the same function?
• Does \(M\) compute the \(\mathsf{IsEven}\) function?

As it turns out, only one of the above functions is computable. But there is one surprising thing that we can do with Turing machines: we can construct one Turing machine that can simulate all the other ones.

Theorem 1. There is a universal Turing machine \(U\) that for each input \(\left< M \right>, x\) simulates the Turing machine \(M\) on input \(x\) in the following sense:

• If \(M\) halts on input \(x\), then \(U\) halts as well and outputs the same string.
• If \(M\) does not halt on input \(x\), then \(U\) does not halt either.

This theorem has far-reaching consequences, but our interest for now is to prove that a specific function is uncomputable. And the best way to do that is to start with a function that is different from all the ones listed above. Consider the following function that considers what a Turing machine outputs when it is given its own description as input:

(This function is analogous to the set of all sets that don’t contain themselvesin Russell’s paradox.)

Theorem 2. The \(\mathsf{SelfReject}\) function is uncomputable.

Proof. Assume for the sake of contradiction that there is a Turing machine \(D\) that computes \(\mathsf{SelfReject}\). Consider \(D\)’s output when we run it with input \(\left< D \right>\).

• If \(D\) outputs \(0\), then by definition

  \[\mathsf{SelfReject}(\left< D \right>) = 1.\]

• But if \(D\) does not output \(0\), then by definition

  \[\mathsf{SelfReject}(\left< D \right>) = 0.\]

In both cases, we find that \(D\) does not output \(\mathsf{SelfReject}(\left<D\right>)\) on input \(\left< D \right>\), contradicting our assumption that it computes this function. Therefore, there is no Turing machine that computes \(\mathsf{SelfReject}\).

The proof of the uncomputability of \(\mathsf{SelfReject}\) is an example of a diagonalization argument.

Reduction

Once we have one uncomputable function, we can use it to prove that many other functions are uncomputable using reductions. Here’s one example of a reduction argument. Consider the function

Theorem 3. The \(\mathsf{Halting}\) function is uncomputable.

Proof. Assume for contradiction that there is a Turing machine \(T\) that computes the \(\mathsf{Halting}\) function. Let \(C\) be the Turing machine that takes \(\left< M \right>\) as input and:

• Runs \(T\) on input \(\left< M \right>, \left< M \right>\).
• If \(T\) outputs 0, \(C\) also halts and outputs 0.
• Otherwise, \(C\) simulates \(M\) on the input \(\left< M \right>\).
• Then once \(M\) halts, \(C\) halts with the output 1 if \(M\)’s output string was 0 and \(C\) outputs 0 otherwise.

Let us now examine the function that \(C\) computes. First, we see that \(C\) always halts, because \(T\) does (by assumption) and because \(C\) only simulates \(M\) when it is guaranteed that \(M\) will halt. When \(M\) halts on input \(\left< M \right>\) and outputs 0, then \(C\) outputs 1. Otherwise, if \(M\) halts on input \(\left< M \right>\) with any other output string or if it does not halt at all on this input, then \(C\) outputs 0. In other words, \(C\) computes the \(\mathsf{SelfReject}\) function. But this contradicts Theorem 2 that no such Turing machine exists, so our assumption that there exists a Turing machine which computes \(\mathsf{Halting}\) is false.