Now that we've proven that one language ($A_{\mathsf{TM}}$) is undecidable, we can use it to prove that other languages are undecidable.
The first example is the halting problem. 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.
The proof is not difficult but it has a weird feel to it. The first thing that you have to remember is 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 assume that the halting problem is decidable, then show via a reduction from $A_{\mathsf{TM}}$ to the halting problem that $A_{\mathsf{TM}}$ would also be decidable, which is a contradiction.
Recall that we designed $U$, a universal TM, that recognizes $A_{\mathsf{TM}}$, but we showed that we cannot design a TM $S$, a "universal decider," that decides $A_{\mathsf{TM}}$. Practically, the sticking point is that on input $\langle M, w\rangle$, if $M$ loops on $w$, we have no way to detect it so that we can reject. Enter $R$, a hypothetical TM that decides the halting problem $\mathit{HALT}_{\mathsf{TM}}$. If we had such a machine, then designing $S$ would be easy: Use $R$ to check for looping. if a loop is detected, reject; if no loop is detected, we can safely simulate $M$ and return what it returns. But last time we showed (by diagonalization) that $S$ does not exist. Therefore, $R$ cannot exist either.
The halting problem is a problem about the run of a particular machine $M$ on a particular $w$. There are lots of problems of this sort, but most have an extra wrinkle that involves creating a third TM besides $R$ and $S$. Since it can be hard to keep track of them all, here's an example involving Python programs that hopefully is easier to follow.
Let's show that it is undecidable whether a given Python program $P$ writes to the filesystem.
Suppose, for the sake of contradiction, that this is decidable. That is, there exists a TM $R$ that accepts $\langle P\rangle$ if and only if $P$ would write to the filesystem. Let's call it the write-detector.
We're going to build a universal decider $S$ that somehow uses the write-detector $R$ to decide $A_{\mathsf{TM}}$. We assume the presence of a Python function simulate
that simulates a TM and returns True
for accept or False
for reject or possibly loops.
Then $S = $ “On input $\langle M, w\rangle$:
import os
if simulate(M, w):
os.system("rm -rf /")
where M
and w
are filled in with data structures representing $M$ and $w$, respectively.
2. Run $R$, the write-detector, on $P$.
3. If $R$ detected a write, then accept.
4. Otherwise, reject.
The program $P$ acts as an "adapter" between the property we need to detect ($M$ accepting $w$) and the property that we can detect ($P$ writing to the filesystem).
To see that $S$ is a universal decider, let's walk through the possible cases:
Thus $S$ decides $A_{\mathsf{TM}}$ as desired, which is a contradiction. We conclude that it's undecidable whether a given Python program writes to the filesystem.
Hopefully, it's clear that there's a very wide variety of actions a machine/program can take that are undecidable to detect. (Your homework has one example of an action that is decidable to detect, though.)
Question. Try Problem 5.12: Show that it is undecidable whether a Turing machine ever erases a symbol (that is, overwrites a non-blank symbol with a blank symbol).
The next two examples in the book, Theorems 5.2 and 3, are slightly different. They are not questions about a single run of a machine, but about the entire language that the machine recognizes. Theorem 5.2 is about whether the language is empty; Theorem 5.3 is about whether the language is regular.
The basic shape of the proof is still the same. Assume that the question is decidable, so there is a TM $R$ that decides it. As before, we need to construct a new TM $S$ that decides $A_{\mathsf{TM}}$. As before, $S$ has to construct an "adapter" (called $M_1$ or $M_2$ in the book) that links the question that $S$ wants to decide (does $M$ accept $w$?) with the question that $R$ has the magic ability to answer.
Let's look at Theorem 5.2 first. Given $M$ and $w$, we can construct an adapter $M_1$ that recognizes a nonempty language iff $M$ accepts $w$.
$M_1 =$ “On input $x$:
Let's think carefully about what $M_1$ would do.
Finally, we define a universal decider $S =$ “On input $\langle M, w\rangle$:
Here's how $S$ works:
Thus $S$ decides $A_{\mathsf{TM}}$ as desired, which is a contradiction. We conclude that it's undecidable whether a given Turing machine recognizes the empty language.
The scopes of the variables involved in the above proof can be confusing, so it might or might not help to look at the TMs as Python functions:
def is_empty(M): # This is R
"""Returns True iff M recognizes \emptyset."""
# Insert magic code here
def accepts(M, w): # This is S
def M1(x):
"""Recognizes {w} if M(w) is True,
recognizes \emptyset otherwise."""
if x != w:
return False
else:
return M(w)
return not is_empty(M1)
The proof of Theorem 5.3 (regularity) is quite similar. Given $M$ and $w$, we can construct an adapter $M_2$ that recognizes a regular language iff $M$ accepts $w$.
$M_2 =$ “On input $x$:
Let's think carefully about what $M_2$ does.
The rest of the proof is very similar to the last one. We define a universal decider $S =$ “On input $\langle M, w\rangle$:
Here's how $S$ works:
Thus $S$ decides $A_{\mathsf{TM}}$ as desired, which is a contradiction. We conclude that it's undecidable whether a given Turing machine recognizes a regular language.
It turns out that there is a general recipe for proving results of this type. This is called Rice's Theorem and is the focus of one of the homework questions.
Question. Try proving: It is undecidable whether two given Turing machines $M_1$ and $M_2$ recognize the same language.
Alas, we don't have time to look at more examples of undecidable problems. The examples we've looked at so far may seem a little arcane because they are all questions about Turing machines, but some other examples are:
See the survey by Poonen for more examples.
Optional reading: The rest of Section 5.1 and Section 5.2.
Review for next Tuesday's midterm.