Our intuitive understanding of infinity leads us to think that infinite sets are all the same size, since they all have infinitely many things in them. And there are many examples of infinite sets that seem “bigger” than the naturals that are really countable, like the rationals or $\mathbb N^k$. As a result, we might then expect that we can if we try hard enough, we can always show that every infinite set is countable and come up with an appropriate bijection. This turns out not to be the case and there are indeed infinite sets that are larger than $\mathbb N$. Such a set is said to be uncountable, since it is not countable.
The first such argument, the diagonal argument, is a proof by contradiction, which is typically attributed to Cantor. The most well-known use is in showing that there are strictly more reals than naturals. Suppose that $\mathbb R$ were countable. Then there’s a bijection $f : \mathbb N \to \mathbb R$ and we can list all the elements. We can then use this hypothetical list to construct a real number $x \in \mathbb R$. However, by the way that the real number $x$ is constructed, it is actually impossible that it shows up in the list, which implies that $f$ could not have been a bijection after all.
We’ll start by using it to show that unrecognizable languages exist—that is, languages for which no Turing machine exists that will recognize them. We showed that the finite strings over $\Sigma$ are countable. What does this say about our ability to compute and solve the associated problems? The set of languages turns out to be uncountable. We’ll adapt Cantor’s diagonal argument for this proof.
For every alphabet $\Sigma$, the set of languages, $2^{\Sigma^*}$, is uncountable.
Suppose that $2^{\Sigma^*}$ is countable. We will make use of the countability of $\Sigma^*$. Since we assume that $2^{\Sigma^*}$ is countable, there exists a bijection $f : \Sigma^* \to 2^{\Sigma^*}$. In other words, we map each string over $\Sigma$ to a language, or a subset of $\Sigma^*$.
Now, define the language $D$ by \[D = \{w \in \Sigma^* \mid w \not \in f(w)\}.\] Since $D \subseteq \Sigma^*$ is a language and $f$ is a bijection, there exists a string $x \in \Sigma^*$ such that $f(x) = D$. So we can ask ourselves whether $x \in D$. We have \[x \in D \iff x \in f(x),\] since $D = f(x)$. But by definition of $D$, we have \[x \in D \iff x \not \in f(x).\] This gives us \[x \in f(x) \iff x \not \in f(x),\] or, in other words, \[x \in D \iff x \not \in D,\] which is a contradiction. Therefore, $2^{\Sigma^*}$ is not countable.
Why is this called a diagonalization argument? Consider the following table, where we have strings running down, and a list of languages running across. This table tells us, hypothetically, whether a particular string is in a particular language, which is something we can construct if we had $f$. Notice that $D$ is constructed by going along the diagonal: $x \in D$ if and only if $x \not\in f(x)$. The contradiction becomes clear when we try to look up the entry for $D$ on $w$, where $f(w) = D$.
| $L_0$ | $L_1$ | $L_2$ | $L_3$ | $L_4$ | $\cdots$ | $D$ | $\cdots$ | |
|---|---|---|---|---|---|---|---|---|
| $f(\varepsilon)$ | $f(0)$ | $f(1)$ | $f(00)$ | $f(01)$ | $\cdots$ | $f(x)$ | $\cdots$ | |
| $\varepsilon$ | ✔️️ | ❌ | ✔️️ | ✔️️ | ❌ | ❌ | ||
| $0$ | ✔️️ | ❌ | ✔️️ | ❌ | ❌ | ✔️️ | ||
| $1$ | ❌ | ✔️️ | ✔️️ | ✔️️ | ❌ | ❌ | ||
| $00$ | ✔️️ | ❌ | ❌ | ❌ | ❌ | ✔️️ | ||
| $01$ | ✔️️ | ❌ | ✔️️ | ✔️️ | ❌ | ✔️️ | ||
| $\vdots$ | $\ddots$ | $\vdots$ | ||||||
| $x$ | ❌ | ✔️️ | ✔️️ | ❌ | ✔️️ | $\cdots$ | ⁇ | $\cdots$ |
| $\vdots$ | $\vdots$ | $\ddots$ |
This proof might seem a bit discomforting because of the way that we defined $D$. And you are not alone—many (admittedly unserious) people are so uncomfortable with diagonalization arguments that they dispute that $|\mathbb R| \gt |\mathbb N|$. But even if you are uncomfortable with how we defined $D$, it has to exist! There has to be a language with the words that we picked, and if it’s a language, it has to show up in somewhere in our bijection.
If you’re familiar with the original diagonalization argument, another way to think about this is that the set of finite strings corresponds to the set of natural numbers. As we argued before, the strings over an alphabet of size $k$ can be thought of as encodings of numbers in base $k$. But what about languages?
There are a number of representations for real numbers, but the one we’re interested in is the real number as an infinite sequence of digits. So if we imagine the real number $0.437$, there’s really an infinite sequence of 0’s following it. But this is the base-10 representation. If we go to base 2, then we have infinite binary sequences.
We can argue that languages, or binary functions over strings, correspond to infinite binary sequences in the following way. Fix an alphabet $\Sigma$. We’ve said already that strings over $\Sigma$ are base $k$ representations of a natural number. So there’s a string for $n$. We can define an infinite binary sequence for a language $L$ by choosing the $n$th digit to be 1 if the string for $n$ is in $L$ and 0 otherwise. So this infinite binary sequence encodes our language.
We can now use this fact to show that there are languages that are not recognizable. In other words, there are languages that have no Turing machine that recognizes them.
There exist languages that are not Turing-recognizable.
First, we need to show that the set of Turing machines is countable. Recall that the set of all string $\Sigma^*$ is countable. Then we observe that every Turing machine has a string encoding $\llbracket M \rrbracket$, for some fixed encoding. Now, not every string corresponds to a proper encoding of a Turing machine, but we can ignore or skip all of those. Thus, there are countably many Turing machines.
Now, suppose that every language is recognizable. Then there is a Turing machine that recognizes each of these languages. We can define a mapping $f : \Sigma^* \to 2^{\Sigma^*}$ that assigns each Turing machine to the language it recognizes. However, we have showed that the set of all languages is uncountable. Thus, $f$ cannot be a bijection, and in fact, there are strictly more languages than there are Turing machines. This means there must exist some language that is not recognized by a Turing machine.
This might be a bit surprising, but it is also not quite satisfying. After all, who cares if there’s some crazy problem out there that’s not solvable? What if we only care about “real” problems?
We will show that there is at least one “useful” problem that is not possible to decide: membership for Turing machines, $\mathsf{A_{TM}}$.
Why is this problem useful? Recall that it is recognizable, just by being able to run the machine. That’s not actually that exciting, just running it and checking the result. But what deciding the problem would say is that it is possible to determine the behaviour of the machine without running it and only by examining its description/encoding.
In modern terms, this is the difference between running a program and seeing what it does and reading the source code of a program and figuring out what it does, without having to run it.
An undecidability result tells us that such analysis is not possible—there is no algorithm that can take the source of any program and any input and tell us what its output is going to be without running it.
Let’s show that $\mathsf{A_{TM}}$, or membership for Turing machines, is undecidable.
$\mathsf{A_{TM}}$ is undecidable.
We assume that $\mathsf{A_{TM}}$ is decidable and end up showing that it isn’t. Suppose we have a TM $H$ that decides $\mathsf{A_{TM}}$. Then on $\llbracket M,w \rrbracket$, $H$ halts and accepts if $M$ accepts $w$ and it rejects if $M$ does not accept $w$.
We construct a new TM $D$ that takes as input the description of a Turing machine and operates as follows:
This seems a bit strange, but first, we recall that $H$ is a Turing machine that takes a Turing machine $M$ and a string $w$ to run on $M$ as input. This is two parameters. Here, $D$ “calls” $H$ with the arguments $M$ and $\llbracket M \rrbracket$. This is a bit easier to see if we render it in pseudocode.
\begin{algorithmic}
\PROCEDURE{D}{$\llbracket M \rrbracket$}
\STATE result $ \gets $ \CALL{H}{$\llbracket M, \llbracket M \rrbracket \rrbracket$}
\IF{result $ = $ \textsf{Accept}}
\RETURN{\textsf{Reject}}
\ELSE
\RETURN{\textsf{Accept}}
\ENDIF
\ENDPROCEDURE
\end{algorithmic}
Let’s consider the result of running each Turing machine on a string of encodings of Turing machines. Essentially, we have \[L(D) = \{\llbracket M \rrbracket \in \Sigma^* \mid \llbracket M \rrbracket \not \in L(M)\}.\]
Again, we can view this as a table. Suppose we have an enumeration of Turing machines $M_1, M_2, \dots$. Then, we have the list of Turing machine encodings running down and whether the $i$th machine accepts it running across. Now, let’s consider the result of $D$ when run on a description of one of these machines: it is basically the opposite of whatever runs along the diagonal.
| $M_1$ | $M_2$ | $M_3$ | $M_4$ | $M_5$ | $\cdots$ | $D$ | $\cdots$ | |
| $\llbracket M_1 \rrbracket$ | ✔️️ | ❌ | ✔️️ | ✔️️ | ❌ | ❌ | ||
| $\llbracket M_2 \rrbracket$ | ✔️️ | ❌ | ✔️️ | ❌ | ❌ | ✔️️ | ||
| $\llbracket M_3 \rrbracket$ | ❌ | ✔️️ | ✔️️ | ✔️️ | ❌ | ❌ | ||
| $\llbracket M_4 \rrbracket$ | ✔️️ | ❌ | ❌ | ❌ | ❌ | ✔️️ | ||
| $\llbracket M_5 \rrbracket$ | ✔️️ | ❌ | ✔️️ | ✔️️ | ❌ | ✔️️ | ||
| $\vdots$ | $\ddots$ | $\vdots$ | ||||||
| $\llbracket D \rrbracket$ | ❌ | ✔️️ | ✔️️ | ❌ | ✔️️ | $\cdots$ | ⁇ | $\cdots$ |
| $\vdots$ | $\vdots$ | $\ddots$ |
Now, let us consider the result of $D$ when run on the input string $\llbracket D \rrbracket$. We have \[\llbracket D \rrbracket \in L(D) \iff \llbracket D \rrbracket \not \in L(D).\] That is, $D$ must accept if $D$ does not accept $\llbracket D \rrbracket$ and it must reject if $D$ accepts $\llbracket D \rrbracket$, which is a contradiction. Thus, neither Turing machines $D$ or $H$ can exist and $\mathsf{A_{TM}}$ is undecidable.
This result will be quite handy. We can make use of this to show that there are many other problems that aren’t decidable either. To start, we’ll consider a problem that you’ve likely already heard about: Turing’s halting problem.
The Halting Problem is “Given a Turing machine $M$ and string $w$, does $M$ halt when run on $w$?” and is defined \[ \mathsf{HALT}_{\mathsf{TM}} = \{ \llbracket M,w \rrbracket \mid \text{$M$ is a TM and $M$ halts on input $w$} \}.\]
$\mathsf{HALT}_{\mathsf{TM}}$ is undecidable.
Assume that there exists a Turing machine $H$ that decides $\mathsf{HALT}_{\mathsf{TM}}$. Then we can construct the following Turing machine to decide $\mathsf{A_{TM}}$:
Again, if we think of this algorithmically, we can see follow the pseudocode to the natural conclusion.
\begin{algorithmic}
\PROCEDURE{tm-accept}{$\llbracket M,w \rrbracket$}
\STATE result $ \gets $ \CALL{H}{$\llbracket M, w \rrbracket$}
\IF{result $ = $ \textsf{Reject}}
\RETURN{\textsf{Reject}}
\ELSE
\STATE result2 $ \gets $ \CALL{M}{$w$}
\IF{result2 $ = $ \textsf{Reject}}
\RETURN{\textsf{Accept}}
\ELSE
\RETURN{\textsf{Reject}}
\ENDIF
\ENDIF
\ENDPROCEDURE
\end{algorithmic}
So if $H$ decides $\mathsf{HALT}_{\mathsf{TM}}$, then we can decide $\mathsf{A_{TM}}$ with the preceding TM. However, we know that $\mathsf{A_{TM}}$ is undecidable, so this is a contradiction and $\mathsf{HALT}_{\mathsf{TM}}$ must be undecidable.
As it turns out, Turing’s original proof of (what we now call) the halting problem is shown directly via a diagonal argument like the proof of the undecidability of $\mathsf{A_{TM}}$. It’s not too hard to see how we might be able to modify the proof of $\mathsf{A_{TM}}$ to work for the halting problem.
Why is this problem of interest? In modern terms, this is the problem of determining whether a given program ever halts on a particular input. You can think of this as being able to check for infinite loops without actually running the program and only by examining the source code of the program.
But originally, this was already quite interesting mathematically. Consider a problem like Goldbach’s conjecture: Every even natural number greater than 2 is the sum of two prime numbers. We can write a short program that tests every even number and stops after it finds one that isn’t the sum of two primes. Does the program ever halt? If it does, then this disproves the conjecture.
And recall that the original context of this work was in trying to determine whether mathematics was decidable in this way. And in order to know this, any such algorithm would have to be guaranteed to stop and produce an answer.
Let’s look at some more examples of undecidable languages. To show that these languages are undecidable, we will start using an idea that is fairly central to theoretical computer science: reducibility. If you’ve taken algorithms or complexity theory, this is the same idea behind reductions in those courses.
Essentially, this is the idea that you can be clever about using a solution to some other problem you’ve already solved. For instance, it is a bit tedious to show that a problem is undecidable by setting up a diagonalization argument every time. Instead, we can make use of results that we’ve already proved, which in this case would involve reducing a problem to some other problem that we know is already undecidable.
In fact, we already did this to show that the Halting problem was undecidable: instead of constructing a bespoke diagonalization proof, we made use of the fact that we already showed $\mathsf{A_{TM}}$ was undecidable. Schematically, this looks kind of like the following:
Here’s the idea. Suppose we want to show that some language $L$ is undecidable. Let’s assume it’s decidable—then there’s a Turing machine we can run that will decide it. We can then use this Turing machine to decide something we’ve already shown is undecidable. This can’t be right—it’s a contradiction, so our assumption that our language was undecidable must have been incorrect.
Let’s consider the emptiness problem for Turing machines.
The emptiness problem for Turing machines is “Given a Turing machine, does it not accept every string?” This is the language \[ \mathsf{E_{TM}} = \{ \llbracket M \rrbracket \mid \text{$M$ is a TM and $L(M) = \emptyset$} \}. \]
$\mathsf{E_{TM}}$ is undecidable.
In modern terms, we might think of this as trying to see if a given program produces anything at all.
First, we describe the construction for a machine $M_w$ that is based on some Turing machine $M$ and some string $w$. It operates in the following way:
The machine $M_w$ rejects every word that is not $w$. Then the only word that can be accepted is $w$. If $M_w$ doesn’t accept $w$, then $L(M_w) = \emptyset$. In other words, we can describe the language of $M_w$ as \[L(M_w) = \begin{cases} \{w\} & \text{if $M$ accepts $w$}, \\ \emptyset & \text{if $M$ does not accept $w$}. \end{cases}\] Thus, $M_w$ recognizes the empty language if and only if it doesn’t accept $w$. We will use this construction in our proof.
\begin{algorithmic}
\PROCEDURE{M-w-hardcoded}{$x$}
\IF{$x \neq w$}
\RETURN{\textsf{Reject}}
\ELSE
\STATE result $ \gets $ \CALL{M}{$w$}
\IF{result $ = $ \textsf{Accept}}
\RETURN{\textsf{Accept}}
\ELSE
\RETURN{\textsf{Reject}}
\ENDIF
\ENDIF
\ENDPROCEDURE
\end{algorithmic}
Now, we assume that there exists a TM $R$ that decides $\mathsf{E_{TM}}$ and construct a TM $S$ that decides $\mathsf{A_{TM}}$ as follows:
In other words, $S$ takes the input $\llbracket M, w \rrbracket$ and uses it to build the machine $M_w$ that we defined earlier. One way to think about this in modern terms is the idea of defining an “inner function” based on some given input.
\begin{algorithmic}
\PROCEDURE{tm-accept}{$\llbracket M,w \rrbracket$}
\PROCEDURE{M-w-hardcoded}{$x$}
\IF{$x \neq w$}
\RETURN{\textsf{Reject}}
\ELSE
\STATE result $ \gets $ \CALL{M}{$w$}
\IF{result $ = $ \textsf{Accept}}
\RETURN{\textsf{Accept}}
\ELSE
\RETURN{\textsf{Reject}}
\ENDIF
\ENDIF
\ENDPROCEDURE
\STATE result $ \gets $ \CALL{is-empty}{$\llbracket$\CALL{M-w-hardcoded}{}$\rrbracket$}
\IF{result $ = $ \textsf{Accept}}
\RETURN{\textsf{Reject}}
\ELSE
\RETURN{\textsf{Accept}}
\ENDIF
\ENDPROCEDURE
\end{algorithmic}
Thus, if $R$ decides $\mathsf{E_{TM}}$, then $S$ decides $\mathsf{A_{TM}}$. However, we know that $\mathsf{A_{TM}}$ is undecidable, so $R$ cannot exist and $\mathsf{E_{TM}}$ is undecidable.
This gives us a handy way to show that other decision problems for Turing machines are undecidable. Let’s consider the problem of equality between two TMs.
The equality problem for Turing machines is “Given Turing machines $M$ and $N$, are the languages of $M$ and $N$ equal?”, and is defined \[\mathsf{EQ}_{\mathsf{TM}} = \{ \llbracket M_1, M_2 \rrbracket \mid \text{$M_1,M_2$ are TMs and $L(M_1) = L(M_2)$} \}.\]
$\mathsf{EQ}_{\mathsf{TM}}$ is undecidable.
This time, we reduce from $\mathsf{E_{TM}}$. Suppose we have a TM $R$ that decides $\mathsf{EQ}_{\mathsf{TM}}$. Then we can construct the following TM to decide $\mathsf{E_{TM}}$.
The idea is relatively straightforward: construct a Turing machine that rejects all strings, which is pretty easy to do. Then test it against the given Turing machine.
\begin{algorithmic}
\PROCEDURE{tm-empty}{$\llbracket M \rrbracket$}
\PROCEDURE{reject-all}{$x$}
\RETURN{\textsf{Reject}}
\ENDPROCEDURE
\STATE result $ \gets $ \CALL{tm-equal}{$\llbracket M,$\CALL{reject-all}{}$\rrbracket$}
\IF{result $ = $ \textsf{Accept}}
\RETURN{\textsf{Accept}}
\ELSE
\RETURN{\textsf{Reject}}
\ENDIF
\ENDPROCEDURE
\end{algorithmic}
Here, $N$ rejects all input so $L(N) = \emptyset$. If we test whether $M$ and $N$ accept the same language, then we’re basically testing whether $L(M) = \emptyset$ and now we have a way to decide $\mathsf{E_{TM}}$.