9.1. А LANGUAGE THAT IS NOT RECURSrVELY ENUMERABLE 371

does not begin with 0, and 0010111010010100 is not valid because it has three consecutive Is. If Wi is not a valid TM code, we shall take Mi to be the TM with one state and no transitions. That is, for these values of г, Mj is a Turing machine that immediately halts on any input. Thus, L{Mi) is 0 if Wi fails to be a valid TM code.

Now, we can make a vital definition.

The language L, the diagonalization language, is the set of strings Wj such that Wi is not in L(Mj).

That is, Ld consists of all strings w such that the TM M whose code is w does not accept when given w as input.

The reason Ld is called a diagonalization language can be seen if we consider Fig. 9.1. This table tells for all i and j, whether the TM Mi accepts input struig Wj; 1 means yes it does and 0 means no it doesnt. We may think of the ith row as the characteristic vector for the language L(Mj); that is, the Is in this row indicate the strings that are members of this language.

Diagonal

Figure 9.1: The table that represents acceptance of strings by Turing machines

The diagonal values teU whether Mi accepts Wi. To construct Ld, we complement the diagonal. For instance, if Fig. 9.1 were the correct table, then the complemented diagonal would begin 1,0,0,0,... . Thus, L would contain wi = e, not contain W2 tlrrough W4, which are 0, 1, and 00, and so on.

The trick of complementing the diagonal to construct the cliaracteristic vector of a language that cannot be the language that appears in any row, is called diagonalization. It works because the complement of the diagonal is itself a characteristic vector describing membership in some language, namely

You should note that the actual table does not look anything like the one suggested by the figure. Since all low integers fail to represent a valid TM code, and thus represent the trivial TM that makes no moves, the top rows of the table are in fact solid Os.

La- This characteristic vector disagrees in some column with every row of the table suggested by Fig. 9.1. Thus, the complement of the diagonal cannot be the characteristic vector of any Turing machine.

9.1.4 Proof that Ld is not Recursively Enumerable

Following the above intuition about characteristic vectors and the diagonal, we shall now prove formally a fundamental result about Turing machines: there is no Turing machine that accepts the language Ld.

Theorem 9.2: Ld is not a recursively enumerable language. That is, there is no Turing machine that accepts L.

PROOF: Suppose Ld were L{M) for some TM M. Since L is a language over alphabet {0,1}, M would be in the list of Turing machines we have constructed, since it includes all TMs with input alphabet {0,1}. Thus, there is at least one code for M, say i; that is, M - Mi. Now, asic if Wi is in Ld-

liwi is in then Mi accepts Wj. But then, by definition of i, Wi is not in Ld, because Lj contains only those Wj such that Mj does not accept Щ-

Similarly, if Wi is not in Ld, then Mi does not accept Wi, Thus, by definition of Ld, Wi is in Ld.

Since Wi can neither be in L nor fail to be in Ld, we conclude that there is a contradiction of our assumption that M exists. That is, Ld is not a recursively enumerable language. □

9.1.5 Exercises for Section 9.1 Exercise 9.1.1; What strings are:

* a) W3jf b) wioo?

Exercise 9.1.2; Write one of the possible codes for the Turing machine of Fig. 8.9.

! Exercise 9.1.3: Here are two definitions of languages that are similar to the definition of Lj, yet different from that language. For each, show that the language is not accepted by a Turing machine, using a diagonalization-type argument. Note that you cannot develop an argument based on the diagonal itself, but must find another infinite sequence of points in the matrix suggested by Fig. 9.1.

* a) The set of all Wi such that Wi is not accepted by Мг,-.

b) The set of all Wi such that W2i is not accepted by Mi.

! Exercise 9.1.4: We have considered only Turing machines that have input alphabet {0,1}. Suppose that we wanted to assign an integer to all Turing machines, regardless of theu* input alphabet. That is not quite possible because, while the names of the states or noninput tape symbols are arbitrary, the particular input symbols matter. For instance, the languages {0 1 \ n> 1} and {o & I > 1}, while similar in some sense, are not the same language, and they are accepted by different TMs. However, suppose that we have an infinite set of symbols, {ui, a2, } from which all TM input alphabets are chosen. Show how we could assign an integer to all TMs that had a finite subset of these symbols as its input alphabet,

9.2 An Undecidable Problem That is RE

Now, we have seen a problem - the diagonalization language L - that has no Turing machine to accept it. Our next goal is to refine the structure of the recursively ermmerable (RE) languages (those that are accepted by TMs) into two classes. One class, which corresponds to what we commonly think of as an algorithm, has a TM that not only recognizes the language, but it tells us when it has decided the input string is not in the language. Such a Turing machine always halts eventually, regardless of whether or not it reaches an accepting state.

The second class of languages consists of those RE languages that are not accepted by any Turing machine with the guarantee of halting. These languages are accepted in an inconvenient way: if the input is in the language, well eventually know that, but if the input is not in the language, then the Turing machine may run forever, and we shall never be sure the input wont be accepted eventually. An example of this type of language, as we shall see, is the set of coded pairs (M,w) such that TM M accepts input w.

9.2.1 Recursive Languages

We call a language L recursive if L - L{M) for some Turing machine M such that:

1. If Ш is in L, then M accepts (and therefore halts).

2. If го is not in L, then M eventually halts, although it never enters an accepting state.

A TM of this type corresponds to our informal notion of an algorithm, a well-defined sequence of steps that always finishes and produces an answer. If we think of the language L as a problem, as will be the case frequently, then problem L is called decidable if it is a recursive language, and it is called undecidable if it is not a recursive language.