AN ENUMERATOR IS A TURING MACHINE WITH AN ATTACHED PRINTER. It takes NO INPUT. It runs, and from time to time it PRINTS a string. THE LANGUAGE ENUMERATED IS THE SET OF STRINGS IT EVENTUALLY PRINTS. THREE PROPERTIES WORTH STATING IMMEDIATELY: · IT MAY RUN FOREVER — indeed it must, if the language is infinite. · THE ORDER IS ARBITRARY unless the definition requires otherwise. · REPETITIONS ARE ALLOWED. A string printed twice is in the language once; the language is a SET. ── THE THEOREM ───────────────────────────────────────────── A LANGUAGE IS RECURSIVELY ENUMERABLE IF AND ONLY IF SOME ENUMERATOR ENUMERATES IT. THIS IS WHERE THE NAME COMES FROM. "Recursively enumerable" means, literally, "can be listed by a machine" — and the theorem shows that listing and recognising are the same capability viewed from two sides. ── DIRECTION 1: ENUMERATOR → RECOGNISER ──────────────────── THE EASY DIRECTION. Given an enumerator E for L, build a recogniser M: "On input w: run E. Each time E prints a string, compare it with w. If they match, ACCEPT." IF w ∈ L, E EVENTUALLY PRINTS IT, so M accepts in finite time. IF w ∉ L, E NEVER PRINTS IT, so M runs forever — WHICH IS EXACTLY WHAT A RECOGNISER IS PERMITTED TO DO. NOTE HOW THE PERMITTED NON-HALTING IS ESSENTIAL. A decider could not be built this way, because M has no way to know that E will never print w. ── DIRECTION 2: RECOGNISER → ENUMERATOR ──────────────────── THE HARDER DIRECTION, AND THE ONE THAT NEEDS DOVETAILING. THE NAIVE ATTEMPT FAILS. One might write: "For each string s₁, s₂, s₃, … in turn: run M on sᵢ; if it accepts, print sᵢ." THIS IS WRONG. If M loops on s₁, the enumerator is stuck forever and never reaches s₂ — even though s₂ might be in L. A SINGLE NON-HALTING COMPUTATION BLOCKS THE ENTIRE ENUMERATION. THE DOVETAILING FIX: "For i = 1, 2, 3, … run M for i STEPS on each of the first i strings s₁, …, sᵢ. Print any string that has accepted." NO COMPUTATION IS EVER RUN TO COMPLETION IN ONE GO — each gets a bounded number of steps, and the bound grows. WHY IT WORKS: if M accepts sⱼ after exactly k steps, then at round i = max(j, k) the enumerator runs M on sⱼ for at least k steps and sees the acceptance. SINCE max(j, k) IS FINITE, EVERY ACCEPTED STRING IS PRINTED AT SOME FINITE ROUND. ∎ THE COST IS REDUNDANCY — round i redoes all the work of round i−1 — but computability is the question and efficiency is not. ── THE PAIRING THAT MAKES IT WORK ────────────────────────── Dovetailing rests on the fact that PAIRS OF NATURAL NUMBERS CAN BE ENUMERATED. Listing pairs (i, j) by DIAGONALS: (1,1) (1,2) (2,1) (1,3) (2,2) (3,1) (1,4) (2,3) (3,2) (4,1) (1,5) (2,4) (3,3) (4,2) (5,1) … giving the sequence (1,1) (1,2) (2,1) (1,3) (2,2) (3,1) (1,4) (2,3) (3,2) (4,1) … EVERY PAIR APPEARS AT A FINITE POSITION. The pair (i, j) sits on diagonal i + j − 1, at a position that is finite no matter how large i and j are. THIS IS CANTOR'S ARGUMENT THAT ℕ × ℕ IS COUNTABLE, and it is the combinatorial engine behind every dovetailing construction. ── LEXICOGRAPHIC ENUMERATION AND DECIDABILITY ────────────── A SHARPER RESULT that separates the two classes cleanly: A LANGUAGE IS **RECURSIVE** IF AND ONLY IF IT CAN BE ENUMERATED IN LEXICOGRAPHIC ORDER — shortest first, and alphabetically within each length. THE PROOF OF THE USEFUL DIRECTION: Suppose E enumerates L in lexicographic order. To decide whether w ∈ L, run E and watch its output. · If w is printed, ACCEPT. · IF E PRINTS ANY STRING **AFTER** w IN LEXICOGRAPHIC ORDER, then w will never appear — REJECT. · If L is finite and E stops, REJECT. THE ORDERING SUPPLIES A STOPPING CONDITION, and that is exactly what the arbitrary-order enumeration lacked. ∎ SO THE DISTINCTION BETWEEN THE TWO CLASSES REDUCES TO ONE WORD: RECURSIVELY ENUMERABLE — listable in SOME order RECURSIVE — listable in SORTED order AND THE GAP BETWEEN THEM IS THE GAP BETWEEN "IT WILL APPEAR EVENTUALLY" AND "I CAN TELL WHEN TO STOP WAITING".

