We now know reversibility costs time and tape. But does it cost power? When you restrict a model of computation — take away nondeterminism, cap the tape, forbid loops — the class of problems it can solve usually shrinks or shifts. Reversibility feels like a heavy restriction: never forget anything, ever. And there is a matching temptation in the other direction — surely a machine that runs backwards as happily as forwards can do something magic, like starting from an answer and rewinding to the question? This lesson settles both hopes and both fears. The punchline is beautifully deflating: as far as computability is concerned, reversibility changes nothing at all — no power lost, no magic gained.

No power lost

The history-tape construction already did the heavy lifting. Take any computable function f, computed by some ordinary machine M. The three-phase simulation yields a reversible machine mapping x \mapsto (x, f(x)), with all working tapes restored to blank. So:

Notice how the two statements click together. A reversible machine's overall input–output map must be injective — each step is injective, and composing injections gives an injection, so two different starting tapes can never end identically. That looks like a real limitation until you see that carrying the input along converts any function into an injective one. The restriction is real but toothless: it dictates the packaging, not the content.

No magic gained: halting stays undecidable

Could the extra discipline help? Reversible machines are so orderly — no merging, a single thread of history — that you might hope their behaviour is easier to predict. In particular, is the halting problem decidable if we only ask it about reversible machines? No — and the proof is a one-line reduction. Given any machine M and input x, build the reversible simulation M' from last lesson. The construction is computable, and M' halts on x exactly when M does — the journaled run tracks the original step for step. A halting decider for reversible machines would therefore decide halting for all machines, which is impossible. The orderliness of reversible runs buys you nothing here: undecidability survives untouched.

No magic gained, part two: running backwards does not invert

The seductive one: "a reversible machine for x \mapsto (x, f(x)) runs backwards mechanically — so feed it f(x) and rewind to recover x! Inverting hash functions, factoring products, breaking crypto…" The flaw: running backwards starts from a configuration, not from an answer. To rewind you need the machine's exact final configuration — the precise halting state, head positions, and the entire tape contents, which after the three phases includes x itself sitting right there next to f(x). If you already have that configuration, there is nothing left to find; if all you have is the value f(x), you do not know which configuration to start the rewind from — and finding a configuration that leads to your answer is exactly the original inversion problem, as hard as it ever was. Reversibility guarantees the return path exists; it does not tell you where the trailhead is.

The shape of a reversible run

Draw every configuration as a dot and every step as an arrow. An irreversible machine's graph has funnels — dots with two or more incoming arrows. A reversible machine's graph has in-degree at most one everywhere, so its runs are clean threads. That simple picture pins down exactly what repeating behaviour is possible:

Suppose a reversible run revisits some configuration: the configuration at step i equals the one at step j > i. Step backwards from both copies. Predecessors are unique, so the configurations at steps i-1 and j-1 are equal too — and so on, marching the pair back in lockstep until the earlier index hits 0. Conclusion: the configuration at step j-i is the start configuration. The run is periodic, an endless loop of period j-i that threads through its own starting point. A cycle that avoids the start is impossible — every configuration on it would need its single predecessor inside the cycle, leaving no way in from outside.