CMSC 28000 — Lecture 22

Universality

So we saw some examples of decidable languages. Now, we'll tackle the notion of undecidability. The notion of algorithmically unsolvable problem poses a problem in practical terms (and philosophically as well). To demonstrate this, we show that the following language is undecidable. $$A_{TM} = \{ \langle M,w \rangle \mid \text{$M$ is a Turing machine and $M$ accepts $w$} \}$$

This is the membership problem for Turing machines.

Theorem 22.1. $A_{TM}$ is undecidable.

It's important to note here that while $A_{TM}$ is not decidable, it is recognizable. The first consequence of this fact is that the recognizable languages are a larger and more powerful set of languages than the decidable languages. Secondly, this means we can construct a Turing machine that simulates a given Turing machine.

We can define a universal Turing machine $U$. We've played around with this idea before. The idea is that we can encode a Turing machine as a string via some appropriate encoding. It is worth pausing a bit to consider the philosophical implications of what it is we're doing. In particular, we're making a number of assumptions that we sort of take for granted as computer scientists.

The first is that we can encode Turing machines as strings. Of course, we've encountered the notion of encoding objects as strings before. However, in this case, we can think of this as a sort of formal way of doing what we've been doing all along: writing programs. And just as we can treat programs we write as text files, we treat the Turing machines as strings.

And what do we do with programs that we treat as text? We usually run them through a compiler that transforms our human-readable code into machine code, which is then run on a computer. There are tons of details in the process which we sort of abstract nowadays, but this is not unlike the notion of some Turing machine taking as input the encoding of another Turing machine and transforming it into something that can be simulated.

The final thing to note here is the idea of the universal Turing machine. We've studied a number of problems where we're essentially simulating other models of computation, but the idea of a universal Turing machine acts very much like our real electronic computers do. And each of our computers has various differences, but via encodings and the power of being able to decode these encodings allows us to simply write programs and have them work on every computer.

Let's move on to describing a universal Turing machine $U$. On input $\langle M,w \rangle$, where $M$ is a Turing machine and $w$ is a string, $U$ operates as follows:

1. Simulate $M$ on input $w$.
2. If $M$ enters the accept state, accept; if $M$ ever enters the reject state, reject.

Note that because $U$ simulates another Turing machine, $U$ will loop forever if $M$ never enters the acecpt or reject state. Of course, this is a rather unsatisfying description of a very important concept, so let's take a closer look at the implementation.

Our universal Turing machine uses three tapes:

1. A tape containing the description of the Turing machine $M$ to be simulated.
2. A simulation of the work tape of $M$.
3. The current state of $M$.

From this, it should not be difficult to see how the machine works. The simulation of the work tape is straightforward, so it remains to see how the simulation of the finite state portion of $M$ is simulated. This is taken care of by scanning the description of $M$ in the first tape. Since the current state is kept track of on the third tape, the machine only needs to scan the transitions in the description of $M$ on the first tape to determine which transition to take.

Uncountability and diagonalization

Now, we move on to the technique that we'll use to show that $A_{TM}$ is undecidable. The crux of the idea has to do with the number of languages that exist compared to the number of Turing machines there are.

This will take us back to some mathematics in the late 19th century involving the sizes of sets. Specifically, we'll be dealing with the size of infnite sets. Georg Cantor was interested in the question of how to compare the sizes of two infinite sets. For instance, if we had the set of natural numbers and the set of all even numbers, what can we say about their sizes? Cantor's solution to this was to show that two sets have the same size if you could pair every element of one set with the other.

Definition 22.2. Let $A$ and $B$ be two sets and consider a function $f:A \to B$. We say $f$ is one-to-one or injective if $f(a) \neq f(b)$ whenever $a \neq b$. We say $f$ is onto or surjective if for every $b \in B$, there exists $a \in A$ such that $f(a) = b$. A function that is both one-to-one and onto is a correspondence or bijection.

Definition 22.3. We say a set $A$ is countable if either it is finite or has the same size as $\mathbb N$.

Example 22.4. Going back to our question of the even numbers, it turns out the size of $\mathbb N$ and $2 \mathbb N$ are the same size, since $f(n) = 2n$ is a bijection from $\mathbb N$ to $2 \mathbb N$. Furthermore, this shows us that the set of even numbers is countable.

Of course, there are more interesting sets that we can consider. For instance, the set of rational numbers $$ \mathbb Q = \left\{\frac m n \mid m,n \in \mathbb N\right\}$$ is also countable. In other words, we can show that there is a correspondence between $\mathbb N$ and $\mathbb Q$.

Theorem 22.5. $\mathbb Q$ is countable.

Proof. What we want to do to show that $\mathbb Q$ is countable is to give a way to enumerate the elements of $\mathbb Q$. First, observe that we can list all of the elements of $\mathbb Q$ by constructing a table, where $\frac i j$ is in the $i$th row and the $j$th column:

