Recursive Language and Recursive Enumerable Language

Recursive Language and Recursive Enumerable Language

Before discussing Recursive language and Recursive Enumerable language, let us see what Turing machine responds for some input string.

• If we have the Turing machine T and it halts and accept the string s.
• The Turing machine T halts and rejects the string s.
• The Turing machine T never halts.

These are the 3 possibilities when we give an input string s to Turing machine T.

Recursive Language

A language L is called recursive or decidable, if there exists a Turing machine T. A recursive language accepts every string of the language L and rejects every string over some alphabet that is not in the language. Let L is a language and imagine it as a problem, then we can say a problem L is called decidable if it is recursive language, and is called undecidable if it not recursive.

• If string s belongs to Language L then Turing machine accepts it.
• If string s not belongs to Language L then Turing machine halts but it never enters an accepting state.

Turing machine: The Turing machine is more powerful because it has external memory which is capable of remembering arbitrary long sequence of input string. Neither finite automata nor push down automata can be considered as accurate model of general purpose computer, since they are unable to recognize simple language like L = { 0ⁿ 1ⁿ 2ⁿ | n>=0 }.

Recursive Enumerable Language

In recursively enumerable, if there exists a Turing machine that language L is said to be accepts it. A language for which an enumeration procedure exist is definitely a recursively enumerable language. The various recursive languages are also recursively enumerable languages but the vice versa is not true.

The above figure shows the relationship between recursive and recursively enumerable language.

Some Properties of Recursive and Recursive Enumerable Language

Theorem:

If L is recursive language then its complement L’ is also recursive language.

Proof: Let L be a recursive language that is accepted by Turing machine T, which halts on all inputs. Now we will construct a Turing machine T_s from Turing machine T, the construction is shown below:

As shown in above figure, the Turing machine T, on input string s enters into accept state then Turing machine T_s halts without accepting input string w. On the other hand, if Turing machine T halts without accepting input string w then T_s enters into a accept state. T_s accepts those strings that T do not accept. Thus, we can say T_s recognizes the complement of L.

Theorem:

If L1 and L2 are two recursive languages then the union of L1 and L2 i.e. L1 U L2 is also recursive.

Proof:

Let T1 and T2 are two Turing machines that recognize L1 and L2. We will construct a Turing machine T, whose construction is shown below:

T first simulates T1 and T accepts the input s if T1 accepts. If T1 rejects then T simulates T2 and accepts if T2 accepts. Since both T1 and T2 are two algorithms. T is guaranteed to halt.

Therefore, it is proved that Turing machine T accepts the union of L1 and L2.

Theorem:

The union of any two recursively enumerable language is also recursively enumerable language.

Proof: Let L1 and L2 are two recursively enumerable languages accepted by Turing machine T1 and T2. We will construct a Turing machine T, whose construction is shown below:

The Turing machine T simultaneously simulates T1 and T2 on separate tapes. If either T1 or T2 accepts the input string s then Turing machine T accepts.

Theorem:

L is a language and its complement L’ is recursively enumerable language, then L is also a recursive language.

Proof: M1 and M2 are the two Turing machines that recognize the language L and its complement L’. We will construct a Turing machine T, whose construction is shown below:

The Turing machine T simulates in parallel both T1 and T2. The states of T1 and T2 are each components of the state of Turing machine T. If Turing machine T1 accepts the input string s, then T also accepts the s. On the other hand, if T2 accepts input string s then T rejects s. Since input string s is either accepted by L or L’ and we know that exactly one of T1 and T2 will accept. Thus, T will always output with accept or reject but never say both. Since T is an algorithm that accepts L so we can say Language L is recursive.