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 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$. 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_{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.
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 \[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}$.
Now we'll formalize the notion of reducibility and reduction. First, we'll need to revisit the notion of Turing machines and functions.
While our basic definition of a Turing machine is a language recognition device, we can modify it so that it becomes a computing device, which seems very relevant and practical. Instead of having accept and reject states, we define our machine to have a single halting state. Then we have the following notion.
A function $f: \Sigma^* \to \Sigma^*$ is a computable function if some Turing machine $M$, on every input $w$, halts with only $f(w)$ left on its tape.
As usual, there are multiple equivalent definitions for the specifics here. For instance, the choice of input alphabet is up to us, so if we want to compute, say, integer functions, then we can take our input and output to be unary or binary or something else. This means that a machine computing the function $f(n) = 2n$ can be implemented as a machine that takes $1^n$ as input and computes $1^{2n}$ in unary, or it could be something that does it in binary, like $(n)_2 \mapsto (n)_2 0 = (2n)_2$.
This notion is useful for a few things. First, it gives a very obvious way for us to connect Turing machines with the concept of recursive functions. Secondly, it gives us a way to think about data transformation. Thirdly, we'll be using it in the formal definition of reducibility, and it shows up again for various definitions in complexity theory.
But is this machine equivalent to our basic model? Sure, it's not hard to see that we can designate something like an output tape for our output to appear on and then we just hit the accept state once we're done computing our function. Similarly, we can always "simulate" the notion of accept and reject states; after all, languages are just decision problems, which are just functions from $\Sigma^*$ to $\{0,1\}$, so we output a 1 for accept and output a 0 for reject.
For our current purposes, we are more interested in transforming various kinds of input strings into other input strings. For instance, we can take as input some description of a Turing machine $\langle M \rangle$ and transform it into some other machine $\langle M' \rangle$. This is something that we've been implicitly doing when we assume that various machines can be constructed.
A language $A$ is reducible to a language $B$, denoted $A \leq B$, if there is a computable function $f:\Sigma^* \to \Sigma^*$, where for every $w$, $$ w \in A \iff f(w) \in B.$$ The function $f$ is called the reduction from $A$ to $B$. The reduction is a formal way of specifying a transformation of an input string for a particular problem to an input string for some other problem.
Let's consider the proof that $HALT_{TM}$ is undecidable. To show an explicit reduction, we need to show that there exists a computable function $f$ that transforms strings $\langle M,w \rangle$ into strings $\langle M',w' \rangle$ where $$ \langle M,w \rangle \in A_{TM} \iff \langle M',w' \rangle \in HALT_{TM}.$$ To do this, we simply show that there is a TM that computes an appropriate function $f$:
We can conclude that the proofs we've done so far are eamples of reduction. However, there is one hitch. If we look at the proof that $E_{TM}$ is undecidable closely, we see that it deviates from our definition a bit: notice that our TM for $A_{TM}$ accepted whenever $E_{TM}$ rejected our machine. This means that what we actually showed was $A_{TM} \leq \overline{E_{TM}}$, or rather non-emptiness for Turing machines. This is fine, since this still implies that $E_{TM}$ is undecidable, but there are some consequences from what our reductions tell us. First, we have the following observations.
Let $A$ and $B$ be languages.
These are natural consequences of the reduction relation and tells us something about the relative hardness of problems $A$ and $B$. Next, we observe that $\overline{E_{TM}}$ is what we say is a co-recognizable language.
We say that a language is co-recognizable if it is the complement of a recognizable language.
A language is decidable if and only if it is recognizable and co-recognizable.
If $A$ is decidable, then $A$ and $\overline A$ are recognizable, since a decidable language and its complement are recognizable.
If $A$ and $\overline A$ are recognizable, then there exist Turing machines $M_1$ and $M_2$ that recognize $A$ and $\overline A$, respectively. Then we can construct a Turing machine $M_3$ that on input $w$ operates as follows:
Since $A \cup \overline A = \Sigma^*$, we have that either of $M_1$ or $M_2$ must accept, which means that $M_3$ is guaranteed to halt. This means that $A$ is decidable.
Note that the TM $M_3$ that we constructed is a deterministic machine and uses a neat trick to avoid falling down a non-halting rabbit hole, which is the danger whenever you're dealing with recognizable languages. We simply bound the computation and systematically lengthen the bound until we get an answer, which we are guaranteed to do since every input must belong to one of the two languages. But if we used a nondeterministic machine, the construction would be even easier: just run the two machines in parallel until one accepts.
This result gives us a clear example of an unrecognizable language.
$\overline{A_{TM}}$ is not recognizable.
If $\overline{A_{TM}}$ were recognizable, then $A_{TM}$ would be decidable.
But from this, we can also get that $E_{TM}$ is also unrecognizable. First, we can conclude that our reduction from $A_{TM}$ doesn't reduce to $E_{TM}$.
$A_{TM}$ is not reducible to $E_{TM}$.
Suppose that we do have a reduction $f$ such that $A_{TM} \leq E_{TM}$. Then this means that by definition we have $\overline{A_{TM}} \leq \overline{E_{TM}}$ from the same reduction $f$. However, $\overline{E_{TM}}$ is recognizable but $\overline{A_{TM}}$ is unrecognizable.
Now, note that this says nothing about whether or not $E_{TM}$ or $\overline{E_{TM}}$ are recognizable or unrecognizable. It could be that one of them are recognizable (which means the other isn't) or both could be unrecognizable. The answer turns out to be the first.
$\overline{E_TM}$ is recognizable.
Recall that $\overline{E_{TM}}$ is the language of Turing machines that accept at least one word. Therefore, all we need to do is enumerate every word and check if $M$ accepts it. There is a slight problem with this: what if we encounter a word that makes $M$ run forever? Then we can never move on to the next word. So we need to be a bit more clever.
We define a Turing machine that does the following:
If no word is accepted by $M$, this machine will run forever. If there is a word $w \in L(M)$, then $w$ must be of finite length $n$ and is accepted within a finite number of steps $t$. This means that the machine will detect that $w$ is accepted when $i = t$.
An alternative proof uses nondeterministic Turing machines: the NTM nondeterministically guesses a string $w$ and simulates $M$ on it. If $w$ is accepted, then this means at least one branch of computation on the NTM is an accepting branch and the word is accepted. Otherwise, none of the branches are accepting branches.
This clearly gives us the following.
$E_{TM}$ is unrecognizable.
Note that unrecognizability is even harder than undecidability. Recall that a language can be recognizable, but undecidable—these are problems that can be solved algorithmically, as long as we're not worried about getting a negative answer. But unrecognizability means that a problem doesn't even have that.
What is the difference between the two? If we examine each of our problems, membership and emptiness, and look at their complements, non-membership and non-emptiness, we get a hint. Membership and non-emptiness are really existential search problems: a search for an accepting computation path or a search for a string that will be accepted. But emptiness and non-membership are universal search problems: a search to ensure no strings are in the language or that there are no possible accepting computation paths. There's a bit of an analogue with problems in NP and co-NP, where one involves an existential search for a certificate while the other involves a universal search for certificates.
Back to the question of decision problems, 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 \[ REG_{TM} = \{ \langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language} \}.\] As it turns out, this is not decidable either.
$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}$.
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...