Computability
Recursive and Recursively Enumerable Languages
Цели урока
- Distinguish Recursive from RE: decider vs recognizer, halting guarantee
- Understand the theorem Recursive = RE intersect co-RE and its proof via parallel simulation
- Explain the dovetailing technique and why it is needed for enumerators
- Apply the classification to concrete problems: halting problem, theorems, syntax
Предварительные знания
Facebook, 2012. The security team built Infer - a static analyzer for null dereference bugs in Instagram's Java codebase. Infer finds bugs. On complex loops, it sometimes hangs. Not a bug in Infer: for arbitrary code, a decidable detector does not exist. The boundary between RE and Recursive is the boundary between 'sometimes hangs' and 'always answers'.
- **Static code analysis:** tools like ESLint/SonarQube operate on decidable subsets of checks. Full verification is undecidable
- **Anti-spam/antivirus:** an RE-style approach - if a virus is found, report it. Not finding one does not mean it is absent. A decidable detector cannot exist
- **Theorem provers:** for some theories (Presburger arithmetic) verification is decidable. For full arithmetic - only RE
Kleene, Post, and the Birth of the Recursive Hierarchy
In 1943, Emil Post of City College of New York published a paper on 'normal systems' - an equivalent of Turing machines. He was the first to introduce the recursively enumerable set and to prove that sets exist that are RE but not recursive - well before anyone connected it to the halting problem. Stephen Kleene formalized recursive functions the same year. Together they laid out what is now called the Post hierarchy - a complete classification of languages by computability, still studied today.
Recursive (Decidable) Languages
**The ideal judge: hand it any question and it ALWAYS answers 'yes' or 'no'.** Never hangs, never wanders off to think forever. That is how a Turing machine behaves for a **decidable** (recursive) language.
**A recursive (decidable) language** is a language L for which there exists a TM M (a decider) such that: for every w in Sigma*, M(w) = accept if w in L, and M(w) = reject if w not in L. The key property: M **always halts**.
Decidable languages are the friendly class. For them, a program can produce a definitive answer for **any** input in finite time. Every everyday programming problem (sorting, searching, parsing) maps to a decidable language.
| Language | Decidable? | Decider |
|---|---|---|
| {a^n b^n | n >= 0} | Yes | Count a's and b's, compare |
| {w | w is valid JSON} | Yes | A JSON parser |
| {G | G is a connected graph} | Yes | BFS/DFS |
| {M, w | M halts on w} | No! | The halting problem |
**Important closure property:** decidable languages are closed under union, intersection, complement, and concatenation. If L1 and L2 are decidable, so are L1 union L2, L1 intersection L2, complement of L1, and L1L2.
How does a decider differ from a recognizer?
Recursively Enumerable (RE) Languages
**The unreliable judge:** if the answer is 'yes', it will eventually say so. If the answer is 'no', it may deliberate forever and the result never arrives. That is a **recursively enumerable** (RE) language.
**A recursively enumerable language** (RE, Turing-recognizable) is a language L for which there exists a TM M such that: M(w) = accept if w in L, and if w not in L then M may reject OR loop forever.
**The 'yes'/'no' asymmetry** defines RE languages. Membership can be confirmed (if a string is in the language, the machine eventually accepts), but non-membership cannot be refuted (if it is not in the language, the wait runs forever).
| Language | Class | TM Behavior |
|---|---|---|
| {w | w is a palindrome} | Recursive | Always accept/reject |
| {M, w | M(w) halts} | RE but not Recursive | accept or loop |
| {M, w | M(w) does NOT halt} | co-RE but not RE | reject or loop |
| {M | L(M) = Sigma*} | Neither RE nor co-RE | No TM exists at all |
The language A_TM = {<M, w> | TM M accepts string w}. Why is it RE but not decidable?
Complement and the RE-Recursive Connection Theorem
A compact result: if a system can both confirm and refute membership of any string in a language, it can **decide** that language. Formally: a language L is recursive iff both L and its complement L-bar are recursively enumerable.
**Theorem:** L in Recursive if and only if L in RE and L-bar in RE. In other words: Recursive = RE intersect co-RE.
The trick in the second direction is **parallel simulation**. Steps of M1 and M2 interleave (one step of M1, one step of M2, ...). Since w belongs to either L or L-bar, one of the machines is guaranteed to halt.
Corollary: if L in RE but L not in Recursive, then **L-bar not in RE**. The complement of the halting problem - the language of non-halting programs - is not even recursively enumerable. No program can reliably detect infinite loops.
| Language L | L in RE? | L-bar in RE? | L in Recursive? |
|---|---|---|---|
| {w | w is a palindrome} | Yes | Yes | Yes (RE intersect co-RE) |
| Halting problem | Yes | No | No |
| Complement of Halting | No | Yes | No |
| {M | L(M) = Sigma*} | No | No | No |
**Practical implication:** writing a program that reliably detects infinite loops in arbitrary code is impossible. The language of 'looping programs' is not even RE - not even a partial recognizer exists.
L is RE but not recursive. What is true about its complement L-bar?
Enumerators and Dovetailing
Why 'recursively **enumerable**'? Because elements can be **enumerated** - printed one by one. Not necessarily in order, not necessarily without repetition, but every element shows up in the list eventually.
**An enumerator** is a TM with a printer. It runs indefinitely and periodically prints strings. The language of an enumerator is the set of all strings it ever prints. Theorem: L is recursively enumerable if and only if there exists an enumerator for L.
**Dovetailing** simulates infinitely many computations in parallel. At step k, each of the first k computations advances by one step. The instant any of them terminates, the system catches it.
Without dovetailing, the naive approach runs M1 and waits. If M1 loops, **nothing** ever reaches M2. Dovetailing solves this by distributing time fairly across every computation.
RE (recursively enumerable) and Recursive are the same thing - just different names
Recursive is a strict subset of RE. Every recursive language is RE, but there are RE languages that are not recursive (e.g., the halting problem). The key difference: for recursive languages the TM always halts; for RE it may loop on 'no' inputs
Recursive = RE intersect co-RE. A language is recursive if and only if both it and its complement are RE. The halting problem is RE but its complement is not - that is why it is RE but not recursive.
Why is dovetailing necessary when enumerating an RE language?
Key Ideas
- **Recursive (decidable):** a TM decider always halts. Closed under all operations, including complement
- **RE (semi-decidable):** a TM may loop on 'no'. Asymmetry: membership confirmed, non-membership cannot be refuted
- **Recursive = RE intersect co-RE:** a language is decidable iff both it and its complement are RE. Running two TMs in parallel yields a decider
- **Dovetailing:** a technique for interleaving infinitely many computations so that no looping machine blocks the others
Related Topics
Classifying languages by computability is the foundation for understanding the limits of algorithms:
- Turing Machine — The formal model through which the RE and Recursive classes are defined
- Computable Functions — Total computable functions correspond to decidable languages; partial computable functions to RE
- Chomsky Hierarchy — RE languages = Type 0 in the hierarchy; context-free and regular languages are strict subsets
Вопросы для размышления
- Why does running two RE recognizers in parallel (for L and L-bar) yield a decider? What guarantees that one of them will halt?
- How does dovetailing relate to the concept of fair scheduling in operating systems?
- If the halting problem could be solved - what practical developer tools would become possible?
Связанные уроки
- comp-02 — Formal TM model - the foundation on which decider and recognizer are defined
- comp-01 — Computable functions: total functions correspond to Recursive, partial to RE
- comp-04 — Reductions between languages build on the RE/Recursive classification
- fl-01-intro — Chomsky hierarchy: RE = Type 0, the top of the formal language tower
- fl-20-church-turing — Church-Turing thesis defines the ceiling of the Recursive class
- cplx-01 — P and NP sit inside Recursive - useful contrast for perspective
- alg-01 — An algorithm guaranteed to terminate = decider. One without that guarantee = recognizer