Simulating Irreversible Machines

Last lesson gave us reversible Turing machines — but also a worry. Reversibility looks like a straitjacket: no forgetting, ever. Surely most programs need to forget — overwrite a counter, discard a temporary, branch and never look back? If reversible machines could only compute some anaemic subset of problems, this whole subject would be a curiosity. The astonishing answer, found independently by Yves Lecerf (1963) and Charles Bennett (1973): any Turing machine whatsoever can be simulated by a reversible one. Forgetting is a convenience, never a necessity. The price is paid not in what you can compute, but in time and tape — and the trick is one you already know from circuits, now wearing a Turing-machine costume.

The history tape: journal every merge

Take any irreversible machine M. Where does its irreversibility live? Precisely in the moments when two configurations step to the same successor — the merges. At such a moment, one piece of information is destroyed: which predecessor you came from. The fix is almost embarrassingly direct: don't destroy it — write it down.

Build a new machine M' with an extra history tape. It runs M exactly, but every time M takes a step that would merge configurations, M' appends to the history tape a note identifying which rule fired (enough to pick out the true predecessor). Now no two configurations of M' ever collide: even if the main tapes agree, the histories differ. The journaled machine is reversible — run it backwards and each history entry tells you exactly which merge to un-merge, after which the entry itself is un-written.

A run of T steps journals at most T entries, so the simulation costs only a constant factor in time. But hold that thought about the history tape's length — it is about to become the villain of the next two lessons.

The catch: a machine buried in its own diary

There is a snag, and it is the same snag we hit with garbage bits in circuits. When M' halts, the answer is on the output tape — but sitting next to it is a history tape holding up to T entries of journal. That junk is not harmlessly ignorable. If you erase it, you have performed a massive irreversible deletion and gained nothing — you have merely relocated the forgetting from the middle of the computation to the end. If you keep it, every run permanently consumes tape proportional to its running time. A reversible simulation that leaves a diary as long as the computation itself has not really solved the problem; it has written it down.

Bennett's three-phase trick

You have seen the escape before, at circuit scale: Bennett's uncompute trick — compute with garbage, copy out the answer, then run the garbage-maker backwards. Bennett's 1973 insight is that the very same three-phase choreography works on Turing machines, with the history tape playing the role of the garbage bits:

Every phase is reversible, so the whole machine is. And look at what is left standing at the end: the input, the copied output, and acres of clean blank tape. The diary was written — and then reversibly unwritten.

The bill

Tally the costs. Time roughly doubles: you run the computation forwards and then again backwards, with a comparatively cheap copying interlude — a constant factor, entirely tolerable. Space is the wound: at the moment between phases 1 and 3, the history tape holds up to T entries. A computation that ran for a billion steps but only ever used a thousand cells of working tape needs a billion-entry history at its peak. Space O(T) instead of space O(S) is a brutal exchange rate, and fixing it — trading a little recomputation for a much shorter diary — is exactly where the next lessons go: first as a beautiful little pebble game, then as sharp space–time trade-off theorems.

Charles Bennett published the construction in 1973 and it rightly made his name. But the French mathematician Yves Lecerf had proved essentially the same theorem in 1963 — reversible simulation of arbitrary Turing machines, local reversibility conditions and all — in a short paper that then sank almost without trace. Lecerf was interested in a purely logical question (a problem of Post about monogenic systems), said nothing about energy or physics, and moved on to other fields entirely; nobody connected his theorem to computation's thermodynamics until the 1980s, when the reversible-computing community rediscovered the paper and blinked at the date. Bennett, meanwhile, had found the result independently — and seen what it was for: his version came wrapped in the physics (Landauer's principle, the energy cost of erasure) and added the uncompute phase that cleans the history away, which is the part that turns a curiosity into a tool. A good moral for the ambitious: being first is nice, but knowing why the theorem matters is what history remembers.

A classic shortcut suggests itself: "skip phase 3 — the answer is already there after phase 1, just take it and throw the history away." But throwing away is the one move the whole subject forbids: erasing T journal entries is a T-bit irreversible deletion, with the full Landauer heat bill attached. You have not avoided forgetting — you have batched it. Equally tempting and equally wrong: "copy the output after uncomputing" — but phase 3 restores the machine to its start, so by then the output no longer exists anywhere. The order is forced: compute while the answer exists, copy it to safety, and only then unwind. Uncompute is not an optional tidy-up; it is the difference between being reversible and merely postponing the crime.