Recursive and Recursively Enumerable Languages

What are Recursive Languages?

Recursive languages are languages for which we can always decide membership.

Simple Analogy

Recursive language is like:

  • Yes/No question: Always get clear answer
  • Traffic light: Always red or green (never stuck)
  • Calculator: Always gives result

Non-recursive is like:

  • Magic 8-ball: Sometimes says “ask again later”
  • Broken light: Might stay yellow forever
  • Infinite loop: Never returns answer

Formal Definition

Language L is recursive (decidable) if there exists TM M such that:

  1. For w ∈ L: M accepts w (halts in qaccept)
  2. For w ∉ L: M rejects w (halts in qreject)
  3. M always halts: Never loops

Key property: Complete decision procedure!

Alternative Names

  • Recursive (original term)
  • Decidable (modern term)
  • Computable (if viewed as characteristic function)
  • Totally decidable

What are Recursively Enumerable Languages?

Recursively Enumerable (RE) languages are languages we can recognize.

Formal Definition

Language L is recursively enumerable if there exists TM M such that:

  1. For w ∈ L: M accepts w (eventually halts in qaccept)
  2. For w ∉ L: M rejects w OR loops forever
  3. M may not halt: Can loop on reject

Key property: Semi-decision procedure (says “yes” if true)

Alternative Names

  • Recursively enumerable (RE) (original term)
  • Turing-recognizable (modern term)
  • Partially decidable
  • Computably enumerable (c.e.)
  • Semi-decidable

Relationship Between Classes

Hierarchy

Recursive ⊂ Recursively Enumerable ⊂ All Languages

Every recursive language is RE:

  • If always halts, certainly recognizes
  • Decidable ⟹ Recognizable

Not every RE language is recursive:

  • May loop on reject
  • Example: HALT is RE but not recursive

Not all languages are RE:

  • Most languages not even recognizable!
  • Example: H̄ALT (complement of HALT)

Venn Diagram

┌─────────────────────────────────────┐
│     All Languages (uncountable)     │
│  ┌──────────────────────────────┐   │
│  │  Recursively Enumerable (RE) │   │
│  │  ┌────────────────────────┐  │   │
│  │  │   Recursive (R)        │  │   │
│  │  │                        │  │   │
│  │  │  {aⁿbⁿcⁿ}             │  │   │
│  │  │  {ww}                  │  │   │
│  │  │  Regular languages     │  │   │
│  │  │  Context-free langs    │  │   │
│  │  └────────────────────────┘  │   │
│  │                               │   │
│  │  HALT (RE but not R)          │   │
│  │  Aₜₘ                          │   │
│  └──────────────────────────────┘   │
│                                      │
│  H̄ALT (not RE)                      │
│  Most languages                      │
└─────────────────────────────────────┘

Examples of Recursive Languages

1. Regular Languages

All regular languages are recursive

Example: L = {w | w has even number of a’s}

TM: Simulate DFA (always halts)

2. Context-Free Languages

All CFLs are recursive

Example: L = {aⁿbⁿ | n ≥ 0}

TM:

1. Mark one 'a' with X
2. Find and mark one 'b' with Y
3. Repeat until all matched
4. Accept if all matched, reject otherwise
5. Always halts!

3. Context-Sensitive Languages

All CSLs are recursive

Example: L = {aⁿbⁿcⁿ | n ≥ 0}

TM:

1. Mark one 'a', one 'b', one 'c'
2. Repeat until all matched
3. Always halts (finite string)

4. Prime Numbers

L = {aᵖ | p is prime}

TM:

1. Count length n of input
2. Test if n is divisible by 2, 3, ..., n-1
3. Accept if no divisors (prime)
4. Reject if divisor found (composite)
5. Always halts in O(n²) steps

5. Palindromes

L = {w | w = wᴿ}

TM:

1. Mark first symbol, remember it
2. Go to end, check last symbol matches
3. Mark and move inward
4. Repeat until all matched or mismatch
5. Always halts

