L(M) is exactly L. Since M always halts, and L(M) = L, we conclude that L is recursive. □

We may summarize Theorems 9.3 and 9.4 as follows. Of the nine possible ways to place a language L and its complement L in the diagram of Fig. 9.2, only the following four are possible:

1. Both L and L are recursive; i.e., both are in the inner ring.

2. Neither L nor L is RE; i.e., both are in the outer ring.

3. L is RE but not recursive, and L is not RE; i.e., one is in the middle ring and the other is in the outer ring.

4. L is RE but not recursive, and L is not RE; i.e., the same as (3), but with L and L swapped.

In proof of the above. Theorem 9.3 eliminates the possibility that one language (L or L) is recursive and the other is in either of the other two classes. Theorem 9.4 eliminates the possibility that both are RE but not recursive.

Example 9,5: As an example, consider the language Lj, which we know is not RE. Thus, Lrf could not be recursive. It is, however, possible that could be either non-RE or REj-but-not-recursive, It is in fact the latter.

Ld is the set of strings Wi such that М,- accepts Wi. This language is similar to the universal language L consisting of all pairs {M, w) such that M accepts w, which we shall show in Section 9.2.3 is RE. The same argument can be used to show Ld is RE. □

9.2.3 The Universal Language

We already discussed informally in Section 8.6.2 how a Turing machine could be used to simulate a computer that had been loaded with an arbitrary program. That is to say, a single TM can be used as a stored program computer, taking its program as well as its data from one or more tapes on which input is placed. In this section, we shall repeat the idea with the additional formality that comes with talking about the Turing macliine as our representation of a stored program.

We define L , the universal language, to be the set of binary strings that encode, in the notation of Section 9.1.2, a pair {M,w), where M is a TM with the binary input alphabet, and ш is a string in (0+1)*, such that w is in L{M). That is, Lu is the set of strings representing a TM and an input accepted by that TM. We shall show that there is a TM U, often called the universal Turing machine, such that L - L{U). Since the input to f/ is a binary string, U is in fact some Mj in the list of binary-input Turing machines we developed in Section 9.1.2.

It is easiest to describe f7 as a multitape Turing macliine, in tlie spirit of Fig. 8.22. In the case of U, the transitions of M are stored initially on the first tape, along with the string w. A second tape will be used to hold the simulated tape of M, using tho same format as for the code of M. That is, tape symbol Xi of M will be represented by 0, and tape symbols will be separated by single Is. The third tape of U holds the state of M, with state qi represented by i Os. A sketch of U is in Fig, 9.5.

Input

Tape of M 0001OOOOO1010001

State of Л/ ООО *** QBB

Scratch

Figure 9.5: Organization of a universal Turing machine The operation of U can be summarized as follows:

1. Examine the input to make sure that the code for M is a legitimate code for some TM. If not, U halts without accepting. Since invalid codes are assumed to represent the TM with no moves, and such a TM accepts no inputs, this action is correct.

2. Initialize the second tape to contain the input w, in its encoded form. That is, for each 0 of w, place 10 on the second tape, and for each 1 of

place 100 there. Note that the blanks on the simulated tape of M, which are represented by 1000, will not actually appear on that tape; aU cells beyond those used for w will hold the blank of U. However, U knows that, should it look for a simulated symbol of M and find its own blank, it must replace that blank by the sequence 1000 to simulate the blank of M.

A More Efficient Universal TM

A efficient simulation of M by U, one that would not require us to shift symbols on the tape, would have U first determine the number of tape symbols M used. If there are between 2* + 1 and 2* symbols, U could use a fc-bit binary code to represent the different tape symbols uniquely. Tape cells of M could be simulated by к of f/s tape cells. To make things even easier, the given transitions of M could be rewritten by U to use the fixed-length binary code instead of the variable-length unary code we introduced.

3. Place 0, the start state of M, on the third tape, and move the head of Us second tape to the first simulated cell.

4. To simulate a move of M, U searches on its first tape for a transition ОиО-lOlOlO , such that 0* is the state on tape 3, and (P is the tape symbol of M that begins at the position on tape 2 scanned by U. This transition is the one M would next make. U shoiUd:

(a) Change the contents of tape 3 to 0*; that is, simulate the state change of M. To do so, и first changes all the Os on tape 3 to blanks, and then copies 0* from tape 1 to tape 3.

(b) Replace 0 on tape 2 by O; that is, change the tape symbol of M. If more or less space is needed (i.e., гф1), use the scratch tape and the shifting-over technique of Section 8,6.2 to manage the spacing.

(c) Move the head on tape 2 to the position of the next 1 to the left or right, respectively, depending on whether m = 1 (move left) or m - 2 (move right). Thus, U simulates the move of M to the left or to the right.

5. If M has no transition that matches the simulated state and tape symbol, then in (4), no transition will be found. Thus, M halts in the simulated configuration, and U must do likewise.

6. If M enters its accepting state, then U accepts.

In this manner, U simulates M anw. U accepts the coded pair (А/, w) if and only if M accepts tn.

9.2.4 Undecidability of the Universal Language

We can now exhibit a problem that is RE but not recursive; it is the language Lu- Knowing that is undecidable (i.e., not a recursive language) is in many ways more valuable than our previous discovery that Ld is not RE. The reason