Reversible computation

Reversible computation is the theoretical and practical study of computations that can be run backward — where every step of the forward execution preserves enough information to uniquely determine the prior state. In a fully reversible computer, no information is ever erased; bits are transformed but never destroyed. This is not merely an engineering curiosity: it is the physical foundation of low-energy computation, since information erasure is the thermodynamic operation that costs energy, not the logical transformation itself.

The field was established by Charles Bennett in 1973, who showed that any conventional computation could be translated into a reversible one with only modest overhead. The key primitives are the Toffoli gate and the Fredkin gate — universal logic gates that are their own inverses. A reversible computer must retain intermediate results during forward execution and then uncompute them during backward execution, a process that trades memory (or time) for energy dissipation. The ultimate limit is the Landauer limit: the minimum energy required to erase one bit under a given temperature, approximately kT ln 2. Reversible computation approaches this limit asymptotically, proving that computation is a physical process governed by thermodynamics, not an abstract mathematical free lunch.