Examples of RE but Not Recursive

1. Halting Problem

HALT = {⟨M, w⟩ | M halts on w}

RE:

TM M_recognize(⟨M, w⟩):
  Simulate M on w
  If M halts, accept
  If M loops, we also loop

Not recursive: Proved by Turing (diagonal argument)

2. Acceptance Problem

Aₜₘ = {⟨M, w⟩ | M accepts w}

RE:

Simulate M on w
Accept if M accepts
Loop if M rejects or loops

Not recursive: Equivalent to HALT

3. Non-Empty Language

NEₜₘ = {⟨M⟩ | L(M) ≠ ∅}

RE:

For each string w in Σ* (in order):
  Simulate M on w
  If M accepts any w, accept ⟨M⟩

Not recursive: Rice’s theorem

Examples of Non-RE Languages

1. Complement of HALT

H̄ALT = {⟨M, w⟩ | M does not halt on w}

Not RE:

  • If H̄ALT were RE, both HALT and H̄ALT would be RE
  • Then HALT would be recursive (theorem below)
  • Contradiction!

2. Complement of Acceptance

Āₜₘ = {⟨M, w⟩ | M does not accept w}

Not RE: Similar reasoning

3. Equivalence to Empty

EQₜₘ,∅ = {⟨M⟩ | L(M) = ∅}

Not RE: Complement of NEₜₘ

Key Theorems

Theorem 1: Complement Closure

Theorem: If L is recursive, then L̄ is recursive.

Proof:

  • Let M decide L
  • Construct M’ that runs M and flips answer
  • M’(w) accepts ⟺ M(w) rejects
  • M’ always halts (M does)
  • M’ decides L̄

Consequence: Recursive closed under complement ✓

Theorem 2: RE Not Closed Under Complement

Theorem: RE is NOT closed under complement.

Proof by counterexample:

  • HALT is RE
  • H̄ALT is not RE
  • If RE closed under complement, H̄ALT would be RE
  • Contradiction!

Consequence: RE ≠ co-RE (in general)

Theorem 3: Characterization of Recursive

Theorem: L is recursive ⟺ L and L̄ are both RE.

Proof (⟹):

  • If L recursive, TM M decides it
  • M recognizes L (accepts w ∈ L)
  • M̄ (flipped M) recognizes L̄
  • Both L and L̄ are RE

Proof (⟸):

  • L recognized by M₁
  • L̄ recognized by M₂
  • Run M₁ and M₂ in parallel on input w: 
    For i = 1, 2, 3, ...:
  Run M₁ for i steps
  If M₁ accepts, ACCEPT
  Run M₂ for i steps
  If M₂ accepts, REJECT
  • One must accept eventually!
  • This procedure always halts
  • L is recursive

Very important theorem!

Co-RE Languages

Definition: L is co-RE if L̄ is RE

Equivalently: TM that accepts complement

Relationship to Recursive

     RE
      ∩
    co-RE
      ∥
  Recursive

L recursive ⟺ L ∈ RE ∩ co-RE

Examples

RE ∩ co-RE: All recursive languages

RE \ co-RE: HALT, Aₜₘ, NEₜₘ

co-RE \ RE: H̄ALT, Āₜₘ, EQₜₘ,∅

Neither: Most languages!

Closure Properties

Recursive Languages

Recursive closed under:

✓ Union: L₁ ∪ L₂

Run M₁ and M₂ sequentially
Accept if either accepts

✓ Intersection: L₁ ∩ L₂

Run M₁ and M₂ sequentially
Accept if both accept

✓ Complement: L̄

Run M and flip answer

✓ Concatenation: L₁L₂

Try all splits w = xy
Check if x ∈ L₁ and y ∈ L₂

✓ Kleene star: L*

Try all splits w = w₁w₂...wₖ
Check if each wᵢ ∈ L

All standard operations!

Recursively Enumerable Languages

RE closed under:

✓ Union: L₁ ∪ L₂

Run M₁ and M₂ in parallel
Accept if either accepts