── ENUMERATION AS A PROOF TECHNIQUE ──────────────────────── Several standard results are proved most easily by constructing an enumerator. CLOSURE OF RE UNDER UNION: Given enumerators E₁ for L₁ and E₂ for L₂, DOVETAIL THEM — alternate steps of each, printing whatever either prints. The result enumerates L₁ ∪ L₂. RUNNING E₁ TO COMPLETION FIRST WOULD FAIL, since E₁ may never finish. CLOSURE OF RE UNDER INTERSECTION: Enumerate L₁ and L₂ simultaneously, keeping two growing lists, and print any string that appears in both. EVERY INFINITE RE LANGUAGE HAS AN INFINITE RECURSIVE SUBSET: Enumerate L and print only those strings LONGER than every string printed so far. The resulting subset is enumerated in increasing length order, hence recursive by the result above. A LANGUAGE AND ITS COMPLEMENT BOTH RE ⟹ RECURSIVE: This is the complementation theorem of the acceptance topic, and dovetailing is again the mechanism. ── THE CONNECTION TO COUNTABILITY ────────────────────────── An enumerator establishes that a language is COUNTABLE — it puts the strings in correspondence with the natural numbers. SINCE Σ* IS COUNTABLE, EVERY LANGUAGE IS COUNTABLE AS A SET, so countability alone is not the issue. THE ISSUE IS WHETHER THE LISTING CAN BE PRODUCED BY A MACHINE. · Σ* itself is enumerable — list by length, then alphabetically. · The set of all TURING MACHINES is enumerable — encode each as a string and list those strings. · The set of all LANGUAGES is NOT — it is uncountable, by Cantor's diagonal argument. SO THERE ARE UNCOUNTABLY MANY LANGUAGES AND ONLY COUNTABLY MANY ENUMERATORS, WHICH IS THE COUNTING PROOF THAT NON-RE LANGUAGES EXIST, restated in the vocabulary of this topic. ── A CONCRETE ENUMERATOR ─────────────────────────────────── ENUMERATING { aⁿbⁿ : n ≥ 0 }: "For n = 0, 1, 2, 3, … print aⁿbⁿ." Output: ε, ab, aabb, aaabbb, … NOTE THAT THIS IS IN LEXICOGRAPHIC ORDER BY LENGTH, which confirms — by the theorem above — that the language is RECURSIVE. And indeed it is: the Turing machine of the earlier topic always halts. ENUMERATING THE SET OF THEOREMS OF A FORMAL SYSTEM: "Systematically generate every finite sequence of formulas. For each, check whether it is a valid proof — a MECHANICAL check. If so, print its last line." THIS IS THE CLASSICAL EXAMPLE, and it is why the theorems of arithmetic form a recursively enumerable set: PROOFS CAN BE CHECKED MECHANICALLY EVEN THOUGH THEY CANNOT BE FOUND MECHANICALLY. GÖDEL'S INCOMPLETENESS THEOREM IS THE STATEMENT THAT THIS SET IS NOT ALL TRUE STATEMENTS — and the undecidability of the halting problem is its computational twin. ── THE SUMMARY ───────────────────────────────────────────── RECOGNISING and ENUMERATING are the same power. DECIDING is strictly more. AND THE DIFFERENCE HAS A CRISP FORM: AN ENUMERATOR IN ARBITRARY ORDER TELLS YOU WHAT IS IN THE LANGUAGE BUT NEVER WHAT IS OUT OF IT; AN ENUMERATOR IN SORTED ORDER TELLS YOU BOTH, BECAUSE PASSING w WITHOUT PRINTING IT SETTLES THE QUESTION.