We'll be looking 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.
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 fairly labourious to show that a problem is undecidable by setting up a diagonalization argument every time. Instead, we want to be able to 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_{TM}$ was undecidable. We will continue to use this same strategy. We can go and ask the same questions of TMs as we've been asking about DFAs and CFGs. As you'd probably expect, they are all undecidable. Let's consider the following language \[ E_{TM} = \{ \langle M \rangle \mid \text{$M$ is a TM and $L(M) = \emptyset$} \}. \]
$E_{TM}$ is undecidable.
First, we construct a machine $M_w$ that 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$. Thus, $M_w$ recognizes the empty language if and only if it doesn't accept $w$.
Now, we assume that there exists a TM $R$ that decides $E_{TM}$ and construct a TM $S$ that decides $A_{TM}$ as follows:
Thus, if $R$ decides $E_{TM}$, then $S$ decides $A_{TM}$. However, we know that $A_{TM}$ is undecidable, so $R$ cannot exist and $E_{TM}$ is undecidable.
Now, let's consider the problem of equality between two TMs, specified as \[EQ_{TM} = \{ \langle M_1, M_2 \rangle \mid \text{$M_1,M_2$ are TMs and $L(M_1) = L(M_2)$} \}.\]
$EQ_{TM}$ is undecidable.
This time, we reduce from $E_{TM}$. Suppose we have a TM $R$ that decides $EQ_{TM}$. Then we can construct the following TM to decide $E_{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_{TM}$.
Here's another kind of question we can ask of Turing machines, since they are so powerful. We can 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 \[ REG_{TM} = \{ \langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language} \}.\] Or as it turns out, we can't ask that question because it is undecidable.
$REG_{TM}$ is undecidable.
Let $R$ be a TM that decides $REG_{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 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_{TM}$.
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 $\langle M \rangle$, where $M$ has property $P$. A semantic property $P$ is said to be non-trivial if there exists a TM $M_1$ such that $\langle M_1 \rangle \in P$ and a TM $M_2$ such that $\langle M_2 \rangle \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 assume that $P$ is a decidable language that satisfies some property and we let $R_P$ be a TM that decides $P$. We will reduce TM membership to property testing.
Let $T_\emptyset$ be a TM that always rejects, so $L(T_\emptyset) = \emptyset$. Without loss of generality, we assume that $\langle T_\emptyset \rangle \not\in P$, since otherwise, we can just use $\overline P$ instead. Since $P$ is non-trivial, there exists a TM $T$ with $\langle T \rangle \in P$.
We construct a Turing machine that decides $A_{TM}$ by being able to distinguish between $T_\emptyset$ and $T$.
So $M_w$ simulates $T$ if $M$ accepts $w$. Then $L(M_w) = L(T)$ if $M$ accepts $w$ and $L(M_w) = \emptyset$ otherwise. Thus, $\langle M_w \rangle \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.