✓ Intersection: L₁ ∩ L₂

Run M₁ and M₂ in parallel
Accept if both accept

✓ Concatenation: L₁L₂

Try all splits in parallel
Accept if any split works

✓ Kleene star: L*

Try all splits in parallel
Accept if any split works

✗ Complement: L̄

NOT closed! (HALT vs H̄ALT)

Summary Table

OperationRecursiveRE
Union✓✓
Intersection✓✓
Complement✓✗
Concatenation✓✓
Kleene star✓✓

Enumerators

Definition

Enumerator: TM with printer that outputs strings

No input! Just generates strings.

Connection to RE

Theorem: L is RE ⟺ Some enumerator enumerates L

Proof (⟹): RE → Enumerator

Given TM M recognizing L:

Enumerator E:
  For i = 1, 2, 3, ...:
    For each string w of length ≤ i:
      Run M on w for i steps
      If M accepts w, print w

Eventually prints all strings in L

Proof (⟸): Enumerator → RE

Given enumerator E for L:

TM M(w):
  Run E
  If E ever prints w, accept
  (Loop forever if w ∉ L)

M recognizes L

Lexicographic Enumerator

Enumerates strings in order:

ε, a, b, aa, ab, ba, bb, aaa, aab, …

For finite languages: Recursive ✓

For infinite languages: May be RE only

Characteristic Functions

Definition

Characteristic function of L:

χₗ(w) = 1 if w ∈ L
       = 0 if w ∉ L

Connection to Recursive

Theorem: L is recursive ⟺ χₗ is computable

Proof (⟹):

  • If L recursive, TM M decides it
  • Compute χₗ(w): Run M(w), output 1 if accept, 0 if reject

Proof (⟸):

  • If χₗ computable, TM computes it
  • Decide L: Compute χₗ(w), accept if 1, reject if 0

Partial Functions

For RE languages: χₗ may be partial (undefined on some inputs)

Computable partial function: TM computes when defined, loops otherwise

Reduction and RE

Mapping Reduction

A ≤ₘ B: Computable f such that w ∈ A ⟺ f(w) ∈ B

Properties:

  1. If B recursive and A ≤ₘ B, then A recursive
  2. If B RE and A ≤ₘ B, then A RE
  3. If A not RE and A ≤ₘ B, then B not RE

Many-One Complete

L is RE-complete if:

  1. L is RE
  2. Every RE language A reduces to L (A ≤ₘ L)

Examples of RE-complete:

  • HALT
  • Aₜₘ
  • Any universal language

Hardest RE problems!

Recursive vs RE Examples Summary

Recursive (Decidable)

  1. All regular languages

    • {aⁿbⁿ} with n even
    • {w | w contains “hello”}

  2. All context-free languages

    • {aⁿbⁿ}
    • Balanced parentheses

  3. All context-sensitive languages

    • {aⁿbⁿcⁿ}

  4. Arithmetic

    • Primes: {aᵖ | p prime}
    • Even numbers

  5. Graph properties with finite graphs

    • Hamiltonian path (for given graph)
    • Graph coloring (for given graph)

RE but Not Recursive

  1. HALT = {⟨M, w⟩ | M halts on w}

  2. Aₜₘ = {⟨M, w⟩ | M accepts w}

  3. NEₜₘ = {⟨M⟩ | L(M) ≠ ∅}

  4. INFₜₘ = {⟨M⟩ | L(M) infinite}

  5. REGₜₘ = {⟨M⟩ | L(M) regular}

Not RE

  1. H̄ALT = {⟨M, w⟩ | M doesn’t halt on w}

  2. Āₜₘ = {⟨M, w⟩ | M doesn’t accept w}

  3. EQₜₘ,∅ = {⟨M⟩ | L(M) = ∅}

  4. TOTₜₘ = {⟨M⟩ | M halts on all inputs}

  5. FINₜₘ = {⟨M⟩ | L(M) finite}

Important Distinctions

