What Is Reversible Computing?

Play a film of a bouncing ball backwards and it looks a little odd — but nothing in it is impossible. The ball rises, slows, falls: perfectly legal physics. Now play a film of a calculator computing 3 \times 0 = 0 backwards. The screen shows 0… and then what? The zero could have come from 3 \times 0, or 7 \times 0, or 0 \times 0. The film cannot be rewound, because the computation threw information away.

Reversible computing is the study of computations built entirely from steps that can be rewound — steps that never destroy information. Every state of the machine has exactly one predecessor, so you can run the whole thing backwards, like that film of the bouncing ball. It sounds like a curiosity. It turns out to be one of the deepest ideas in computer science: it sets the ultimate energy cost of computation, it is the reason quantum computers are built the way they are, and it is quietly at work every time a debugger steps backwards to the moment a program went wrong.

Forgetting is a one-way street

A computational step is reversible when you can always deduce its input from its output — in the language of inverse functions, when the step has an inverse. "Add 3" is reversible: whatever came out, subtract 3 and you have what went in. "Multiply by 0" is hopeless: every input maps to 0, and the past is gone.

The same split runs right through the logic gates at the bottom of every computer:

NOT is reversible. Output 1? The input was 0. Output 0? The input was 1. In fact NOT undoes itself — apply it twice and you are back where you started.
AND is not. If an AND gate outputs 0, the inputs might have been 00, 01 or 10 — three different pasts, squeezed into one present. Two bits went in, one bit came out, and one bit of information was destroyed.

Two pictures of the same idea

Draw a gate as arrows from its possible inputs to its possible outputs. A reversible gate's diagram is a perfect pairing — every output is hit by exactly one arrow, so the arrows can be followed backwards. An irreversible gate's diagram has a funnel in it — several arrows crash into the same output, and the reverse direction is ambiguous.

Try it in code

Here is the whole idea in ten lines. stepForward can always be undone by stepBack; crush cannot be undone by anything, because two different inputs produce the same output:

No function uncrush can exist: given the output 0, it would somehow have to return both 4 and 9. The information needed to choose is not stored anywhere — it has been destroyed.

Why anyone cares

So ordinary computers forget things constantly. Why does that matter? Three reasons, and each one is a whole module of this subject:

Energy. Forgetting is not free. A famous result — Landauer's principle — says that erasing one bit of information must release at least a tiny puff of heat, about 3 \times 10^{-21} joules at room temperature. That is the only fundamental energy cost in all of computing: computation itself can be free, but forgetting cannot. A computer built from reversible steps could, in principle, run on almost nothing.
Quantum computers. The laws of quantum mechanics only allow reversible operations (plus measurement). Every quantum circuit is a reversible circuit, so the classical theory of reversible gates is the load-bearing skeleton of quantum computing.
Running programs backwards. Reversible languages, time-travel debuggers that step back to the bug, and simulations that can roll back a mistaken guess — all engineering payoffs of computation that keeps its past.

Strangely — yes. The microscopic laws of physics are themselves reversible: Newton's equations run equally well in either direction, and quantum mechanics evolves states by steps that are perfectly invertible. A film of molecules bouncing around, played backwards, breaks no law of physics. The one-way feel of everyday life (eggs scramble, tea cools, we grow older) is a statistical effect that emerges when trillions of particles are involved — the subject of the second law of thermodynamics. Here is the delicious irony this course lives on: our computers throw information away at every gate, yet they are built on top of physics that never forgets anything at all. Reversible computing asks: what if the computer worked with the grain of physics instead of against it?

Your text editor's undo looks like reversibility, but it is the opposite: the editor saves a copy of the old state before destroying it, then "undoes" by pasting the copy back. That is memory spent to fake reversibility — the destructive step still happened. True reversible computing is stricter and more elegant: no step destroys anything in the first place, so no backup copies are needed — the current state alone determines the entire past. Keep this distinction in mind; the interplay between "keep a journal" and "be genuinely reversible" becomes a major theme when we meet reversible Turing machines.

The road ahead

This first module builds the physics: what information has to do with entropy, and exactly what forgetting a bit costs. Then the subject opens out — reversible logic gates and how to build circuits from them, reversible Turing machines and their space–time bargains, a computer made of bouncing billiard balls, electronic circuits that pour their charge back into the supply, programming languages where every program runs backwards, the bridge to quantum circuits, and finally the outer physical limits of what any computer can ever do.