A Reversible Instruction Set

We now have fully adiabatic circuits and resonant supplies to feed them. But circuits execute instructions, and here the whole edifice can collapse in one line of assembly: a single MOV that overwrites a register throws away its old value — an erasure the hardware underneath cannot take back gently, however perfect its ramps. If the machine is to be reversible, reversibility must be lifted into the ISA — the contract between hardware and software itself. The classic demonstration is PISA, the instruction set of MIT's Pendulum processor: an ISA in which every instruction is invertible, so any program can be run backwards, step by step, by inverting each instruction in reverse order.

Rewriting the instruction repertoire

Design rule: every instruction must be a bijection on the machine state — old state recoverable from new. Walk the standard von Neumann repertoire with that lens and it splits cleanly:

Arithmetic becomes in-place update. Not r_3 \leftarrow r_1 + r_2 (which destroys r_3's old value) but ADD r_1, r_2 meaning r_1 \mathrel{+}= r_2: knowing the result and r_2, subtraction recovers the past. Its inverse is simply SUB r_1, r_2. NEG (r \leftarrow -r) is its own inverse.
Data movement becomes exchange. MOV copies over a value, destroying it; PISA uses EXCH (swap), a self-inverse shuffle in which nothing is lost. Loads and stores likewise become exchanges with memory.
Bit logic becomes XOR-style update. r_1 \mathrel{\oplus}= r_2 is self-inverse (XOR again and the old value returns); "load a constant" becomes XOR-with-a-constant into a register whose prior contents are accounted for.
Forbidden outright: destructive overwrite in any costume — MOV, CLR, load-with-overwrite, any write that does not preserve enough to reconstruct what it replaced.

; illegal (destroys information) ; PISA style (invertible) MOV r1, r2 ; r1's past gone EXCH r1, r2 ; swap - nothing lost CLR r3 ; r3's past gone ADD r1, r2 ; r1 += r2 (inverse: SUB r1, r2) LD r1, [addr] ; r1 overwritten XOR r3, r1 ; r3 ^= r1 (self-inverse) NEG r1 ; r1 = -r1 (self-inverse)

Worked example: five instructions, forwards then backwards

Start with r_1 = 3,\; r_2 = 5,\; r_3 = 0 and run this little program:

#	instruction	meaning	r1	r2	r3
—	(start)		3	5	0
1	ADD r1, r2	r1 += r2	8	5	0
2	EXCH r2, r3	swap r2, r3	8	0	5
3	ADDI r2, 4	r2 += 4	8	4	5
4	XOR r3, r2	r3 ^= r2	8	4	1
5	NEG r1	r1 = −r1	−8	4	1

Now run it backwards: invert each instruction, in reverse order — last done, first undone:

#	inverse instruction	meaning	r1	r2	r3
—	(end state)		−8	4	1
5⁻¹	NEG r1	r1 = −r1	8	4	1
4⁻¹	XOR r3, r2	r3 ^= r2	8	4	5
3⁻¹	SUBI r2, 4	r2 −= 4	8	0	5
2⁻¹	EXCH r2, r3	swap r2, r3	8	5	0
1⁻¹	SUB r1, r2	r1 −= r2	3	5	0

Back to (3, 5, 0) exactly. Notice the two self-inverse instructions (NEG, XOR) undo themselves, while ADD/SUB and ADDI/SUBI come in mirror pairs. Running a program of n instructions backwards is always the same recipe: P^{-1} = I_n^{-1};\, \ldots;\, I_2^{-1};\, I_1^{-1}.

The control-flow problem: where did you come from?

Data instructions were the easy half. Control flow hides a subtler erasure: after an ordinary jump, the program counter holds the target address — and the machine has forgotten where it jumped from. Two different jump origins landing on one target is a many-to-one merge in the PC, just as fatal as a MOV. Running backwards from the target, which way do you go?

PISA's cure is paired branches: control transfer is annotated at both ends. A jump's target site carries a matching come-from annotation, so that at every point in execution the previous PC value is deducible from the current state — each jump-in is paired with exactly one acknowledged origin, and branch conditions are computed from registers that the branch itself does not disturb. Backwards execution then reads the pairing in reverse: the come-from tells the reversed machine which way the PC must retrace. The bookkeeping echoes everything in this course: what Bennett's histories did for Turing machines and retraction order did for cascades, come-from pairing does for the program counter. Instructions can also be classed expanding (they grow the represented information — e.g. producing a result alongside preserved inputs) or contracting (they consume previously saved information, running an expansion in reverse); a well-formed reversible program balances the two, which is precisely the garbage management story returning at instruction granularity.

Because a pendulum is the physicist's favourite machine that runs the same forwards and backwards: film a frictionless pendulum and the reversed film is indistinguishable from the original — and it swings all day on no energy input, losing only what friction skims. The MIT group (Carlin Vieri, Michael Frank, Tom Knight and colleagues, late 1990s) wanted exactly those two properties in silicon: a processor whose execution could swing either way, built on charge-recovery circuits that, like the pendulum's bob, borrow energy and give it back every cycle. The name is a thesis statement in one word. The project produced real fabricated chips — proof that "reversible computer" names an engineering artefact, not a thought experiment.

"ADD is invertible" has fine print: ADD r_1, r_2 is invertible when the operands are different registers. Try ADD r1, r1 — doubling — in a real w-bit register: doubling shifts the top bit off the end, and modulo 2^w the map x \mapsto 2x sends x and x + 2^{w-1} to the same result. Two pasts, one present: not a bijection. Worse still, XOR r1, r1 always yields zero — a clear instruction in disguise, the very erasure the ISA was built to ban. Reversible ISAs therefore forbid instructions whose source and destination coincide. The general lesson: invertibility is a property of the whole map on machine state, checked case by case — not a sticker an opcode carries with it.