The physics module ended with a promise: a computer that never forgets could, in principle, compute for free — even Maxwell's demon only pays when it erases. This module cashes that promise in. We stop talking about entropy and start building hardware: logic gates that never destroy a bit. And the first question is beautifully concrete — what does a reversible gate look like in a truth table?

The answer fits in one sentence. An ordinary gate's truth table may send several input rows to the same output. A reversible gate's table is a shuffle: every output pattern appears exactly once. A reversible n-bit gate is nothing more, and nothing less, than a permutation of the 2^n bit patterns.

Same width in, same width out

First, a ground rule. An AND gate eats two bits and emits one — that alone dooms it, because 4 possible inputs cannot fit into 2 possible outputs without a collision. A reversible gate must have as many output wires as input wires: n bits in, n bits out. Its truth table therefore has 2^n rows, and both the input column and the output column list n-bit patterns.

With the widths matched, reversibility becomes a property you can read off the table: the gate is reversible exactly when no output pattern is repeated — the output column is the input column, reshuffled. Then every output has a unique past, and the table can be read backwards. Here are two 2-bit gates side by side:

Gate G's output column is 00, 11, 01, 10 — all four patterns, each once: a shuffle, hence reversible. Gate H's column is 00, 01, 00, 11 — 00 appears twice and 10 never: two pasts have merged, one pattern is unreachable, and the gate is irreversible. That double symptom always travels together: with 2^n rows on each side, a repeat on the output side forces a gap somewhere else.

Gates are permutations — so use permutation language

"A shuffle of the 2^n patterns" has a proper mathematical name: a permutation of a set with 2^n elements. That identification is worth its weight in gold, because everything you know about permutations transfers instantly to reversible gates — in particular cycle notation.

Take gate G above. Follow a pattern round and round: 01 \to 11 \to 10 \to 01 — a 3-cycle — while 00 stays put. In cycle notation,

Or take the gate you will meet properly in the next lesson, the controlled-NOT: it fixes 00 and 01 and swaps 10 \leftrightarrow 11 — a single transposition (\,10\;11\,). The cycle structure tells you real things at a glance: a gate made of a single transposition undoes itself (do the swap twice and you are home), and gate G applied three times is the identity, because a 3-cycle has order 3.

Seeing a 3-bit gate whole

Three bits give 2^3 = 8 patterns, so a 3-bit reversible gate is a shuffle of eight things. Here is a particularly tidy one, the increment gate: read the pattern as a binary number and add 1, wrapping 111 back to 000. Step through the mapping diagram and watch the bijection assemble — in cycle notation this gate is one single 8-cycle, (\,000\;001\;010\;011\;100\;101\;110\;111\,).

Its inverse is just as easy to name: the decrement gate, subtract 1 mod 8. And notice how you build the inverse's table: read the original table backwards — swap the input and output columns (then sort the rows if you like tidiness). Because a reversible gate's output column contains every pattern once, the swapped table is a legal truth table, and it is the table of the inverse gate G^{-1}.

Closure: reversible gates form a group

Wire the output of one reversible gate into the input of another. Is the combination reversible? Run the argument backwards: undo the second gate, then undo the first. Every composite state still has exactly one predecessor, so yes — composing reversible gates gives a reversible gate. In permutation language this is no surprise at all: a composition of permutations is a permutation.

This closure is what makes the whole enterprise work. A circuit is a long composition of gates — and if each gate is a permutation, the entire circuit is one big permutation of the machine's states, exactly the "every state has one predecessor" condition from the foundations module. Build from reversible parts and reversibility of the whole comes for free.