6. fejezet - Recursively Enumerable Languages and Turing Machines

At the beginning of this chapter we introduce the recursive languages and the recursively enumerable languages. These two language classes are fundamental in computability theory. There are many equivalent definitions, however, we are going to use these two definitions now, and we are going to show how these definitions fit for the concept of the Turing machine later.

Definition 30. The language L ∈ V^* is recursive, if there is an algorithm, which decides about any word p ∈ V^*, whether or not p ∈ L.

We can say a language L is recursive, if the word problem can be solved in L. In Chapter 1. we define the class of the recursively enumerable languages as languages which can be generated by unrestricted generative grammars. Now, we give another definition.

Definition 31. The language L ∈ V^* is recursively enumerable, if there is a procedure, which specifies all the elements of L.

The two definitions of the recursively enumerable languages are equivalent. If there is a procedure, which specifies all elements of the language L, then there is a generative grammar which generates the language L, and if there is a generative grammar generating the language L, then this grammar itself is a procedure, which can be used to specify all elements of the language L.

It is obvious that each recursive language is a recursively enumerable, because we can list the words over an alphabet V, and select those words which are contained by the language L.

Theorem 31. The language L is recursive, if and only if both L and are recursively enumerable.

Proof. First, we show that, if L ∈ V^* and are recursively enumerables, then L - and also - is recursive. The language L is recursively enumerable, so there is a procedure which lists the elements of L. Let us denote these words p₁, p₂,.... However, is recursively enumerable as well, so we have another procedure which lists the elements of . Let us denote these words r₁,r₂,.... Now we can combine these two procedures, to use the first one, and then the second one, alternately. What we receive is the list of all words over the alphabet V: p₁, r₁, p₂, r₂,... and we know about each one if it belongs to the language L or not.

Now, we show that if L is recursive, then L and is recursively enumerable. We already mentioned that recursive languages are recursively enumerable, because we can list all the words over an alphabet V, and add the current word to the language if it is in L. The same algorithm can be used for the language , we can list the words again, and we add them to the language if they are not in the language L.

QED.

The following theorem shows the connection between the context-sensitive and recursive languages.

Theorem 32. Each context-sensitive language is recursive, but there are recursive languages which are not context-sensitive.

Proof. The first part of the theorem states that the word problem can be solved for each context-sensitive language. This was shown already in Section 5.3.2.

For the second part, let us create the list of each possible context-sensitive generative grammar G_i = (N_i, T_i, S_i, P_i), which generates numbers. (The set of the terminal letters of each grammar G_i are digits, so T_i = {0,1,2,3,4,5,6,7,8,9} for each G_i.) Now, we define language L, which contains the sequential numbers of grammars whose generated language does not contain its own sequential number (position in the list): L = {i∣i ∉ L(G_i)}.

We can create a list of all context-sensitive generative grammars which generates numbers, and we can decide whether or not a context-sensitive grammar generates its position in the list, so language L is recursive.

Now, suppose to the contrary that language L is context-sensitive. In this case, there is a context-sensitive grammar G_k, such that L(G_k) = L. Then, by the definition of L, if k ∈ L(G_k), then k ∉ L is a contradiction, and if k ∉ L(G_k), then k ∈ L is also a contradiction. The only possible solution is that language L is not context-sensitive.

QED.

The next theorem shows that there are languages which are not in the class of recursively enumerable languages, so the recursively enumerable language class does not contain all possible languages. The concept of the proof is similar to the previous proof.

Theorem 33. There exists a language L, which is not recursively enumerable.

Proof. Let us create the list of each generative grammar G_i = (N_i, T_i, S_i, P_i) which generates numbers. (The set of the terminals of each grammar G_i are numbers: T_i = {0,1,2,3,4,5,6,7,8,9} for each grammar G_i). We have to note that it is easy to create an ordered list of all possible generative grammars which generates numbers. Now, we define language L, which contains the numbers of the grammars which does not generate the number of its position in the list: L = {i∣i ∉ L(G_i)}.

Now, suppose to the contrary that the language L is recursively enumerable. In this case, there is a generative grammar G_k, such that L(G_k) = L. Then, by the definition of L, if k ∈ L(G_k), then k ∉ L is a contradiction, and if k ∉ L(G_k), then k ∈ L is also a contradiction. The only possible solution is that language L is not recursively enumerable.

QED.

We have already shown that the class of context-sensitive languages is a proper subset of the class of recursive languages. It has also been proven that the class of all languages is a proper superset of the class of recursively enumerable languages. Finally, we note that the complementer language of language L defined in the proof of Theorem 33. is recursively enumerable, but not recursive. We can summarize our results in the following formula:

where CS stands for context-sensitive languages, R stands for recursive languages, RE stands for recursively enumerable languages, and AL stands for all languages.