from tock import *
Now we shift for the moment to a totally different topic, the uncountability of the real numbers. The concept of an uncountable infinity, and the associated proof technique of diagonalization, was discovered by Georg Cantor. Unfortunately, it also drove him crazy.
Read subsection "The Diagonalization Method," from page 202 to the table at the top of page 206.
Watch W10E1: Diagonalization.
Suppose that there are countably many real numbers. Then there is a way to enumerate all the real numbers in $[0,1)$. We can write the digits after the decimal point in a table like this:
$x_1$ | .1 | 4 | 1 | 5 | $\cdots$ |
$x_2$ | .5 | 5 | 5 | 5 | $\cdots$ |
$x_3$ | .1 | 2 | 3 | 4 | $\cdots$ |
$x_4$ | .5 | 0 | 0 | 0 | $\cdots$ |
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
Then we can form a new real number by taking the diagonal and changing every digit (but avoid 0 and 9, as explained in the book):
$x_1$ | .1 | 4 | 1 | 5 | $\cdots$ |
$x_2$ | .5 | 5 | 5 | 5 | $\cdots$ |
$x_3$ | .1 | 2 | 3 | 4 | $\cdots$ |
$x_4$ | .5 | 0 | 0 | 0 | $\cdots$ |
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | |
$x'$ | .2 | 6 | 4 | 1 | $\cdots$ |
This new number cannot be equal to any row of the table, which is a contradiction.
We can adapt Cantor's argument for the uncountability of the reals to an argument for the uncountability of the set of all languages. Our proof is different from the book's proof of Corollary 4.18 (page 206), and I think it should be okay just to read ours.
Suppose that there are countably many languages over a finite alphabet $\Sigma$. Then we can number them $L_1, L_2, L_3, \ldots$.
We can number all strings in $\Sigma^\ast$ in shortlex order. Call the $j$th string in this ordering $w^{(j)}$. (We use this notation to avoid confusion with the notation $w_j$ for the $j$th symbol of $w$.)
Imagine a big table whose $i$th row is $L_i$ and whose $j$th column is $w^{(j)}$, and cell $(i,j)$ says whether $w^{(j)} \in L_i$. For illustration's sake, we assume $\Sigma = \{\mathtt{0}, \mathtt{1}\}$.
$\varepsilon$ | $\mathtt{0}$ | $\mathtt{1}$ | $\mathtt{00}$ | $\cdots$ | |
---|---|---|---|---|---|
$L_1$ | no | yes | no | yes | $\cdots$ |
$L_2$ | no | yes | yes | no | $\cdots$ |
$L_3$ | yes | no | yes | no | $\cdots$ |
$L_4$ | no | no | no | yes | $\cdots$ |
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
Then we can form a new language by taking all the diagonal entries of this table and inverting them (yes to no and no to yes):
$\varepsilon$ | $\mathtt{0}$ | $\mathtt{1}$ | $\mathtt{00}$ | $\cdots$ | |
---|---|---|---|---|---|
$L_1$ | no | yes | no | yes | $\cdots$ |
$L_2$ | no | yes | yes | no | $\cdots$ |
$L_3$ | yes | no | yes | no | $\cdots$ |
$L_4$ | no | no | no | yes | $\cdots$ |
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | |
$L'$ | yes | no | no | no | $\cdots$ |
More formally, $$L' = \{ w^{(i)} \mid w^{(i)} \not\in L_i \}.$$
This language $L'$ cannot be equal to any row of the table, because for any $i$, either $w^{(i)} \in L'$ but $w^{(i)} \not\in L_i$, or $w^{(i)} \not\in L'$ but $w^{(i)} \in L_i$.
But the table supposedly contains all possible languages, which is a contradiction. Therefore there are uncountably many languages.
Today's topic is undecidability: is there such a thing as a language that can't be decided by a Turing machine (and therefore, by any computer program as we know it)?
The answer is yes, and not only so, but almost all languages are undecidable.
Watch W10E2: Undecidable Languages.
Since Turing machines can be encoded as strings, there is a way to number all possible Turing machines $M_1, M_2, M_3, \ldots$ (e.g., sort their encodings in shortlex order and then number them consecutively). It follows that there are languages (in fact, almost all languages) which cannot be decided by any Turing machine. But we'd like a proof that explicitly constructs such a language.
Imagine a big table whose $i$th row is $M_i$ and whose $j$th column is $w^{(j)}$, and cell $(i,j)$ says whether $w^{(j)} \in \mathcal{L}(M_i)$ (that is, it says "yes" if $M_i$ accepts $w^{(j)}$, but "no" if $M_i$ rejects or loops on $w^{(j)}$.)
$\varepsilon$ | $\mathtt{0}$ | $\mathtt{1}$ | $\mathtt{00}$ | $\cdots$ | |
---|---|---|---|---|---|
$M_1$ | no | yes | no | yes | $\cdots$ |
$M_2$ | no | yes | yes | no | $\cdots$ |
$M_3$ | yes | no | yes | no | $\cdots$ |
$M_4$ | no | no | no | yes | $\cdots$ |
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
We can again form a new language by taking all the diagonal entries of this table and inverting them:
$$L_D = \{w^{(i)} \mid \text{$M_i$ does not accept $w^{(i)}$}\}$$And this language again cannot be equal to any row of the table, because for any $i$, either $w^{(i)} \in L_D$ but $M_i$ does not accept $w^{(i)}$, or $w^{(i)} \not\in L_D$ but $M_i$ accepts $w^{(i)}$.
This means that there is no such thing as a Turing machine that decides $L_D$. (In fact, there isn't even one that recognizes it.)
The book's first example of an undecidable language is
$$A_{\mathsf{TM}} = \{ \langle M, w \rangle \mid \text{$M$ accepts $w$} \}.$$This language will be very useful for proving other undecidable languages. We can prove $A_{\mathsf{TM}}$ undecidable by continuing our proof above. Suppose that there exists a decider $H$ that decides $A_{\mathsf{TM}}$.
Then we would be able to compute the value of any cell of the above table since $H$ is supposedly a decider. But that would enable us to define a decider for $L_D$. Namely, define a TM $D$ that, on input $w$,
But we know this is impossible, either by using the undecidability of $L_D$ as shown above, or we can repeat the argument again. If $D$ exists, then for some $i$, $D = M_i$. If $D$ accepts $w^{(i)}$, then (by the definition of $D$) we know that $H$ rejects $\langle D, w^{(i)}\rangle$, but (by the definition of $H$) it was supposed to accept. Similarly, if $D$ rejects $w^{(i)}$, then (by the definition of $D$) we know that $H$ accepts $\langle D, w^{(i)}\rangle$, but (by the definition of $H$) it was supposed to reject. Therefore, $D$ cannot exist, and $A_{\mathsf{TM}}$ is undecidable.
Read: If the above isn't clear, try the book's proof on pages 207–209.
Watch W10E3: The Halting Problem.
Most books use the following language as their first undecidable language:
$$\mathit{HALT}_{\mathsf{TM}} = \{ \langle M, w \rangle \mid \text{$M$ halts on $w$} \}.$$This is probably the most well-known undecidable problem: Can you write a program that looks at another program $M$ and input $w$ and decides whether $M$ halts or loops on $w$?
Question: Adapt the above diagonalization argument to prove that $\mathit{HALT}_{\mathsf{TM}}$ is undecidable.
For fun, you can read Geoff Pullum's "Scooping the Loop Snooper: A proof that the Halting Problem is undecidable."
The following table may help. Unlike our proof above (and like Sipser's), the columns of the table are not the strings in shortlex order, but the encodings of $M_1, M_2, \ldots$.
$M_1$ | $M_2$ | $M_3$ | $M_4$ | $\cdots$ | $Q$ | $\cdots$ | |
---|---|---|---|---|---|---|---|
$M_1$ | bad! | good! | bad! | good! | $\cdots$ | good! | $\cdots$ |
$M_2$ | bad! | good! | good! | bad! | $\cdots$ | bad! | $\cdots$ |
$M_3$ | good! | bad! | good! | bad! | $\cdots$ | good! | $\cdots$ |
$M_4$ | bad! | bad! | bad! | good! | $\cdots$ | good! | $\cdots$ |
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | bad! | $\cdots$ |
$Q$ | good! | bad! | bad! | bad! | $\cdots$ | ??? | $\cdots$ |
Read the subsection "A Turing-Unrecognizable Language."
Now that we've proven that one language ($A_{\mathsf{TM}}$) is undecidable, we can use it to prove that other languages are undecidable.
Read pages 215–217, up to "via the diagonalization method."
The first example is the halting problem $\mathit{HALT}_{\mathsf{TM}}$. In many textbooks (and the poem "Scooping the Loop Snooper"), the halting problem is actually the prototypical undecidable language, but Sipser does things a little differently.
To prove that the halting problem is undecidable, you assume that it is decidable, that is, there is a TM $R$ that decides it. Then, you show that armed with such a TM, you could implement another TM, $S$, that decides $A_{\mathsf{TM}}$, which is a contradiction because we know that $A_{\mathsf{TM}}$ is undecidable.
Remember that the direction of the reduction is the opposite of what most people intuitively think of first. If you want to show that the halting problem is undecidable, you do not reduce the halting problem to $A_{\mathsf{TM}}$; you reduce $A_{\mathsf{TM}}$ to the halting problem. To avoid confusion (and, you will see that the potential for confusion grows below), we give a nickname to each TM to help you remember which is which. Call $R$ the "loop snooper," in homage to Pullum, and $S$ the "universal decider" (because it's a universal TM but it always halts).
So, suppose that we had a TM $R$ (the loop snooper) that decides the halting problem $\mathit{HALT}_{\mathsf{TM}}$. Then, designing a universal decider $S$ would be easy: $S =$ "On input $\langle M, w\rangle$,
But last time we showed (by diagonalization) that the universal decider $S$ does not exist. Therefore, the loop snooper $R$ cannot exist either.
Watch (optional) W10E4: The Penrose-Lucas Argument.
Turing machines were invented as a model of what it means for humans, not computing machines, to compute, and so a natural question is, can Turing machines serve as a model for all human reasoning? I want to present to you one argument for the "no" position. Turing called it "the mathematical objection" and it is usually known today as the Penrose-Lucas argument. This version, which is an interesting variation on the diagonalization argument for the undecidability of the halting problem, is due to Penrose and comes from an article criticizing him. Although I agree with the conclusion, I don't agree with the argument -- what do you think about it?
Let $R$ be a "partial loop-snooper," a decider TM that detects some cases of looping. That is, on input $\langle M, w\rangle$, if $R$ accepts, then $M$ loops on input $w$. But if $R$ rejects, it doesn't mean anything.
Now we go through the usual diagonalization argument; the only difference is that it doesn't lead to a contradiction, but to a machine/input pair that is beyond $R$'s detection abilities. Assume an ordering $M_1, M_2, \ldots$ on Turing machines and an ordering $w^{(1)}, w^{(2)}, \ldots$ on strings. We can build a big table with the results of $R$ on all machines and inputs:
$\varepsilon$ | $\mathtt{0}$ | $\mathtt{1}$ | $\mathtt{00}$ | $\cdots$ | |
---|---|---|---|---|---|
$M_1$ | don't know | loops | don't know | loops | |
$M_2$ | don't know | loops | loops | don't know | |
$M_3$ | loops | don't know | loops | don't know | |
$M_4$ | don't know | don't know | don't know | loops | |
$\vdots$ |
We define $D$ to be the Turing machine that does the opposite of the diagonal of this table. That is, on input $w$:
Now, there must be an $i$ such that $D = M_i$. We claim that $D$ loops on $w^{(i)}$ but $R$ does not detect it.
So, in fact, $D$ does loop on $w^{(i)}$, but $R$ does not detect it.
It's critical that you understand the argument thus far before moving on.
Suppose that you are equivalent to a Turing machine. You have a partial ability to detect looping. So it should be possible to construct a Turing machine $Y$ that accepts $\langle M, w\rangle$ in exactly those cases when you are able to detect that $M$ loops on input $w$.
Then, by the above argument, there is a machine/input pair $\langle D, w^{(i)}\rangle$ that loops, but $Y$ rejects it. By the definition of $Y$, you are not able to detect that $\langle D, w^{(i)}\rangle$ loops. But if you understood the above argument, then you know that $\langle D, w^{(i)}\rangle$ does loop. This is a contradiction! Therefore, congratulations! You are not equivalent to a Turing machine.