We showed last class that $A_{\mathsf{TM}}$, or membership for Turing machines, 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 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 $A_{\mathsf{TM}}$:
So if $H$ decides $\mathsf{HALT}_{\mathsf{TM}}$, then we can decide $A_{\mathsf{TM}}$ with the preceding TM. However, we know that $A_{\mathsf{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 $A_{\mathsf{TM}}$. It's not too hard to see how we might be able to modify the proof of $A_{\mathsf{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.
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 $A_{\mathsf{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. That is, given a Turing machine, does it not accept anything? This is the language \[ E_{\mathsf{TM}} = \{ \llbracket M \rrbracket \mid \text{$M$ is a TM and $L(M) = \emptyset$} \}. \]
$E_{\mathsf{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.
Now, we assume that there exists a TM $R$ that decides $E_{\mathsf{TM}}$ and construct a TM $S$ that decides $A_{\mathsf{TM}}$ as follows:
Thus, if $R$ decides $E_{\mathsf{TM}}$, then $S$ decides $A_{\mathsf{TM}}$. However, we know that $A_{\mathsf{TM}}$ is undecidable, so $R$ cannot exist and $E_{\mathsf{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, specified as \[\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 $E_{\mathsf{TM}}$. Suppose we have a TM $R$ that decides $\mathsf{EQ}_{\mathsf{TM}}$. Then we can construct the following TM to decide $E_{\mathsf{TM}}$.
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 $E_{\mathsf{TM}}$.
Here's another kind of question we can ask of Turing machines. Since they are so powerful, we may want to ask whether or not the language of a TM can be recognized by a less powerful model of computation, like a DFA. Such a language is defined \[ \mathsf{REG}_{\mathsf{TM}} = \{ \llbracket M \rrbracket \mid \text{$M$ is a TM and $L(M)$ is a regular language} \}.\] If we know this, then maybe we could come up witha simpler or more efficient way to solve this problem. As it turns out, this is not decidable either.
$\mathsf{REG}_{\mathsf{TM}}$ is undecidable.
Let $R$ be a TM that decides $\mathsf{REG}_{\mathsf{TM}}$. Construct a TM $S$ that does the following:
How does this work? The TM $M'$ accepts all strings in $\{0^n 1^n \mid n \geq 0\}$, which we know is context-free. If $M$ doesn't accept $w$, then $L(M') = \{0^n 1^n \mid n \geq 0\}$. If $M$ accepts $w$, then $M'$ also accepts every other string and in this case $L(M') = \Sigma^*$, which is regular. In other words, the language of $M'$ is \[L(M') = \begin{cases} \Sigma^* & \text{if $M$ accepts $w$}, \\ \{0^n 1^n \mid n \geq 0 \} & \text{if $M$ does not accept $w$}. \end{cases}\] In this way, if there's a way to figure out whether $M'$ recognizes a regular language, then we can come up with a way to decide $A_{\mathsf{TM}}$.
At this point, we begin to see a possible pattern emerge: if we want to ask about whether a Turing machine accepts this or that set of strings, we can come up with an easy way to test for membership. Simply construct a Turing machine that collapses to one language or another. Perhaps we can generalize this idea...
So far, it seems like every question we ask about Turing machines is undecidable. As it turns out, this is not just an educated hunch, but a theorem. First, we'll try to formalize the notion of a "property".
A property $P$ of a Turing machine is a semantic property if it depends on the language recognized by $M$ and not the syntactic structure of $M$. In other words, if $L(M_1) = L(M_2)$, then $M_1$ and $M_2$ have the same semantic properties.
A property $P$ can be expressed as a language consisting of exactly the encodings $\llbracket M \rrbracket$, where $M$ has property $P$. A semantic property $P$ is said to be non-trivial if there exists a TM $M_1$ such that $\llbracket M_1 \rrbracket \in P$ and a TM $M_2$ such that $\llbracket M_2 \rrbracket \not\in P$.
Then we have the following theorem.
All non-trivial semantic properties of Turing machines are undecidable.
In other words, for any given Turing machine $M$, we can't decide any properties about $L(M)$ except for properties that are true for either exactly all or exactly none of the languages recognized by Turing machines. The proof is surprisingly simple, since it follows the basic template that we've been using so far.
To show this, we let $P$ be a property (that is, a language of encodings of Turing machines that have the property) and assume that it is decidable. Let $R_P$ be a Turing machine that decides $P$. We will reduce TM membership to property testing.
Let $T_\emptyset$ be a Turing machine that rejects every string. So $L(T_\emptyset) = \emptyset$. Without loss of generality, we assume that $\llbracket T_\emptyset \rrbracket \not\in P$. Otherwise, we can just use $\overline P$ instead. Since $P$ is non-trivial, there exists a Turing machine $T$ with $\llbracket T \rrbracket \in P$.
We construct a Turing machine that decides $A_{\mathsf{TM}}$ by being able to distinguish between $T_\emptyset$ and $T$.
So $M_w$ simulates $T$ if $M$ accepts $w$. This gives us \[L(M_w) = \begin{cases} L(T) & \text{if $M$ accepts $w$}, \\ \emptyset & \text{otherwise}. \end{cases}\] Thus, $\llbracket M_w \rrbracket \in P$ iff $M$ accepts $w$.
Rice's theorem was proved by Rice in 1951 (the result appeared in a journal later in 1953). It is interesting to note that a similar result was discussed by Turing in his original 1936 paper about undecidability.
In essence, what Rice's theorem says is that if we want to know something about the result of a program, there's no silver bullet to figure this out just by reading the source code.