Recursive & Recursively Enumerable Languages: Definitions, Machines, Proofs & Real-World Links

TAKEAWAYS:

• Recursive languages are decidable (Turing machine halts on all inputs), while recursively enumerable languages are recognizable (Turing machine halts only on "yes" instances).
• The halting problem proves no general algorithm can decide if a TM halts, separating recursive from recursively enumerable languages.
• Post’s Correspondence Problem is a classic example of a recursively enumerable but non-recursive language.
• Real-world applications include compiler optimizations (deciding if a program terminates) and database query planning (enumerating valid query paths).
• Reduction techniques (e.g., mapping NP-complete problems to RE languages) are key tools in computability proofs.
• Recursive languages are closed under complement, intersection, and union, while RE languages are only closed under union.

Core Definitions: Recursive vs. Recursively Enumerable Languages

Recursive and recursively enumerable (RE) languages are two fundamental classes in computability theory, distinguished by whether a Turing machine (TM) can decide (halt on all inputs) or merely recognize (halt only on "yes" instances) them.

1. Recursive Languages (Decidable)

A language $L$ is recursive if there exists a Turing machine $M$ that:

• Halts on all inputs (accepts or rejects).
• Correctly decides membership in $L$.

Key Properties:

• Closed under complement: If $L$ is recursive, so is $\overline{L}$.
• Closed under union, intersection, and concatenation.
• Example: $L=\{w\in \{0,1{\}}^{\ast }\mid w\text{ has even number of }1\text{s}\}$.

2. Recursively Enumerable Languages (Recognizable)

A language $L$ is recursively enumerable (RE) if there exists a Turing machine $M$ that:

• Halts and accepts if $w\in L$.
• May loop forever if $w\notin L$.

Key Properties:

• Not closed under complement: If $L$ is RE, $\overline{L}$ may not be RE.
• Closed under union (but not intersection or complement).
• Example: The halting problem $L_{halt}=\{⟨M,w⟩\mid M\text{ halts on }w\}$ is RE but not recursive.

Visual: Recursive vs. RE Languages

classDiagram
    class Recursive {
        +Decidable by TM
        +Closed under complement
        +Example: Even 1s in binary strings
    }
    class RE {
        +Recognizable by TM
        +Not closed under complement
        +Example: Halting problem
    }
    Recursive --|> RE : Subset
    note for Recursive "All recursive languages are RE, but not vice versa."

The Halting Problem: Why RE ≠ Recursive

The halting problem (proven undecidable by Alan Turing, 1936) shows that not all RE languages are recursive.

Proof Sketch (Reduction from $L_{halt}$ to $\overline{L_{halt}}$)

1. Assume a TM $M$ decides $L_{halt}$.
2. Construct a TM $M^{\prime }$ that:
   • On input $⟨M,w⟩$, runs $M$ on $⟨M,w⟩$.
   • If $M$ accepts, $M^{\prime }$ loops forever.
   • If $M$ rejects, $M^{\prime }$ accepts.
3. Contradiction: $M^{\prime }$ would decide $\overline{L_{halt}}$, but $\overline{L_{halt}}$ is not RE (by Rice’s Theorem).

Post’s Correspondence Problem (PCP): A Classic RE but Non-Recursive Language

PCP is a decision problem where:

• Given pairs of strings $(u_1,v_1),(u_2,v_2),\dots ,(u_n,v_n)$, determine if there exists a sequence $i_1,i_2,\dots ,i_k$ such that: $u_{i_1}{u}_{i_2}\dots u_{i_k}=v_{i_1}{v}_{i_2}\dots v_{i_k}$.

Why PCP is RE but not recursive?

• RE: A TM can enumerate all possible sequences and check for equality.
• Not recursive: No TM can decide PCP in finite time (proven by Post, 1946).

Example (Solvable Instance):

Pairs: (a, ε), (b, a), (ε, b)
Solution: Choose indices 1, 2 → \( u_1u_2 = a \cdot b \), \( v_1v_2 = \varepsilon \cdot a = a \). Not equal.
Wait, let’s correct:
Pairs: (a, ε), (b, a), (ε, b)
Solution: Choose indices 1, 3 → \( u_1u_3 = a \cdot \varepsilon = a \), \( v_1v_3 = \varepsilon \cdot b = b \). Still no.
Better example:
Pairs: (a, ε), (ε, a)
Solution: Choose index 1 → \( u_1 = a \), \( v_1 = \varepsilon \). Not equal.
Hmm, perhaps a clearer example:
Pairs: (a, ε), (ε, a), (b, b)
Solution: Choose indices 1, 2 → \( u_1u_2 = a \cdot \varepsilon = a \), \( v_1v_2 = \varepsilon \cdot a = a \). **Equal!**

