**Tartalom**

Summary of the chapter:In this chapter, we discuss the most universal language class, the class of recursively enumerable languages, and the most universal automaton, the Turing machine. In the first section, we investigate the recursive and the recursively enumerable languages, and their closure and other properties. The second and third section is dedicated to the Turing machine. We will show two different applications. First, we are going to use the Turing machine as a universal language acceptor, then we show how we can use it as a simple but universal computing device.

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*_{1},
*p*_{2},....
However, is recursively enumerable as well, so we have another procedure which lists
the elements of . Let us denote these words *r*_{1},*r*_{2},....
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*_{1}, *r*_{1}, *p*_{2},
*r*_{2},... 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}* = (

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

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}* = (

Now, suppose to the contrary that the language *L* is recursively enumerable. In this case, there is a generative
grammar *G _{k}*, such that

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:

CS⊊R⊊RE⊊AL

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

**Theorem 34.** *The class of recursive languages is closed under complement operation.*

**Proof.** Theorem 31. states that language *L* is recursive,
if and only if *L* and
are both recursively enumerable. However, we can apply the same theorem for the language ,
and what we receive as a result is that is recursive, if and *L* are both recursively
enumerable, which is the same condition, so if *L* is recursive, then is recursive, as well.

QED.

**Theorem 35.** *The class of recursively enumerable languages is not closed under complement operation.*

**Proof.** The proof of this theorem is easy, we need only one example, where the language itself is recursively
enumerable, and the complement language is not recursively enumerable. In the proof of the Theorem 33.
we have defined a language *L* which is not recursively
enumerable. The complement language is recursively enumerable. Here we have a recursively
enumerable language , whose complement is not recursively enumerable.

QED.

**Theorem 36.** *The class of recursively enumerable languages is closed under
regular operations.*

**Proof.** We give a constructive proof here. Let the languages *L*_{1} and
*L*_{2} be recursively
enumerable. Let the grammar *G**1* = (*N*_{1}, *T,
S*_{1}, *P*_{1}) such that
*L*(*G*_{1}) = *L*_{1}, and let the
grammar *G*_{2} = (*N*_{2}, *T, S*_{2},
*P*_{2}) such that *L*(*G*_{2}) = *L*_{2}.
Without loss of generality we can suppose that *N*_{1} ∩ *N*_{2} =∅,
and the terminal symbols appear only in rules having the form *A* → *a*,
where *A* ∈ *N, a* ∈ *T*. We define generative grammars
*G _{Un}*, and

Union

Let

*S*be a new start symbol, such that*S*∩*N*_{1}=*S*∩*N*_{2}=*S*∩*T*= ∅, and let*G*= (_{Un}*N*_{1}∪*N*_{2}∪ {*S*},*T, S, P*_{1}∪*P*_{2}∪ {*S*→*S*_{1},*S*→*S*_{2}}).Concatenation

Let

*S*be a new start symbol, such that*S*∩*N*_{1}=*S*∩*N*_{2}=*S*∩*T*= ∅, and let*G*= (_{Co}*N*_{1}∪*N*_{2}∪ {*S*},*T, S, P*_{1}∪*P*_{2}∪ {*S*→*S*_{1}*S*_{2}}).Kleene star

In order to create a grammar generating the language

*L*(*G*) =_{Kl}*L*_{1}^{*}we use two grammars. Let the grammar*G*_{1}= (*N*_{1},*T, S*_{1},*P*_{1}), and let the grammar*G*_{2}= (*N*_{2},*T, S*_{2},*P*_{2}) such that*L*(*G*_{1}) =*L*(*G*_{2}) =*L*_{1}\ {λ}, and*N*_{1}∩*N*_{2}= ∅. Without loss of generality we can suppose that the terminal symbols appear only in rules having the form*A*→*a*, where*A*∈*N, a*∈*T*. For the grammar*G*we again use a new start symbol_{Kl}*S*, where*S*∩*N*_{1}=*S*∩*N*_{2}=*S*∩*T*= ∅. Then, let*G*= (_{Kl}*N*_{1}∪*N*_{2}∪ {*S*},*T, S, P*_{1}∪*P*_{2}∪ {*S*→ λ,*S*→*S*_{1},*S*→*S*_{1}*S*_{2}*S*}).

QED.

**Theorem 37.** *The class of recursively enumerable languages is closed under intersection.*

**Proof.** By applying the definition of the recursively enumerable language, we can create a list of
the elements of the recursively enumerable language *L*_{1} without repetitions, and yet another list, which
contains the elements from the recursively enumerable language *L*_{2} without repetitions. Then, we can
create a list, which contains one element from the list of the language *L*_{1}, and then one element of the list
of the language *L*_{2} alternately. We move an element from this combined list into the list of the
*L*_{1} ∩ *L*_{2}, if the element appears twice.

QED.

Finally, we have to note that recursive languages are also closed under regular operations and intersection.

**Definition ** *The grammar G* = (*N, T, S, P*) *is in Révész normal form,
if all of its production rules has the following forms:*

*S*→ λ,*A*→*a*,*A*→*B*,*A*→*BC*,*AB*→*AC*,*AB*→*CB, or**AB*→*B*,

where *A, B, C* ∈ *N* and *a* ∈ *T*.

This normal form for unrestricted grammars was introduced by György Révész. Compared to the Kuroda normal form, the differences are the following:

It allows the rule

*S*→ λ for grammars generating the empty word,instead of the rule

*AB*→*CD*it allows two rules, namely*AB*→*AC*and*AB*→*CB*,the only ,,really plus'' rule, which makes the difference between the monotone and unrestricted grammars is the last production rule:

*AB*→*B*.

As you can see, there is not a huge difference between the unrestricted grammars and the context-sensitive grammars. For generative grammars generating context-sensitive languages, only one production rule form is enough to be able to generate any recursively enumerable language.

Even more surprising results were proven by Viliam Geffert. His results put limitations not just to the form of the production rules, but also to the number of the nonterminal symbols. We introduce his results as theorems, without proofs.

**Theorem 38.** *For each recursively enumerable language L we can give an unrestricted generative grammar
G* = (*N, T, S, H*)
*such that*

*grammar G generates the language L, (L*(*G*) =*L)*,*G has exactly 5 nonterminal symbols, (N*= {*S, A, B, C, D*}*), and**each rule has a form:**S*→*p where S is the start symbol, and p is a nonempty word, (p*∈ (*N*∪*T*)^{+}*),**AB*→ λ,*or**CD*→ λ.

**Theorem 39.** *For each recursively enumerable language L we can give an unrestricted generative grammar
G* = (*N, T, S, H*)
*such that*

*grammar G generates the language L, (L*(*G*) =*L)*,*G has exactly 4 nonterminal symbols, (N*= {*S, A, B, C*}*), and**each rule has a form:**S*→*p where S is the start symbol, and p is a nonempty word, (p*∈ (*N*∪*T*)^{+}*),**AB*→ λ,*or**CC*→ λ.

**Theorem 40.** *For each recursively enumerable language L we can give an unrestricted generative grammar
G* = (*N, T, S, H*)
*such that*

*grammar G generates the language L, (L*(*G*) =*L),**G has exactly 3 nonterminal symbols, (N*= {*S,A,B*}),*and**each rule has a form:**S*→*p where S is the start symbol, and p is a nonempty word, (p*∈ (*N*∪*T*)^{+}*),**AA*→ λ,*or**BBB*→ λ.

**Theorem 41.**
*For each recursively enumerable language L we can give an unrestricted generative grammar G* =
(*N, T, S, H*)
*such that*

*grammar G generates the language L, (L*(*G*) =*L),**G has exactly 3 nonterminal symbols, (N*= {*S, A, B*}),*and**each rule has a form:**S*→*p where S is the start symbol, and p is a nonempty word, (p*∈ (*N*∪*T*)^{+}*), or**ABBBA*→ λ.

**Theorem 42.**
*For each recursively enumerable language L we can give an unrestricted generative grammar
G* = (*N, T, S, H*) *such that*

*grammar G generates the language L, (L*(*G*) =*L),**G has exactly 4 nonterminal symbols, (N*= {*S, A, B, C*}),*and**each rule has a form:**S*→*p where S is the start symbol, and p is a nonempty word, (p*∈ (*N*∪*T*)^{+}*), or**ABC*→ λ.