Reversible Turing Machines

So far we have made circuits reversible — fixed webs of Toffoli and Fredkin gates, all the way up to whole arithmetic units. But a circuit is a snapshot: it computes one function of a fixed number of bits and stops. The general-purpose model of computation is the Turing machine — an unbounded tape, a head, a finite table of rules, running for as long as it likes. So the obvious question: what does it mean for a Turing machine to be reversible? The answer is one clean sentence, and then a surprisingly delicate hunt for rules you can check by staring at the transition table.

The one-sentence definition

Freeze a running Turing machine at any instant and write down everything: the state, the entire tape contents, and the head position. That snapshot is a configuration. The machine's rule table defines a step map — a function sending each configuration to the next one.

An ordinary machine breaks this constantly. Suppose two rules read (A, 0) \to (B, 0, \text{stay}) and (A, 1) \to (B, 0, \text{stay}) — "whatever you see, write 0 and go to B". Two different configurations (state A over a 0, and state A over a 1) now step to the same configuration. Standing in state B looking at that freshly written 0, you cannot say what was there a moment ago. Two pasts have merged into one present — exactly the AND-gate funnel, scaled up to a whole machine.

Local rules you can check by eye

Injectivity is a global property — quantified over infinitely many configurations. Nobody wants to prove that from scratch for every machine. The good news: because a single step only touches one cell, injectivity follows from local conditions on the rule table. The cleanest version is Bennett's quadruple form: split every move into two half-steps, each of which does only one thing.

Each half-step is trivially invertible on its own — a write rule reversed is the write rule (q', s' \to s, q), and a move rule reversed just moves the other way. The only remaining danger is two rules arriving at the same state and becoming indistinguishable there. That gives the checkable criterion:

Read the conditions backwards and they say exactly: "standing in the state you just entered, you can tell which rule brought you here." If a write rule brought you, the symbol under the head names it uniquely; if a move rule brought you, it is the only one.

Worked example: a two-state machine you can run both ways

Here is a complete reversible machine, the NOT-sweep: it marches right along the tape, flipping every bit until it meets a blank \sqcup, then halts. Three rules and a halting rule:

(A, 0 \to 1, B) \qquad (A, 1 \to 0, B) \qquad (B, / \to \text{R}, A) \qquad (A, \sqcup \to \sqcup, H)

Check the conditions. State B is entered by two write rules — but they write different symbols (1 and 0), so in B the symbol under the head tells you which fired. State A is entered by exactly one move rule, H by one write rule. Reversible. Now watch it eat the tape 0110 — and note that every row below is recoverable from the row after it:

Running it backwards is mechanical: in state A (entered by the move rule) step the head left and enter B; in state B read the cell — a 1 means the first write rule fired, so restore the 0 and re-enter A. The reversed rule table is itself a perfectly ordinary Turing machine — the past is computed, not remembered.

Where irreversible machines go wrong

Contrast the eraser: (A, 0 \to 0, B) and (A, 1 \to 0, B), then move on. Both rules enter B writing the same symbol 0 — the fourth condition fails. And sure enough, the configuration "state B, a fresh 0 under the head" has two predecessors. Every merged pair like this is one bit of history destroyed — and by Landauer's principle, one unavoidable puff of heat. A reversible machine's configurations never merge, so its entire run is one long thread you can trace in either direction.

You can state reversibility conditions for classic quintuple rules (q, s) \to (q', s', d) too, but they are slippery: a single rule both writes and moves, so undoing it means "step back, peek at what you find there, and work out which rule could have written it before moving away" — and rules entering the same state with different directions can still collide in subtle ways. Bennett's quadruple trick is the classic move of a good theorist: factor each step into pieces so simple that each is obviously invertible, then all you must police is how the pieces chain together. The same instinct — decompose until invertibility is local — is exactly how we built reversible circuits gate by gate.

It is tempting to read "reversible machine" as "a machine that keeps a journal so it can undo." That is backwards. Reversibility is a property of the transition relation: read the arrows of the step map in reverse, and that reversed relation must be a function — at most one predecessor per configuration. Nothing is logged, nothing is stored; the current configuration alone determines the whole past, because no information was ever destroyed. A machine that journals every step so it can undo is a perfectly good simulation trick (it is next lesson's star, in fact) — but the journal is a cost you pay to fake reversibility, not the thing itself.