Real-World Applications

1. Compiler Design (Termination Analysis)

• Idea Used: Deciding if a program terminates (recursive language).
• Example: eSewa’s payment validation system uses recursive checks to ensure transactions complete (no infinite loops in payment processing scripts).
• How: The compiler’s static analyzer checks for loops with no exit conditions (a recursive decision problem).

2. Database Query Optimization (RE Languages)

• Idea Used: Enumerating valid query paths (RE language).
• Example: Ncell’s customer data queries enumerate possible paths to fetch records without exhaustively checking all combinations (RE but not recursive due to NP-hard subproblems).
• How: The query planner generates candidate execution plans (RE) but cannot always decide the optimal one in polynomial time.

3. Cryptography (One-Way Functions)

• Idea Used: RE languages for "hard" problems (e.g., factoring).
• Example: Khalti’s transaction hashing relies on RE problems (e.g., discrete log) to ensure security. Breaking these would require enumerating solutions (RE) but is computationally infeasible.

Worked Example: Proving a Language is RE

Problem: Show $L=\{⟨M⟩\mid M\text{ is a TM that accepts at least one input}\}$ is RE.

Solution:

1. TM Construction: Build a TM $M^{\prime }$ that:
   • Enumerates all possible inputs $w_1,w_2,\dots$.
   • Simulates $M$ on each $w_i$.
   • If $M$ accepts any $w_i$, $M^{\prime }$ accepts $⟨M⟩$.
2. Why RE?: $M^{\prime }$ halts and accepts if $⟨M⟩\in L$. If $M$ accepts no input, $M^{\prime }$ loops forever.

Trace:

Comparison Table: Recursive vs. RE Languages

Key Theorems and Proof Techniques

1. Rice’s Theorem

• Statement: Any non-trivial property of TMs is undecidable.
• Implication: Most "interesting" questions about TMs (e.g., "Does $M$ accept only strings of length 5?") are recursive.

2. S-m-n Theorem

• Statement: For any $m,n\ge 1$, there exists a TM $S$ such that: $S(⟨M⟩,x_1,\dots ,x_n)$ computes $M(x_1,\dots ,x_n)$.
• Use: Enables encoding of multiple inputs into a single TM.

3. Reduction (Many-One)

• Definition: $A{\le }_{m}B$ if there exists a computable function $f$ such that: $w\in A⟺f(w)\in B$.
• Example: Reduce $L_{halt}$ to $\overline{L_{halt}}$ (as in the halting problem proof).

Exam Tip

1. Definitions First: Always start with precise definitions of recursive/RE languages.
   • Bad: "Recursive languages are decidable."
   • Good: "A language $L$ is recursive if there exists a TM that halts on all inputs and accepts iff $w\in L$."
2. Proofs Require TMs: For questions like "Show $L$ is RE," construct a TM and describe its steps.
3. Halting Problem: Know the reduction proof (not just the statement). Examiners love seeing $M^{\prime }$ that diagonalizes over $M$.
4. RE vs. Recursive: Emphasize that RE languages can be "recognized" but not necessarily decided. Use $L_{halt}$ as your go-to example.
5. Real-World Links: Connect to compilers (termination), databases (query planning), or cryptography (hard problems). Even if not asked, this shows depth.

Practice Questions (Self-Check)

1. Short Answer:

   • Why is $\{⟨M⟩\mid M\text{ accepts no input}\}$ not RE?
   • Give an example of a language that is neither recursive nor RE.

2. Proof:

   • Show $L=\{⟨M⟩\mid M\text{ accepts }\epsilon \}$ is recursive.

3. Application:

   • How might a Pathao driver’s route optimizer use RE languages? (Hint: Enumerating possible paths.)

Final Visual: Recursive vs. RE Hierarchy

flowchart TD
    A["All Languages"] --> B["Recursively Enumerable (RE)"]
    B --> C["Recursive"]
    C --> D["Regular/Context-Free"]