Not RE

Figure 9.2: Relatiouship between the recursive, RE, and non-RE languages

The existence or nonexistence of an algorithm to solve a problem is often of more importance than the existence of some TM to solve the problem. As mentioned above, the Taring machines that are not guaranteed to halt may not give us enough information ever to conclude that a string is not in the language, so there is a sense in which they have not solved the problem. Thus, dividing problems or languages between the decidable - those that are solved by an algorithm - and those that are undecidable is often more important than the division between the recursively enumerable languages (those that have TMs of some sort) and the non-recursively-enumerable languages (which have no TM at all). Figure 9.2 suggests the relationship among three classes of languages:

1. The recursive languages.

2. The languages that are recursively enumerable but not recursive.

3. The non-recursively-enumerable (non-RE) languages.

We have positioned the non-RE language Ld properly, and we also show the language L , or universal language, that we shall prove shortly not to be recursive, although it is RE.

9.2.2 Complements of Recursive and RE languages

A powerful tool in proving languages to belong in the second ring of Fig. 9.2 (i.e., to be RE, but not recursive) is consideration of the complement of the language. We shall show that the recursive languages are closed under complementation. Thus, if a language L is RE, but L, the complement of i, is not RE, then we

Why Recursive ?

Programmers today are familiar with recursive functions. Yet these recursive functions dont seem to have anything to do with Turing machines that always halt. Worse, the opposite nonrecursive or undecidable - refers to languages that cannot be recognized by any algorithm, yet we are accustomed to thinking of nonrecursive as referring to computations that are so simple there is no need for recursive function calls.

The term recursive, as a synonym for decidable, goes back to Mathematics as it existed prior to computers. Then, formalisms for computation based on recursion (but not iteration or loops) were commonly used as a notion of computation. These notations, which we shall not cover here, had some of the flavor of computation in functional programming languages such as LISP or ML. In that sense, to say a problem was recursive had the positive sense of it is sufficiently simple that I can write a recursive function to solve it, and the function always finishes. That is exactly the meaning carried by the term today, in connection with Turing machines.

The term recursively enumerable harks back to the same family of concepts. A function could list all the members of a language, in some order; that is, it could enumerate them. The languages that can have their members Usted in some order are the same as the languages that are accepted by some TM, although that TM might run forever on inputs that it does not accept.

know L cannot be recursive. For if L were recursive, then L would also be recursive and thus surely RE. We now prove this important closure property of the recursive languages.

Theorem 9.3: If L is a recursive language, so is L.

PROOF: Let L = L{M) for some TM M that always halts. We construct a TM M such that L = L(M) by the construction suggested in Fig. 9.3. That is, M behaves just like M. However, M is modified as follows to create M:

1. The accepting states of M are made nonaccepting states of M with no transitions; i.e., in these states M will halt without accepting.

2. M has a new accepting state r; there are no transitions from r.

3. For each combination of a nonaccepting state of M and a tape symbol of M such that M has no transition (i.e., M halts without accepting), add a transition to the accepting state r.

Accept Reject

Figure 9.3: Construction of a TM accepting the complement of a recursive laiignage

Since M is guaranteed to halt, we Icnow that M is also guaranteed to hsdt. Moreove£, M accepts exactly those strings that M does not accept. Thus M accepts L. □

There is another important fact about complements of languages that further restricts where in the diagram of Fig. 9.2 a language and its complement can fall. We state this restriction in the next theorem.

Theorem 9.4: If both a language L and its complement are RE, then L is recursive. Note that then by Theorem 9.3, L is recursive as well.

PROOF: The proof is suggested by Fig. 9.4. Let L = L{Mi) and L = L(M-2). Both Ml and M2 are simulated in parallel by a TM M. We can make M a two-tape TM, and then convert it to a one-tape TM, to make the simulation easy and obvious. One tape of M simulates the tape of Mi. while the other tape of M simulates the tape of M2. The states of Mi and M2 are each components of the state of M.

- Accept

Reject

Figure 9.4: Simulation of two TMs accepting a language and its complement

If Input w to M is in L, then Mi will eventually accept. If so, M accepts and halts. If ш is not in L, then it is in L, so M2 will eventually accept. When M2 accepts, M halts without accepting. Thus, on ail inputs, M halts, and