Cantor’s diagonal argument and undecidability

Posted by: Alan Guo | July 12, 2011

Cantor’s diagonal argument and undecidability

Probably every mathematician is familiar with Cantor’s diagonal argument for proving that there are uncountably many real numbers, but less well-known is the proof of the existence of an undecidable problem in computer science, which also uses Cantor’s diagonal argument. I thought it was really cool when I first learned it last year.

To understand undecidability, you first have to know what a Turing machine is. A Turing machine is just a theoretical model of a computer, with a work tape, a tape head which points to a cell on the tape, and a set of states. These three things determine a configuration of the TM. In addition, the TM comes with a transition function which dictates how the TM changes its configuration. Lastly, one of its states is designated the initial state, which is the state that the TM starts in every time it runs on an input, and some of its states are designated accept states, while others are designated reject states. A precise definition of a Turing machine can be found in any textbook on theory of computation, but it’s not terribly important for our goal here. The thing to take away is that a TM is given an input (written on its tape), then its transition function dictates what it does (like an algorithm), and if the TM lands on an accept state, then it accepts the input, and if it lands on a reject state, then it rejects the input. Note that it is also possible for infinite loops to occur for certain inputs, in which case the TM is considered to not accept or reject.

I didn’t mention what kind of inputs are allowed for Turing machines. It can be any finite alphabet $\Sigma$ , but I like to think of the allowed alphabet as $\{0, 1\}$ since that’s what we use in modern electronic computers, and two letters is enough to do everything you want to do, so from now on we’ll assume Turing machines take binary string inputs. A language is a set (possibly infinite) of binary strings. The language recognized by a Turing machine is the set of strings that it accepts. So, when we talk about “problems”, such as the primality problem (given an positive integer, determine if it’s prime) or the SAT problem (given a boolean formula, determine if it’s satisfiable), we are really talking about languages. For example, we can view the primality problem as the set of binary strings which represent prime numbers. Then the question of whether there exists an algorithm for deciding primality is actually whether there exists a Turing machine which decides the corresponding language.

I just used the term “decide” but I haven’t defined it yet. Whereas a machine recognizes a language if it accepts precisely those strings in it, a machine decides a language if it recognizes the language and halts on every input. The cool thing is that there are problems that are recognizable but not decidable, and showing that is the main goal of my post.

Consider the language

$L = \{\langle M, x \rangle : \text{ Turing machine } M \text{ accepts } x \}$

where $\langle M, x \rangle$ just means a binary string encoding $M$ concatenated with the binary string $x$ , with a delimiter in between so the Turing machine knows where the encoding of $M$ ends. In other words, the problem is to determine if a given Turing machine $M$ accepts a given binary string $x$ . This problem is recognizable. You can design a Turing machine $U$ , called the “universal Turing machine”, which can simulate any other Turing machine. Then, given input $\langle M, x \rangle$ , just simulate $M$ on $x$ and accept if $M$ accepts $x$ and reject if $M$ rejects $x$ . Clearly our machine will accept $\langle M, x \rangle$ if and only if $M$ accepts $x$ , so it recognizes $L$ . It doesn’t decide $L$ , however, since if $M$ goes into an infinite loop on $x$ , then so does our machine, but we want our machine to reject when this happens.

To show that $L$ is undecidable, we prove it by contradiction. Suppose we had a machine $D$ which decides $L$ . Note that every Turing machine has some encoding as a finite length binary string, so we can enumerate them as $M_1, M_2, M_3, M_4, \ldots$ and construct the following table:

$\begin{array}{cccccc} & M_1 & M_2 & M_3 & M_4 & \cdots \\ M_1 & 1 & 0 & 0 & 1 & \cdots \\ M_2 & 0 & 1 & 0 & 0 & \cdots \\ M_3 & 1 & 1 & 0 & 1 & \cdots \\ M_4 & 0 & 0 & 1 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$

where the entry in row $i$ , column $j$ is a $0$ if $M_i$ accepts $\langle M_j \rangle$ and is a $1$ if not. I just made up the numbers for concreteness. We can construct this table since we have $D$ (to determine the value of an entry, just run $D$ on $\langle M_i, M_j \rangle$ . Now, consider the Turing machine $M_{\text{bad}}$ which, given input $\langle M \rangle$ , does the opposite of what $D$ does on input $\langle M, M \rangle$ (if the input happens to not be a proper encoding of any Turing machine, then it’s irrelevant what $M_{\text{bad}}$ does). That is, $M_{\text{bad}}$ accepts $\langle M \rangle$ if the entry corresponding to $\langle M, M \rangle$ in our table is a $0$ , and rejects if the corresponding entry is a $1$ . Now, ask yourself: which $M_i$ is $M_{\text{bad}}$ ? For each $i$ , our machine $M_{\text{bad}}$ differs from $M_i$ on the input $\langle M_i \rangle$ , so it can’t be any of these. But we’ve enumerated all the Turing machines, so we have a contradiction! Therefore, $L$ is not decidable.

That ends the proof. I hope you found this as cool as I did when I first saw it. Anyway, feel free to leave comments if you have any questions about the proof, or corrections to it if I made a mistake.

-Alan

P.S. It’s also straightforward to see that there are languages that aren’t even Turing-recognizable, since there are countably many Turing machines but uncountably many languages.

About these ads

Posted in Computer Science | Tags: computer science, turing machine, undecidability

Responses

I’ve always liked this argument. I’m wondering how general this diagonalization tool is; it seems very functorial since it doesn’t depend on a lot of words like “machine” or “algorithm,” but as you said, is a bit more refined than “countable vs uncountable.”
By: yanzhang on July 13, 2011
at 2:08 PM
Unquestionably lovely. As to how general the argument is, see Lawvere’s category theoretic account, “Diagonal arguments and Cartesian closed categories”. (Given a more user-friendly treatment towards the end of his & Schanuel’s book “Conceptual mathematics”.)
By: Richard Elwes on July 18, 2011
at 4:34 PM
[...] old proof of the infinitude of primes and how fast one can get to unknown territory from there, Concrete Nonsense remembers the application of Cantor’s diagonal argument to prove the existen…, Mathlog tells us about the article “the unplanned impact of mathematics” [...]
By: Weekly Picks « Mathblogging.org — the Blog on July 20, 2011
at 5:49 AM

Concrete Nonsense