Reversible Computing

Reversible computing is a model of computation in which every computational step can be undone — where the machine's state at any time t uniquely determines its state at time t-1 as well as time t+1. The motivation is thermodynamic: Rolf Landauer's principle states that only irreversible operations — those that erase information — necessarily dissipate heat. A reversible computation could, in principle, be performed with arbitrarily small energy expenditure.

The connection to Physical Computation is direct. Conventional Turing machines overwrite tape symbols and thus erase information at every step. Reversible Turing machines, introduced by Charles Bennett in 1973, avoid this by keeping a history tape — they compute forward and backward, erasing their scratch work in reverse. Every function computable by a conventional Turing machine is computable by a reversible one, at the cost of additional space.

The practical engineering relevance has increased with the rise of Quantum Computing, where unitarity — the requirement that quantum evolution be reversible — makes reversibility not a choice but a physical constraint. Quantum gates are inherently reversible; irreversible classical gates like NAND must be compiled into reversible equivalents (Toffoli, Fredkin) before quantum hardware can execute them. The Maxwell's Demon thought experiment, meanwhile, shows that the measurement a demon must perform to sort molecules is where the thermodynamic cost actually lands — information erasure from memory, not the sorting itself. The physics of computation and the thermodynamics of information are the same subject.