Recursive and Recursively Enumerable Languages
Prof. (Dr.) K.R. Chowdhary
Email: kr.chowdhary@gmail.com
Formerly at department of Computer Science and Engineering
MBM Engineering College, Jodhpur

Thursday 13th November, 2025

kr chowdhary

TOC

1/ 12

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Defining R and RE languages
Recursive: They allow a function to call itself. Or, a recursive
language is a recursive subset in the set of all possible words over
alphabet Σ of that language.
Non-recursive should not be taken as simpler version of computation,
i.e., e.g., obtaining factorial value without recursion method.
Regular languages ⊆ context free languages ⊆ context sensitive
languages ⊆ recursive languages ⊆ recursive enumerable languages.
A language is Recursively Enumerable (RE) if some Turing machine
accepts it.
- A TM M with alphabet Σ accepts L if
L = {w ∈ Σ∗ |M halts with input w }
- Let L be a RE language and M the Turing Machine that accepts it.
∴, for w ∈ L, M halts in final state. For w ∈
/ L, M halts in non-final
state or loops for ever.
A language is Recursive (R) if some Turing machine M recognizes it
and halts on every input string, w ∈ Σ∗ . Recognizable = Decidable.
Or A language is recursive if there is a membership algorithm for it.
Let L be a recursive language and M the Turing Machine that
accepts (i.e. recognizes) it. For string w , if w ∈ L, then M halts in
final state. If w ∈
/ L, then M halts in non-final state. (halts always!).
kr chowdhary

TOC

2/ 12

Relation between Recursive and RE languages

Every Recursive language is RE. ∴, if M is TM recognizing L, the M
can be easily modified so its accepts L.
The languages which are non-RE cannot be recognized by TM.
These are diagonal (Ld ) languages of the diagonal of x − y , where xi
is language string wi , and yi is TM Mi .
Language < M, w >, where M is TM and w is string, is not RE
language, since its generalized form is not Turing decidable
(undecidability proof), ∴, it is non-RE language.

kr chowdhary

TOC

3/ 12

Every is recursive language can be enumerated
Theorem
If a language L is recursive then there exists an enumeration procedure
for it.

Proof.
If Σ = {a, b}, then M´can enumerate strings:
a, b, aa, ab, ba, bb, aaa, . . . .

Enumeration procedure: M´generates string w. M checks, if w ∈ L;
if yes, output w else ignore w.
Let L = {a, ab, bb, aaa, . . . }. M´output = {a, b, aa, ab, ba, bb, aaa, };
L(M) = {a, ab, bb, aaa, . . . }; enumerated output = a, ab, bb, aaa, . . .
kr chowdhary

TOC

4/ 12

Class of Languages
• recursive = decidable, their TM
always halts
• recursive enumerable
(semi-decidable) but not recursive
= their TM always halt if they
accept, otherwise halts in non-final
state or loops.
• non-recursively enumerable
(non-RE) = there are no TMs for
them.
• Recursive languages are closed
under complementation.

are made non-accepting states of
M ′ with no transitions, i.e., here
M ′ will halt without accepting.
• If s is new accepting state in M ′ ,
then there is no transition from this
state.
• If L is recursive, then L = L(M)
for some TM M, that always halts.
• Transform M into M´ so that M´
accept when M does not and
vice-versa. So M´ always halts and
accepts L̄. Hence L̄ is recursive.

Theorem
If L is recursive then L̄ is also recursive.
Proof: The accepting states of M

kr chowdhary

TOC

5/ 12

Theorem Proof
Theorem

recursive.

If L and L̄ are RE, then L is recursive.
Proof: Let L = L(M1 ) and
L̄ = L(M2 ). Construct a TM M
that simulates M1 and M2 in
parallel, using two tapes and two
heads. If i/p to M is in L, then M1
accepts it and halts, hence M
accepts it and halts. If input to M
is not in L, hence it is in L̄, ∴, M2
accepts and halts, hence M halts
without accepting. Hence M halts
on every i/p and L(M) = L. So L is

kr chowdhary

Closure Properties: Recursive
languages are closed under union,
concatenation, intersection and
Kleene star, complement, set
difference (L1 − L2 )

TOC

6/ 12

RE Language
Theorem
A language L is recursive enumerable iff there exists an enumeration
procedure for it.

Proof.
If there is an enumeration procedure, then we can enumerate all the
strings, and compare each with w each time till it is found.
If the language is RE, then we can follow an enumerature procedure
to systematically generate all the strings.

kr chowdhary

TOC

7/ 12

Intersection of RE and R languages
Given a Recursive and a RE languages: Their Union is RE,
Intersection is RE, Concatenation is RE, and Kleene’s closure is RE.
if L1 is Recursive and L2 is RE , then L2 − L1 is RE and L1 − L2 is
not RE .

Theorem
The intersection R and RE languages is RE.

Proof.
Let L1 and L2 be languages recognized by Turing machines M1 and
M2 , respectively.
Let a new TM M∩ is for the intersection L1 ∩ L2 . M∩ simply
executes M1 and M2 one after the other on the same input w : It
first simulates M1 on w . If M1 halts by accepting it, M∩ clears the
tape, copies the input word w on the tape and starts simulating M2 .
If M2 also accepts w then M∩ accepts.
Clearly, M∩ recognizes L1 ∩ L2 , and if M1 and M2 halt on all inputs
then also M∩ halts on all inputs.
kr chowdhary

TOC

8/ 12

closure properties . . .
Theorem
The union of two Recursive languages is recursive.

Proof.
The TM corresponding to this must halt always. Let L1 and L2 be
sets accepted by M1 and M2 , respectively. Then L1 ∪ L2 is accepted
by TM M, where x = w1 ∪ w2 , for w1 ∈ L1 and w2 ∈ L2 .

kr chowdhary

TOC

9/ 12

Closure properties . . .
Theorem
The union of two RE languages is RE.

Proof.
Let L1 and L2 be sets accepted by M1 and M2 , respectively. Then
L1 ∪ L2 is accepted by TM M, where x = w1 ∪ w2 , for w1 ∈ L1 and
w 2 ∈ L2 .
To determine if M1 or M2 accepts x we run both M1 and M2
simultaneously, using a two-tape TM M. M simulates M1 on the
first tape and M2 on the second tape. If either one enters the final
state, the input is accepted.

kr chowdhary

TOC

10/ 12

Summary of R and RE
• There are languages which are
neither recursive nor RE (Ref:
Countable algorithms(TM) but
uncountable languages)

• Both L and L̄ are recursive, then
both are in the inner circle.
Palindrome and CFG are recursive.
• Neither L or L̄ are RE, the both
are outside the outer ring.
• L is RE but not recursive, and L̄
is non-RE; then first is in outer
circle, and second is in outer most
space.
kr chowdhary

• Closure of recursive language in
L1 − L2 follows from the fact that
these set difference can be
expressed in terms of intersection
and complement.
• Weak Result: If a language is
recursive then there is an
enumeration procedure.
•Strong Result: A language is RE
iff there is an Enumeration
procedure.
TOC

11/ 12

Bibliography

Chowdhary, K.R. (2025). Decidability, Undecidability, and
Unsolvability. In: Theory of Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_12

kr chowdhary

TOC

12/ 12