9.1 A Language That Is Not Recursively Enumerable

Recall that a language L is recursively enumerable, (abbreviated RE) if L - L(M) for some TM M. Also, we shall in Section 9.2 introduce recursive or decidable languages that are not only recursively enumerable, but are accepted by a TM that always halts, regardless of whether or not it accepts.

Our long-range goal is to prove undecidable the language consisting of pairs (M,w) snch that:

1. M is a Turing machine (suitably coded, in binary) with input alphabet {0,1},

2. w is a string of Os and Is, and

3. M accepts input w.

If this problem with inputs restricted to the binary alphabet is undecidable, then surely the more general problem, where TMs may have any alphabet, is undecidable.

Our first step is to set this question up as a true question about membership in a particular language. Thus, we must give a coding for Turing machines that uses only Os and Is, regardless of how many states the TM has. Once we have this coding, we can treat any binary struig as if it were a Turing machine. If the string is not a well-formed representation of some TM, we may think of it as representing a TM with no moves. Thus, we may think of every binary string as some TM.

An intermediate goal, and the subject of this section. Involves the language Ld, the diagonalization language, which consists of all those strings w such tiiat the TM represented by ui does not accept the input w. We shall show that Ld has no Turing machine at all that accepts it. Remember that showing there is no Turing machine at all for a language is showing something stronger than that the language is undecidable (i.e., that it has no algorithm, or TM that always halts).

The language plays a role analogous to the hypothetical program H2 of Section 8.1.2, which prints hello, world whenever its input does Tjoi print hello, world when given itself as input. More precisely, just as Щ cannot

Does this Turing machine accept this input?

Then, we exploit this undecidabiiity result to exhibit a number of other undecidable problems. For instance, we show that all nontrivial problems about the language accepted by a Turing machine are undecidable, as are a number of problems that have nothing at all to do with Turing machines, programs, or computers.

9.1. А LANGUAGE THAT IS NOT RECURSIVELY ENUMERABLE 369

exist because its response when given itself as input is paradoxical, L cannot be accepted by a Turing machine, because if it were, then that Turing machine would have to disagree with itself when given a code for itself as input.

9.1.1 Enumerating the Binary Strings

In what follows, we shall need to assign integers to all the binary strings so that each string corresponds to one integer, and eacli integer corresponds to one string. If Ш is a binary string, treat Iw as a binary integer i. Then we shall call w the ith string. That is, с is the first string, 0 is the second, 1 the third, 00 the fourth, 01 the fifth, and so on. Equivalently, strings are ordered by length, and strings of equal length are ordered lexicographically. Hereafter, we shall refer to the ith string as Wi.

9.1.2 Codes for Turing Machines

Our next goal is to devise a binary code for Turing machines so that each TM with input alphabet {0,1} may be thought of as a binary string. Since we just saw how to enumerate the binary strings, we shall then have an identification of the Turing machines with the integers, and we can talk about the ith Turing machine, M,. To represent a TM M (Q, {0,1}, Г, J, gi, Б,Е) as a binary string, we must first assign integers to the states, tape symbols, and directions L and R.

We shall assume the states are qi,q2, - ,Qt for some r. The start state will always be qi, and 2 will be the only accepting state. Note that, since we may assume the TM halts whenever it enters an accepting state, there is never any need for more than one accepting state.

We shall assume the tape symbols are XXi, iXg for some s. Xi always will be the symbol 0, X2 wiU be 1, and X3 will be B, the blank. However, other tape symbols can be assigned to the remaining integers arbitrarily.

We shall refer to direction L as Di and direction R as D2-

Since each TM M can have integers assigned to its states and tape synibols in many different orders, there will be more than one encoding of the typical TM. However, that fact is unimportant in what follows, since we shall show that no encoding can represent a TM M such that L{M] - Ld-

Once we have established an integer to represent each state, symbol, and direction, we can encode the transition function 5. Suppose one transition rule is S{qi,Xj) - {qk,Xi,Dm), for some integers г, j, k, /, and m. We shall code this rule by the string ОиОЮЮЮ . Notice that, since all oft, j, k, /, and m are at least one, there are no occurrences of two or more consecutive Is within the code for a single transition.

A code for the entire TM M consists of all the codes for the transitions, in some order, separated by pairs of Is:

where each of the Cs is the code for one transition of M. Example 9.1: Let the TM in question be

M = {{диЯ2.Яз},{0Л}ЛОА,В},5,диВ,{д2}) where S consists of the rules:

(дь1) = (<?з.0,Д) Siq3,0) = (quhR) 5(93,1)-(92,0,Д)

5(93,£f) = (93,l,L)

The codes for each of these rules, respectively, are:

0100100010100 0001010100100 00010010010100 0001000100010010

For example, the first rule can be written as 6{qi,X2) = {дз,Хт,D2), since 1 X2, 0 Xi, and R = D2. Thus, its code is 040101040, as was indicated above. A code for M is:

OlOOlOOOlOlOOllOOOlOlOlOOlOOllOOOlOOlOOlOlOOllOOOlOOOlOOOlOOlO

Note that there are many other possible codes for M. In particular, the codes for the four transitions may be fisted in any of 4! orders, giving us 24 codes for M. □

In Section 9.2.3, we shall have need to code pairs consisting of a TM and a string, {M,w). For this pair we use the code for M followed by 111, followed by w. Note that, since no vafid code for a TM contains three Is in a row, we can be sure that the first occurrence of 111 separates the code for M from w. For instance, if M were the TM of Example 9.1, and w were 1011, then the code for {M,w) would be the string shown at the end of Example 9.1 followed by 1111011.

9.1.3 The Diagonalization Language

In Section 9.1.2 we coded Turing machines so there is now a concrete notion of Mu the ith Turing machine : that TM M whose code is lOj, the ith binary string. Many integers do not correspond to any TM at all. For instance, 11001