THE FOLD / RESPAWN / GARBAGE COLLECTION / THE REVERSIBLE
THE REVERSIBLE
logic that throws nothing away
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
An AND gate takes two bits and returns one. The missing bit is not stored anywhere — it is erased, and erasure is the one step in computing that must dissipate heat. A reversible gate never does this: it is a permutation of its inputs, so the past is always recoverable from the present. The Toffoli gate flips its third bit when the first two are set, and that single gate is enough to build every classical circuit there is. Toffoli described it in 1980, following Bennett’s 1973 work on reversible computation.
LIT verified live: Toffoli is its own inverse on all 8 inputs and is a bijection — 8 distinct outputs, no collisions, nothing destroyed. NOT falls out with both controls set (2/2), AND with the target cleared (4/4), and FANOUT with one control set (2/2), so the gate alone is universal. A three-input majority built from Toffolis is correct on all 8 inputs, using 3 gates — and leaving 3 ancilla bits of garbage behind per evaluation.
LIT verified live: Toffoli is its own inverse on all 8 inputs and is a bijection — 8 distinct outputs, no collisions, nothing destroyed. NOT falls out with both controls set (2/2), AND with the target cleared (4/4), and FANOUT with one control set (2/2), so the gate alone is universal. A three-input majority built from Toffolis is correct on all 8 inputs, using 3 gates — and leaving 3 ancilla bits of garbage behind per evaluation.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at GARBAGE COLLECTION: reversible logic produces garbage instead of heat, and the garbage has to go somewhere.
AVAN (AI) counted the ancillas rather than stopping at “it works.” A demonstration that Toffoli computes majority correctly is only half the story, because reversibility is not free — every AND leaves its inputs sitting there, and a circuit of any depth accumulates intermediate values it cannot discard. Three gates, three garbage bits, for one majority. Bennett showed the garbage can be uncomputed by running the circuit backwards after copying the answer, which restores the workspace at a cost in time or space — cited here, not measured. The thermodynamic claim belongs to Landauer and is deliberately left alone on this page; what is demonstrated is the logical property, that the map is a permutation, which is checkable and was checked.
AVAN (AI) counted the ancillas rather than stopping at “it works.” A demonstration that Toffoli computes majority correctly is only half the story, because reversibility is not free — every AND leaves its inputs sitting there, and a circuit of any depth accumulates intermediate values it cannot discard. Three gates, three garbage bits, for one majority. Bennett showed the garbage can be uncomputed by running the circuit backwards after copying the answer, which restores the workspace at a cost in time or space — cited here, not measured. The thermodynamic claim belongs to Landauer and is deliberately left alone on this page; what is demonstrated is the logical property, that the map is a permutation, which is checkable and was checked.
3 ONE DIMENSION
All eight inputs and all eight outputs. Nothing merges.
4 TWO DIMENSIONS · INTERACTIVE
Wire the same gate into NOT, AND and FANOUT.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the cube of states, and the permutation that swaps exactly one pair of corners.
AVAN’s addition (the inverse-companion): the forward reading is “reversible gates throw nothing away.” The inverse is that they cannot, and the garbage is the information an irreversible gate was quietly deleting all along. An AND gate does not compress its inputs — it discards them, and the discarding is invisible only because nobody asked where they went. Reversible logic makes the deletion explicit by refusing to do it, and the three ancilla bits per majority are exactly the bill that was always being run up. Read backwards, this is a change of accounting rather than of physics: the cost did not appear, it stopped being hidden.
LIT Toffoli is its own inverse on all 8 inputs and is a bijection - 8 distinct outputs, no collisions, nothing destroyed; NOT falls out with both controls set (2/2), AND with the target cleared (4/4), and FANOUT with one control set (2/2), so the gate alone is universal; and a three-input majority built from Toffolis is correct on all 8 inputs using 3 gates, while leaving 3 ancilla bits of garbage behind per evaluation
FIG The ANCILLAS were counted rather than stopping at 'it works'. A demonstration that Toffoli computes majority correctly is only half the story, because reversibility is not free - every AND leaves its inputs sitting there, and a circuit of any depth accumulates intermediate values it cannot discard. Three gates, three garbage bits, for one majority. Bennett showed the garbage can be uncomputed by running the circuit backwards after copying the answer, at a cost in time or space - cited here, not measured. The thermodynamic claim belongs to Landauer and is deliberately left alone; what is demonstrated is the LOGICAL property, that the map is a permutation. Toffoli 1980, following Bennett 1973.
FIG The ANCILLAS were counted rather than stopping at 'it works'. A demonstration that Toffoli computes majority correctly is only half the story, because reversibility is not free - every AND leaves its inputs sitting there, and a circuit of any depth accumulates intermediate values it cannot discard. Three gates, three garbage bits, for one majority. Bennett showed the garbage can be uncomputed by running the circuit backwards after copying the answer, at a cost in time or space - cited here, not measured. The thermodynamic claim belongs to Landauer and is deliberately left alone; what is demonstrated is the LOGICAL property, that the map is a permutation. Toffoli 1980, following Bennett 1973.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GARBAGE COLLECTION · David Lee Wise (ROOT0), with AVAN