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 ATM, 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 😿😿😿.


ATM Is Undecidable

We define a language called ATM which is the Turing machine version of ADFA and ACFG

ATM = {<M,w> | M is a Turing machine and M accepts the string w}

Claim: Unlike ADFA and ACFG, however, ATM 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 ATM 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 ATM is decidable, then these are the only two possibilities for its decider A. For instance, here's that table on six arbitrary Turing machines M1 ... M6

<M1>

<M2>

<M3>

<M4>

<M5>

<M6>

...

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 ith column should be the opposite of the ith diagonal entry of the table. Let's try to do this:

<M1>

<M2>

<M3>

<M4>

<M5>

<M6>

...

<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 ATM is decidable. Therefore, ATM 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 ATM! 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 ATM 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 ATM 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.


HaltTM Is Undecidable

We can now talk about the problem that everyone mentions as the canonical undecidable problem: the halting problem:

HaltTM = {<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 ATM is easier to use as the canonical undecidable problem, but it doesn't matter, because it's relatively straightforward to reduce ATM 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 HaltTM is undecidable. We'll use ATM as problem A and HaltTM as problem B. If we assume by contradiction that HaltTM is decidable, then there must exist a decider machine H for this problem. We can use H to define the following machine to decide ATM

This is, of course, a contradiction, since we know that ATM is undecidable. Therefore, our assumption that HaltTM is decidable is false, so HaltTM must be undecidable.


ETM 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 ETM, which is the Turing machine equivalent of EDFA and ECFG

ETM = {<M> | M is a Turing machine that does not accept anything}

Claim: ETM is undecidable

Proof: We'll follow the same strategy by assuming by contradiction that ETM is decidable. Let's say we have a decider machine E for this language, which we'll use to create a machine to decide ATM. 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 ATM by using ETM's decider E

Since we know that ATM is undecidable, we've reached a contradiction, and ETM 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 ETM can decide whether any machine is empty. And this was enough for us to complete the proof by contradiction.


RegTM 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 Church-Turing 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

RegTM = {<M> | M is a Turing machine and the language L(M) generated by M can be recognized by a DFA}

Claim: RegTM is undecidable

Proof: As per procedure, we'll assume by contradiction that RegTM is decidable and use it to create a decider for ATM. Let's assume a decider for RegTM is called R. We'll use a similar trick to the one we used for ETM and design an auxiliary machine that we'll eventually feed to RegTM

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 ATM by using RegTM's decider R on RegIndicator_M_w

We know ATM is undecidable, so we've reached a contradiction, and RegTM must be undecidable as well.


TwoWriteTM Is Undecidable

Let's consider one more language for good measure. Suppose we have a 2-tape turing machine. Then we claim the language

TwoWriteTM = {<M,w> | M is a 2-tape Turing machine that writes a non-blank symbol to its second tape while processing w}

is undecidable

Proof: We can create a fairly straightforward decider for ATM if we assume by contradiction that TwoWriteTM 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 non-blank symbol on the second tape if and only if M accepts w. Written out in pseudocode, we have:

Used to decide ATM, we then have

Hence, TwoWriteTM 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

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

  2. This property applies to the language associated to Turing machines, not to specific implementation details of Turing machines; that is, if the language L(M1) associated to machine M1 fulfills this property (and hence <M1> ∈ P), then M2 satisfies this property (<M2> ∈ P) if and only if L(M1) = L(M2).

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 ETM and RegTM, but Rice's theorem does not apply to TwoWriteTM, 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 ETM and RegTM.

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 ATM. 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 MP be a decider for our assumed decidable language P. Then the following machine decides ATM

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, Mp accepts P_M_w if and only if M accepts w. Therefore, we have created a decider for ATM, 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, RegTM creates an auxiliary machine that acts like DFA if M accepts w, but which otherwise acts like a CFG, which is not in RegTM. 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.


Co-Recognizable And Unrecognizable Languages

There's one more thing worth mentioning about undecidable languages: they don't play nicely with complements.

A language is called co-recognizable if its complement is recognizable. We can prove the following theorem about decidable languages:

Theorem: Recognizable/Co-Recognizable Languages

A language is decidable if and only if it is both Turing recognizable and Turing co-recognizable.

Proof: Let's prove the first direction: that if a language is decidable, then it is recognizable and co-recognizable. 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 co-recognizable, 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 co-recognizable, then it is decidable. In this case, we can assume that we have machines ML and MC that recognize a language and its complement, respectively. So we'll run ML and MC in parallel. If ML accepts, then we accept. If MC 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 ATM Is Not Even Recognizable

Proof: Suppose by contradiction that the complement of ATM is recognizable. Then both ATM and its complement are recognizable, so by the above theorem, ATM must be decidable. But the very first thing we talked about in these notes is that ATM is not decidable. Therefore, the complement of ATM must not even be recognizable! This completes the proof.

But wait, you may be saying! I can create a recognizer for the complement of ATM using a recognizer A for ATM as follows

Doesn't this recognize the complement of ATM? 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 ATM is not recognizable (but again, we need the rigorous proof above to rule out all ways of being clever).