Encodings and Enumerators

An encoding of a discrete mathematical object $O$ (a graph, a Turing machine, a polynomial, a proof) is a string $\langle O \rangle$ over some fixed finite alphabet $\Sigma$, produced by an effective, injective procedure: distinct objects get distinct strings, and there is an algorithm that reconstructs $O$ from $\langle O \rangle$. The specific bit-level details of an encoding scheme are never important — what matters is that some reasonable encoding exists, because any two reasonable encodings are interconvertible by a Turing machine in a way that changes no decidability or recognizability question. This is why textbooks freely write things like $\langle G, k \rangle$ for a graph paired with an integer, trusting the reader to accept that graphs, integers, and tuples can all be serialized into one string. When we say a Turing machine $M$ takes "another machine $N$" as input, we mean formally that $M$ receives the string $\langle N \rangle$ and must decode the transition table, state set, and start/accept/reject states from it before simulating $N$. An enumerator is a variant of the Turing machine model equipped with an extra output device — a printer — attached to a second, write-only tape. An enumerator $E$ has no explicit input; it runs forever (or halts) starting from a blank work tape, and periodically it copies the current contents of a work tape onto the printer tape followed by a special separator symbol, effectively "printing" a string. The language enumerated by $E$, written $L(E)$, is the set of all strings that appear on the printer output at some point during the (possibly infinite) run. If $E$ never halts but keeps printing forever, it may still enumerate a language completely, as long as every string of $L(E)$ eventually appears — it is allowed (indeed expected, for infinite languages) that no finite prefix of the run has printed everything. Two enumerators can enumerate the same language while printing strings in wildly different orders, with or without repetition; none of this affects which language is enumerated, only the algorithm's internal behavior. This freedom is what lets an enumerator built from a recognizer use a slow, repetitive strategy (dovetailing) and still correctly enumerate the target language, which is the crux of the main theorem below.

The equivalence between recognizers and enumerators is proved by two explicit constructions, each turning one kind of machine into the other.

Direction 1 — Enumerator ⇒ Recognizer. Given an enumerator $E$ for language $L$, build a recognizer $R$: on input $w$, simulate $E$, and each time $E$ prints a string, compare it to $w$; if it matches, $R$ accepts. If $E$ runs forever without printing $w$ (because $w \notin L$), $R$ simply never halts — which is fine, because recognizers are only required to halt and accept on strings in $L$; they may loop on strings not in $L$.

Direction 2 — Recognizer ⇒ Enumerator (the subtle direction). Given a recognizer $M$ for $L$, we want to build an enumerator $E$ that prints exactly the strings $M$ accepts. The naive idea — go through $w_1, w_2, w_3, \dots$ in the standard order of all strings over $\Sigma^*$, run $M$ on $w_1$ to completion, then on $w_2$, and so on, printing $w_i$ whenever $M$ accepts it — fails, because $M$ might not halt on $w_1$ (recall $M$ is only guaranteed to halt on strings in $L$). The construction would hang forever on the first non-halting input and never reach $w_2, w_3, \dots$, even if they are in $L$. The fix is dovetailing: instead of running each simulation to completion before starting the next, run all of them simultaneously, each for a bounded number of steps, in a carefully staggered order that guarantees every pair $(w_i, \text{step budget } j)$ is eventually tried. ``` ENUMERATOR-FROM-RECOGNIZER(M): // M is a Turing machine (recognizer) for language L. // Produces an enumerator E that prints exactly the strings in L, // each at least once, in some order (possibly with repeats). let w_1, w_2, w_3, ... be all strings in Sigma* in standard order (length order, then lexicographic within each length) for i = 1, 2, 3, ... : // outer counter: "round" i for each pair (p, q) with p + q = i, p >= 1, q >= 1: // p indexes which string, q is the step budget simulate M on input w_p for exactly q steps if M accepts w_p within those q steps: print w_p // if M rejects or has not halted within q steps: do nothing, move on // E never halts (unless L is finite and we choose to stop early, // which is optional and not required) ``` Every string $w_p \in L$ is accepted by $M$ in some finite number of steps $q_0$. The pair $(p, q_0)$ appears at round $i = p + q_0$ in the double loop, so $E$ is guaranteed to print $w_p$ at that round (and possibly again at later rounds, which is harmless). Strings not in $L$ are never printed, because $M$ never accepts them, regardless of how many steps we simulate. Hence $L(E) = L$ exactly. The diagram below shows the dovetailing schedule as a grid: rows are candidate strings $w_p$, columns are step budgets $q$, and the diagonal sweep order is how $E$ actually visits cells.

The core mechanism generalizes far beyond this pair: dovetailing is the standard technique whenever infinitely many potentially-nonhalting processes must all be given a "fair share" of computation. It reappears in constructing the Universal Turing Machine simulation strategy for time-bounded diagonal arguments and in enumerating all provable statements of a formal system.

Correctness of Direction 1 (enumerator ⇒ recognizer). $R$ accepts $w$ exactly when $w$ eventually appears in $E$'s output, i.e., exactly when $w \in L(E) = L$. If $w \notin L$, $E$ never prints $w$, so $R$ never finds a match and runs forever — consistent with $R$ being a recognizer (not necessarily a decider) for $L$. No false accepts are possible since $R$ only accepts on an exact string match against $E$'s genuine output.

Correctness of Direction 2 (recognizer ⇒ enumerator). Let $L = L(M)$.

• Soundness ($L(E) \subseteq L$): $E$ only prints $w_p$ when its simulation of $M$ on $w_p$ reaches an

accepting configuration within the allotted $q$ steps — a genuine, faithfully simulated accept of $M$. Hence every printed string is truly in $L$.

