The word "reversible" is doing two different jobs, and this whole subject balances on telling them apart. Ask a logician whether a step is reversible and they ask: could I deduce the input from the output? Ask a physicist and they ask: could this process actually run backwards, without stirring up heat? The first is a question about functions. The second is a question about friction, resistors and molecules. The miracle — which took until 1961 to see clearly — is that the two questions are joined at the hip.

Logical reversibility: being a bijection

A computational step maps machine states to machine states — it is a function. The step is logically reversible exactly when that function is a bijection: every possible output comes from exactly one input. No output is ambiguous (that would make it impossible to run backwards), and none is unused. A bijection from a finite set of bit-patterns to itself is just a shuffle — it rearranges the patterns without ever merging two into one.

A useful first test needs no truth table at all: count the wires. A gate mapping n input bits to m output bits has 2^n possible inputs and 2^m possible outputs. If m < n, there are more inputs than outputs, so — by the pigeonhole principle — some two inputs must collide, and the gate cannot be reversible. Equal numbers of inputs and outputs is the entry fee; a genuinely reversible gate then has to use its 2^n outputs without any collisions.

Worked example: rescuing XOR

Plain XOR, (x, y) \mapsto x \oplus y, maps two bits to one — irreversible before we even look at the truth table. But watch what happens if we simply keep one of the inputs:

All four outputs are distinct — it is a bijection, a shuffle of the four patterns (in fact it swaps 10 \leftrightarrow 11 and fixes the rest). To invert it, note x \oplus (x \oplus y) = y: applying the very same map again restores (x, y). We have computed XOR and kept enough context to undo it. This little map is the classical seed of the CNOT gate, and "carry your inputs along with you" is the single most important trick in reversible logic.

Now try the same rescue on AND: (x, y) \mapsto (x,\; x \wedge y). Widths match — two bits in, two bits out. But check the table: inputs 00 and 01 both give 00. Still a collision, still irreversible. Keeping x is not enough, because when x = 0 the output x \wedge y wipes out all trace of y. (AND can be rescued — but it takes three wires, and that story belongs to the Toffoli gate.)

Seeing the difference

Here are both two-bit maps drawn as arrows between the four patterns. Reversibility is something you can see: the left diagram pairs patterns off perfectly; the right one has a collision — and one output pattern that nothing maps to at all.

Physical reversibility: no entropy left behind

A process is physically reversible when running it creates no entropy — no organised energy degraded into random heat. A frictionless pendulum is (ideally) physically reversible; a book sliding to a halt is not. Note this is about how a step is carried out, not what it computes: you can implement the humble NOT gate wastefully, burning a million kT of energy per flip — logically reversible, physically a bonfire. Every real chip today does exactly this.

So one direction is easy: logical reversibility does not guarantee physical reversibility. The deep claim runs the other way. A logically irreversible step merges two distinct machine states into one. Physics, microscopically, never merges states — its laws are one-to-one. So the "lost" distinction cannot actually vanish: it must be pushed out of the machine's orderly bits and into the disorderly jiggling of its atoms. Merging computational states forces heat into the environment. That is the argument we make quantitative over the next few lessons, and it lands at Landauer's principle.