However, we have to be a bit careful in how we enumerate the elements. We can't just go row by row, since each row is infinitely long and we won't ever reach the end of a row and go on to the next. What we do instead is enumerate along each diagonal from the top left-hand corner. We must also be careful to skip any elements that have already been accounted for, such as $\frac 2 2, \frac 3 3, \dots$. Then we will encounter every element of $\mathbb Q$ by following this process. $$\tag*{$\Box$}$$

Now after seeing this, we might expect that we can do this with any infinite set if we try hard enough to come up with a correspondence. As it turns out, this is not the case and there are infinite sets that are larger than $\mathbb N$. Such a set is said to be uncountable.

Theorem 22.6. $\mathbb R$ is uncountable.

Proof. We will show this by contradiction. We assume that we have some appropriate bijection $f:\mathbb N \to \mathbb R$. Then, we begin listing all of the numbers.

We claim that we can find a real number that cannot be in this correspondence. To do this, we define our number by setting its $i$th decimal place to be a number different from the $i$th decimal place of $f(i)$. So according to our example, our number can begin as 1.234168$\dots$. But according to this definition, our number can't be on the list that we've enumerated. Suppose that our number corresponds to some $t \in \mathbb N$. According to our definition, the $t$th digit of our number must differ from the $t$th digit of $f(t)$, which is a contradiction. Thus, our number is not enumerated and doesn't exist in our mapping and thus, the mapping is not a bijection. $$\tag*{$\Box$}$$

Undecidability

First, we'll use the same idea to show that undecdiable languages exist. The idea is that there are only countably many Turing machines but uncountably many languages. Thus, at least some of them have to be unrecognizable.

Theorem 22.7. Some languages are not Turing-recognizable.

Proof. First we need to show that the set of Turing machines is countable. We note that the set of all string $\Sigma^*$ is countable. Clearly, we can systematically enumerate them in lexicographic order.

Then we observe that every Turing machine has a string encoding $\langle M \rangle$. Now, not every string corresponds to a proper encoding of a Turing machine, but we can ignore all of those. Thus, there are countably many Turing machines.

Now, we show that the set of all languages is uncountable. To do so, we show that the set of all infinite binary sequences is uncountable. An infinite binary sequence is an infinitely long sequence of 0s and 1s. Let $\mathcal B$ be the set of all infinite binary sequences. We use diagonalization to show that $\mathcal B$ is uncountable.

Suppose we have a correspondence $f : \mathbb N \to \mathcal B$. Then we construct an infinite binary sequence $\overline b = b_1 b_2 \cdots$ by specifying that $b_i$ is a 0 if the $i$th digit of $f(i)$ is 1 and 1 if the $i$th digit of $f(i)$ is 0. Then, $\overline b$ is clearly not in the correspondence so we have a contradiction and $\mathcal B$ is uncountable.

Now, let $\mathcal L$ be the set of all languages over $\Sigma$. We show that there is a correspondence $f : \mathcal L \to \mathcal B$. Let $s_1, s_2, \dots$ be a sequence of words in $\Sigma^*$ in lexicographic order. We show that every language $A \in \mathcal L$ corresponds to a unique sequence in $\mathcal B$. We define $f(A)$ as the sequence in $\mathcal B$ where the $i$th bit is 1 if $s_i \in A$. We call this sequence the characterstic sequence of $A$.

This correspondence establishes the uncountability of the set of all languages $\mathcal L$. Thus, we cannot establish a correspondence between $\mathcal L$ and the set of all Turing machines, which means there must exist some language that is not recognized by a Turing machine. $$\tag*{$\Box$}$$

Just to refresh our memory, $A_{TM}$ is defined $$ A_{TM} = \{ \langle M,w \rangle \mid \text{$M$ is a TM and $M$ accepts $w$} \} $$ and we are ready to prove the following result.

Theorem 22.8. $A_{TM}$ is undecidable.

Proof. We assume that $A_{TM}$ is decidable and end up showing that it isn't. Suppose we have a TM $H$ that decides $A_{TM}$. Then on $\langle M,w \rangle$, $H$ halts and accepts if $M$ accepts $w$ and it rejects if $M$ does not accept $w$.

We construct a new TM $D$ that takes as input the description of a Turing machine and operates as follows:

1. On input $\langle M \rangle$, where $M$ is a TM, run $H$ on input $\langle M, \langle M \rangle \rangle$.
2. If $H$ accepts, then reject; if $H$ rejects, then accept.

Let's consider the result of running each Turing machine on a string of encodings of Turing machines. Suppose we have an enumeration of Turing machines $M_1, M_2, \dots$ and the following table tells us whether or not each machine accepts the encoding of some other machine, including itself. Now, let's consider the result of $D$ when run on a description of one of these machines: it is basically the opposite of whatever runs along the diagonal. When presented this way, the diagonal argument becomes clear.

Now, let us consider the result of $D$ when run on the input string $\langle D \rangle$. $D$ must accept if $D$ does not accept $\langle D \rangle$ and it must reject if $D$ accepts $\langle D \rangle$, which is a contradiction. Thus, neither Turing machines $D$ or $H$ can exist and $A_{TM}$ is undecidable. $$\tag*{$\Box$}$$