• Completeness ($L \subseteq L(E)$): Fix any $w_p \in L$. Since $M$ recognizes $L$, $M$ halts and accepts

$w_p$ after some finite number of steps $q_0$. The double loop enumerates every pair $(p,q)$ with $p, q \geq 1$ exactly once, organized by increasing sum $i = p+q$; since there are only finitely many pairs with a given sum, every specific pair — including $(p, q_0)$ — is reached after finitely many rounds. At that point $E$ simulates $M$ on $w_p$ for at least $q_0$ steps and detects the accept, so $w_p$ is printed. Together these give $L(E) = L$, establishing the Enumerator-Recognizer Equivalence Theorem: a language is Turing-recognizable if and only if it is enumerable by some enumerator. This is exactly the theorem that justifies the alternate name "recursively enumerable" for Turing-recognizable languages, tying directly into the classification of languages developed alongside Decidable and Turing-Recognizable Languages.

Complexity, honestly. These constructions are about computability, not efficiency — there is no polynomial-time bound to state here, and none is claimed. The dovetailed enumerator can be catastrophically slow: to print a single short string $w_p \in L$ discovered only after $M$ needs $q_0 = 10^6$ steps, $E$ must first complete rounds $1$ through $p + q_0 - 1$, wastefully re-simulating many other candidates from scratch (a naive implementation restarts each simulation at step 1 every round, giving a step count that grows roughly quadratically in the round index for a fixed candidate, i.e., overall super-linear blowup relative to $M$'s own running time). This is an accepted cost: the theorem is purely about which languages are enumerable, not about doing so quickly. A refined version keeps partial configurations across rounds instead of restarting, saving redundant work, but the asymptotic classification (recognizable ⟺ enumerable) is unaffected either way, since we only need some enumerator to exist.

Encoding correctness. For an encoding scheme $\langle \cdot \rangle$ to be sound for these arguments, it must be: 1. Total and effective — an algorithm computes $\langle O \rangle$ from any valid $O$. 2. Injective (up to a fixed canonical form) — distinct objects map to distinct strings, so decoding is unambiguous. 3. Decodable — an algorithm recovers $O$ (or detects "invalid string") from $\langle O \rangle$. Any two encoding schemes satisfying these properties are interchangeable via a computable translation, so no computability result (recognizability, decidability, or the enumerator equivalence above) depends on which reasonable encoding is chosen — only on the fact that some reasonable encoding exists.

Let $L = \{a^n b^n : n \geq 0\}$, over $\Sigma = \{a,b\}$, a classic non-regular but decidable (hence certainly recognizable) language. Take $M$ to be a straightforward Turing machine deciding $L$ by repeatedly crossing off one leading $a$ and one trailing $b$, running in $O(n^2)$ time on inputs of length $2n$ (each pass is $O(n)$, and $O(n)$ passes are needed) — but for this example the exact runtime doesn't matter, only that $M$ halts on every input (accepting strings of the form $a^nb^n$, rejecting all else). Standard order over $\{a,b\}^*$ begins:

so $w_1=\varepsilon, w_2=a, w_3=b, w_4=aa, w_5=ab, \dots$ Only $\varepsilon$ ($n=0$), $ab$ ($n=1$), $aabb$ ($n=2$), etc. belong to $L$. Because $M$ is a decider here (it always halts), the trace is simpler than the worst case, but it still shows the dovetailing schedule concretely. The table shows which round $i=p+q$ first causes $E$ to discover and print each in-language string, assuming (for illustration) that $M$ needs $q_0(w_p)$ steps as listed.

Even though $\varepsilon$ (round 2) and $ab$ (round 9) are far apart in output order, $E$ still reaches each of them eventually because every finite $(p, q_0)$ pair sits on some finite diagonal. The output stream of $E$ is therefore $\varepsilon, ab, aabb, \dots$ interleaved with the many wasted rounds spent on strings never destined to be accepted — those rounds simply produce no printed output and are silently skipped. This matches the general argument: soundness (only true members are printed) and completeness (every member is eventually printed) both hold, exactly as claimed above.

The encoding of machines as data, and the enumerator/recognizer duality, trace back to the founding of computability theory in the 1930s, when the very notion of an "algorithm" had to be pinned down mathematically before anyone could ask what algorithms cannot do.

Encoding schemes are the invisible plumbing behind every system where programs treat other programs as data: compilers parse source code (an encoding of a program) into an abstract syntax tree; virtual machines like the JVM load bytecode (an encoding of a program for a specific machine model) and execute it; version-control and build systems serialize dependency graphs and configuration objects as strings for storage and transmission. The very idea of a Universal Turing Machine — one machine that simulates any other machine given as encoded input — is only meaningful because a robust, decodable encoding convention exists; this is the theoretical seed of every general-purpose computer, which is itself a physical universal machine executing encoded programs. Enumerators show up wherever systems must generate all instances of something without ever declaring "done": web crawlers enumerate reachable pages, theorem provers enumerate consequences of an axiom set, and property-based testing tools enumerate candidate inputs. The equivalence between recognizing and enumerating clarifies a subtle limitation these systems share: a search process that can verify a "success" case is a recognizer, and it can always be turned into a generator of successes by dovetailing — but it can never be upgraded into a machine that also reliably reports failure (halts and rejects) unless extra structure (co-recognizability) is available. This distinction is the direct ancestor of the harder undecidability results explored under Decidable Problems About Automata, where recognizing an automaton property is easy but deciding it, or its negation, can be genuinely impossible.

Ask the tutor: How does the dovetailing idea generalize to build a Universal Turing Machine that simulates any encoded machine on any encoded input?