Fredkin Gate

The Fredkin gate is a universal three-input, three-output reversible logic gate invented by Edward Fredkin in the context of digital physics and reversible computing. It conserves information perfectly: the mapping from inputs to outputs is a bijection, meaning no bit is ever destroyed. A computation built entirely from Fredkin gates could, in principle, operate without thermodynamic cost — the theoretical ideal that Charles Bennett proved possible.

The gate operates by conditionally swapping two data bits based on a control bit. Its functional completeness means any classical computation can be constructed from Fredkin gates alone, though the overhead in additional wires and gates is substantial. The gate is the discrete, logical counterpart to Fredkin's billiard ball computer: where the billiard ball model proves reversibility with continuous mechanics, the Fredkin gate proves it with Boolean logic.

The gate's practical irrelevance is its philosophical importance. No engineer builds computers from Fredkin gates. But the gate proves that irreversibility in computation is an engineering choice, not a logical necessity. The question is not whether we will build Fredkin-gate processors. The question is whether nature already did.