Recursive vs RE

Recursive: Always answers

  • “Yes” or “No”
  • Like deterministic decision

RE: Sometimes answers

  • “Yes” if true
  • Silent if false (may loop)
  • Like search: find if exists

Recognizable vs Decidable

Recognizable = RE (same thing!)

Decidable = Recursive (same thing!)

Modern terminology: Recognizable and Decidable

Classical terminology: RE and Recursive

Practical Implications

Program Verification

Decidable: Can verify property always

  • Type checking ✓
  • Syntax checking ✓

RE: Can verify if true, may loop if false

  • Program correctness (search for proof)

Not RE: Can’t even verify if true

  • Program incorrectness (for all inputs)

Testing

Decidable: Can test completely

  • Finite state machine testing

RE: Can test for success

  • Find bug (eventually if exists)

Not RE: Can’t test at all

  • Prove no bugs exist

Important Exam Points

  1. ✓ Recursive: TM always halts (decidable)
  2. ✓ RE: TM accepts members (may loop on non-members)
  3. ✓ Recursive ⊂ RE: Every decidable is recognizable
  4. ✓ L recursive ⟺ L and L̄ both RE
  5. ✓ RE not closed under complement: HALT vs H̄ALT
  6. ✓ Recursive closed under complement: Can flip answer
  7. ✓ All CFLs recursive: Can use parsing algorithms
  8. ✓ HALT is RE but not recursive: Can simulate but not decide
  9. ✓ Enumerator ⟺ RE: Can list strings in language
  10. ✓ Most languages not RE: Uncountably many languages

Common Mistakes to Avoid

✗ Mistake 1: Confusing recursive and RE
✓ Correct: Recursive always halts, RE may loop

✗ Mistake 2: Thinking RE closed under complement
✓ Correct: RE NOT closed (HALT vs H̄ALT)

✗ Mistake 3: All languages are RE
✓ Correct: Most languages not even RE!

✗ Mistake 4: If L is RE, L̄ is RE
✓ Correct: Only if L is recursive

✗ Mistake 5: Recursive = recognizable
✓ Correct: Recursive = decidable (stronger than recognizable)

✗ Mistake 6: Using “recursive” and “RE” interchangeably
✓ Correct: Recursive ⊂ RE (recursive is subset)

Practice Questions

Q1: What is a recursive language?

Answer: Language for which TM always halts with correct answer.

Q2: What is RE language?

Answer: Language for which TM accepts members (may loop on non-members).

Q3: Is every recursive language RE?

Answer: Yes! Recursive ⊂ RE (subset).

Q4: Is every RE language recursive?

Answer: No! HALT is RE but not recursive.

Q5: How to prove L is recursive?

Answer: Show L and L̄ both RE, or show TM that always halts.

Q6: Is RE closed under complement?

Answer: No! HALT is RE but H̄ALT is not RE.

Q7: Is recursive closed under complement?

Answer: Yes! Can flip accept/reject.

Q8: What is enumerator?

Answer: TM that prints all strings in language.

Q9: Is HALT recursive?

Answer: No! HALT is RE but not recursive (undecidable).

Q10: Are all CFLs recursive?

Answer: Yes! Can parse in finite time.

Summary

  • Recursive: TM always halts (decidable, computable)
  • RE: TM accepts members (recognizable, semi-decidable)
  • Relationship: Recursive ⊂ RE ⊂ All
  • Complement: Recursive closed ✓, RE not closed ✗
  • Characterization: L recursive ⟺ L and L̄ both RE
  • Closure: Both closed under ∪, ∩, concat, star
  • Examples recursive: Regular, CFL, CSL, primes
  • Examples RE not recursive: HALT, Aₜₘ, NEₜₘ
  • Examples not RE: H̄ALT, Āₜₘ, TOTₜₘ
  • Enumerator: Can list RE languages
  • Most languages: Not even RE (uncountable)
  • Key insight: Hierarchy of computability power

Recursive and RE languages form the foundation of computability!