Week 12: Undecidability
Chris Tralie
It's now time to consider some languages that are not decidable. If a language L is not decidable, it means that while it may be possible to design a Turing machine to recognize L, we can't hope to avoid an infinite loop on all strings not in the language.
We'll start with a very specific example of an undecidable language known as A_{TM}, which we will use as the canonical undecidable language when proving that other languages are undecidable. It will be one very short step after this to prove that the ever famous Halting problem is undecidable, but that is just the tip of the iceberg of interesting problems we can't hope to solve in general, as we will see πΏπΏπΏ.
A_{TM} Is Undecidable
We define a language called A_{TM} which is the Turing machine version of A_{DFA} and A_{CFG}
A_{TM} = {<M,w>  M is a Turing machine and M accepts the string w}
Claim: Unlike A_{DFA} and A_{CFG}, however, A_{TM} is not decidable.
Proof: Intuitively, there's something about the fact that Turing machines can throw infinite loops that prevent us from being able to rule out a particular string from just taking a long time to accept/reject or from actually infinitely looping. But we need a more rigorous argument for this.
Suppose by contradiction that A_{TM} is actually decidable, and let a decider for it be a machine called A. Then we can use A as a subroutine to build another decidable universal Turing machine which I'll call weird (following Thorsten Altenkirch's convention). Below is a high level description of this machine, which feeds a string encoding of M to itself:
In other words, weird does the opposite of A on the string encoding of a machine and itself. Since A is assumed to be a decidable Turing machine, so is weird. But here's a diagonalization argument can run us into trouble. Since the set of all Turing machines is countable, we can arrange all possible Turing machines along the rows of a table in some order (such as the lexographic order of their string encoding). We'll then order their string encodings in the same order across the columns. In the entries of the table, let's record Accept or Reject to indicate whether the machine on the row accepts or rejects the string encoding of the machine on the column. Since we've assumed that A_{TM} is decidable, then these are the only two possibilities for its decider A. For instance, here's that table on six arbitrary Turing machines M_{1} ... M_{6}
<M_{1}> 
<M_{2}> 
<M_{3}> 
<M_{4}> 
<M_{5}> 
<M_{6}> 
...  
M1 
Accept 
Accept 
Accept 
Reject 
Accept 
Accept 
... 
M2 
Accept 
Accept 
Reject 
Accept 
Accept 
Accept 
... 
M3 
Accept 
Accept 
Accept 
Accept 
Accept 
Reject 
... 
M4 
Accept 
Reject 
Accept 
Reject 
Reject 
Reject 
... 
M5 
Accept 
Accept 
Accept 
Accept 
Reject 
Accept 
... 
M6 
Accept 
Accept 
Reject 
Accept 
Accept 
Accept 
... 
...  ...  ...  ...  ...  ...  ...  ... 
But we just argued a moment ago that weird is a valid Turing machine, so we should be able to have a row and column for weird and its string encoding <weird>, respectively, in our table. Since weird does the reverse behavior of A on a machine and its string encoding, the value of weird's row at the i^{th} column should be the opposite of the i^{th} diagonal entry of the table. Let's try to do this:
<M_{1}> 
<M_{2}> 
<M_{3}> 
<M_{4}> 
<M_{5}> 
<M_{6}> 
... 
<weird> 
...  
M1 
Accept 
Accept 
Accept 
Reject 
Accept 
Accept 
...  Reject 
... 
M2 
Accept 
Accept 
Reject 
Accept 
Accept 
Accept 
...  Reject 
... 
M3 
Accept 
Accept 
Accept 
Accept 
Accept 
Reject 
...  Reject 
... 
M4 
Accept 
Reject 
Accept 
Reject 
Reject 
Reject 
...  Accept 
... 
M5 
Accept 
Accept 
Accept 
Accept 
Reject 
Accept 
...  Reject 
... 
M6 
Accept 
Accept 
Reject 
Accept 
Accept 
Accept 
...  Accept 
... 
...  ...  ...  ...  ...  ...  ...  ...  ...  ... 
weird 
Reject 
Reject 
Reject 
Accept 
Accept 
Reject 
...  ππ???ππ 
... 
...  ...  ...  ...  ...  ...  ...  ...  ...  ... 
We start off just fine by having weird do the opposite on other machines. However, when we get to weird itself, we reach a contradiction, because we define its accept/reject status to be the opposite of what it is. But it's impossible to choose either accept or reject to be the opposite of itself. So we've arrived at a contradiction. The only falsifiable assumption we made this whole time is that A_{TM} is decidable. Therefore, A_{TM} must not be decidable!
Diagonalization Disclaimer!!
Most math students would be used to using a diagonalization argument to prove that certain sets are uncountably infinite. But that's not what we're showing with A_{TM}! Actually, as we discussed, the set of all strings in an alphabet is countably infinite, and every language is a subset of these strings, so every language must be countable, whether it's decidable or not. So even though A_{TM} is undecidable, it is still countably infinite! So don't make the mistake of assuming that undecidable languages are uncountable!
At the root of the confusion is exactly what we're assuming by contradiction before we apply the diagonal argument. When we prove that a set is uncountable, we assume by contradiction that it is countable, and then we find an inconsistency with the diagonal argument. By contrast, when we show that A_{TM} is undecidable, we are not assuming countability of the set of languages by contradiction, because that is already true! Instead, we're assuming by contradiction the existence of an oracle. So in this case, we use the contradiction with a diagonal argument to disprove the existence of an oracle.
Halt_{TM} Is Undecidable
We can now talk about the problem that everyone mentions as the canonical undecidable problem: the halting problem:
Halt_{TM} = {<M,w>  M is a Turing machine and M halts (either accepts or rejects, but does not loop) on the string w}
Personally, I think A_{TM} is easier to use as the canonical undecidable problem, but it doesn't matter, because it's relatively straightforward to reduce A_{TM} to the halting problem. We will use the following theorem to our advantage
Reduction Strategy for Proving Undecidability
If a problem A is undecidable, then we assume by contradiction that B is decidable and use a decider machine for problem B as a subroutine to solve problem A. If we ensure that everything other than B's decider takes decidable steps, then we reach the conclusion that A is decidable. But this is a contradiction, so our assumption that B was decidable must be false, proving that B is undecidable.
Let's use this strategy to prove that Halt_{TM} is undecidable. We'll use A_{TM} as problem A and Halt_{TM} as problem B. If we assume by contradiction that Halt_{TM} is decidable, then there must exist a decider machine H for this problem. We can use H to define the following machine to decide A_{TM}
This is, of course, a contradiction, since we know that A_{TM} is undecidable. Therefore, our assumption that Halt_{TM} is decidable is false, so Halt_{TM} must be undecidable.
E_{TM} Is Undecidable
A lot of times the halting problem is stated as the be all end all of undecidability. But there are (sadly) so many other useful problems that we cannot hope to solve in general. Let's now consider one called E_{TM}, which is the Turing machine equivalent of E_{DFA} and E_{CFG}
E_{TM} = {<M>  M is a Turing machine that does not accept anything}
Claim: E_{TM} is undecidable
Proof: We'll follow the same strategy by assuming by contradiction that E_{TM} is decidable. Let's say we have a decider machine E for this language, which we'll use to create a machine to decide A_{TM}. To do this, let's define a third machine that will help us:
This is kind of a weird trick, but we've defined a machine EmptyIndicator_M_w whose definition depends on a machine M and a string w, so the machine will actually change for a different M and w. But when we fix M and w, we see that the language L(EmptyIndicator_M_w) is empty if M does not accept w, or it consists of a single string "CS 373 Rocks" if M does accept w. Therefore, we can create a decider for A_{TM} by using E_{TM}'s decider E
Since we know that A_{TM} is undecidable, we've reached a contradiction, and E_{TM} must not be decidable.
The thing that's weird about this proof is that the machine EmptyIndicator_M_w does not have to be a decider for us to decide whether it's empty by our assumption; we assumed that E_{TM} can decide whether any machine is empty. And this was enough for us to complete the proof by contradiction.
Reg_{TM} Is Undecidable
There's another fact we might love to know about a Turing machine we have (or about a computer program that we have, as per the ChurchTuring Thesis): did we go way overkill but it can actually just be implemented as a DFA? This machine could have solved problem 5 on homework 6 with the "broken Turing machines," for example. For a more specific example, let's consider the following Turing machine:
This Turing machine decides the language of binary strings with at least one 0. But this can be implemented more simply by just using a DFA
Let's now state the language in question more formally
Reg_{TM} = {<M>  M is a Turing machine and the language L(M) generated by M can be recognized by a DFA}
Claim: Reg_{TM} is undecidable
Proof: As per procedure, we'll assume by contradiction that Reg_{TM} is decidable and use it to create a decider for A_{TM}. Let's assume a decider for Reg_{TM} is called R. We'll use a similar trick to the one we used for E_{TM} and design an auxiliary machine that we'll eventually feed to Reg_{TM}
When we fix M and w, we see that the language L(RegIndicator_M_w) happens to be regular if M accepts w, or it happens to be nonregular if M does not accept w. Therefore, we can create a decider for A_{TM} by using Reg_{TM}'s decider R on RegIndicator_M_w
We know A_{TM} is undecidable, so we've reached a contradiction, and Reg_{TM} must be undecidable as well.
TwoWrite_{TM} Is Undecidable
Let's consider one more language for good measure. Suppose we have a 2tape turing machine. Then we claim the language
TwoWrite_{TM} = {<M,w>  M is a 2tape Turing machine that writes a nonblank symbol to its second tape while processing w}
is undecidable
Proof: We can create a fairly straightforward decider for A_{TM} if we assume by contradiction that TwoWrite_{TM} is decidable. Let's create an auxiliary "wrapper machine" TwoWrite_Accept_M for any single tape turing machine M. This machine runs M on an input as normal, and if M accepts w, then it writes a single 1 on the second tape. Hence, this machine writes a nonblank symbol on the second tape if and only if M accepts w. Written out in pseudocode, we have:
Used to decide A_{TM}, we then have
Hence, TwoWrite_{TM} cannot be decidable.
Rice's Theorem
It may seem like we keep doing a similar thing for all of these problems, and we'd be able to save ourselves some work if we came up with a more general theorem for a class of undecidable languages that all have certain things in common. Here, we'll explore one such theorem known as Rice's Theorem.
Rice's Theorem
Let P be a language of Turing machine string encodings satisfying some property that meets two conditions

This property is nontrivial; there is at least one Turing machine that satisfies this property, but not all Turing machines satisfy this property.

This property applies to the language associated to Turing machines, not to specific implementation details of Turing machines; that is, if the language L(M_{1}) associated to machine M_{1} fulfills this property (and hence <M_{1}> ∈ P), then M_{2} satisfies this property (<M_{2}> ∈ P) if and only if L(M_{1}) = L(M_{2}).
Rice's theorem states that if P's property meets these two conditions, then P is an undecidable language.
Another way to understand Rice's theorem in the context of programming languages is that it is impossible to devise a decider for programs with a particular nontrivial semantic/behavioral property, ignoring the actual syntax of the programs that have this property. So we see, for example, that Rice's theorem applies to E_{TM} and Reg_{TM}, but Rice's theorem does not apply to TwoWrite_{TM}, since there are certainly ways to implement the same recognizer for a language without using a second tape, as we explained in the multitape to single tape reduction in class. Still, it could have saved us work on E_{TM} and Reg_{TM}.
Proof of Rice's Theorem: Let's assume the language P satisfying these two conditions is decidable. We have to somehow use the nontrivial and semantic properties of its language to create a decider for A_{TM}. Since it's nontrivial, we can assume there is at least one machine T whose encoding is in P, and at least one machine F whose encoding is not in P. Let's create the following auxiliary machine
Now let's let the machine M_{P} be a decider for our assumed decidable language P. Then the following machine decides A_{TM}
We've setup our auxiliary machine P_M_w to act like a machine in P if and only if M accepts w. Otherwise, it acts like a machine not in P. Therefore, M_{p} accepts P_M_w if and only if M accepts w. Therefore, we have created a decider for A_{TM}, which is a contradiction, showing that P is undecidable. This completes the proof.
We can see that some of the above examples use this logic directly. For instance, Reg_{TM} creates an auxiliary machine that acts like DFA if M accepts w, but which otherwise acts like a CFG, which is not in Reg_{TM}. But now we don't have to think so hard, and we just have to convince ourselves that there is at least one machine in the language and at least one machine not in the language, and that this property is a semantic property.
CoRecognizable And Unrecognizable Languages
There's one more thing worth mentioning about undecidable languages: they don't play nicely with complements.
A language is called corecognizable if its complement is recognizable. We can prove the following theorem about decidable languages:
Theorem: Recognizable/CoRecognizable Languages
A language is decidable if and only if it is both Turing recognizable and Turing corecognizable.
Proof: Let's prove the first direction: that if a language is decidable, then it is recognizable and corecognizable. We already know that if a language is decidable, then it's recognizable (since decidability is a stronger condition that rules out infinite loops). To show that it's also corecognizable, we simply flip the Accept/Reject states, which we can safely do because there are no infinite loops.
Let's now prove the other direction: that if a language is both recognizable and corecognizable, then it is decidable. In this case, we can assume that we have machines M_{L} and M_{C} that recognize a language and its complement, respectively. So we'll run M_{L} and M_{C} in parallel. If M_{L} accepts, then we accept. If M_{C} accepts, then we reject (since if a string is in the complement, it should not be in our language). Since these are both recognizers and they accept the opposite of each other, exactly one of them will accept eventually, even if the other loops infinitely. So we have a valid decider. This completes the proof.
This theorem tells us that complements play nicely with decidable languages, but they may not with undecidable languages.
The complement of A_{TM} Is Not Even Recognizable
Proof: Suppose by contradiction that the complement of A_{TM} is recognizable. Then both A_{TM} and its complement are recognizable, so by the above theorem, A_{TM} must be decidable. But the very first thing we talked about in these notes is that A_{TM} is not decidable. Therefore, the complement of A_{TM} must not even be recognizable! This completes the proof.
But wait, you may be saying! I can create a recognizer for the complement of A_{TM} using a recognizer A for A_{TM} as follows
Doesn't this recognize the complement of A_{TM}? Well, in order to recognize a language, we have to always be able to get to an accept state without infinitely looping. However, if A does not accept w, it may infinitely loop on it. So we might never get past the first if statement. This is intuitively why the complement of A_{TM} is not recognizable (but again, we need the rigorous proof above to rule out all ways of being clever).