Manuscript VIII-B@3 · VIII-B-v3.tex · section · 3aa6baa1
The classical update and permutation extension
A finite algebraic table and reversible realization › The classical update and permutation extension · lines 1961–1988
VIII-B@3#eq:forward-map, VIII-B@3#eq:Q
Define by setting stage to 1, replacing the packet index by , decreasing permission by one, and recomputing reports. Token, clock, incidence mode, and metadata are retained. Prescribe
The number of canonical geometric inputs is
Matter states and name locations are not counted by .
Outputs are distinct because they retain . Input and output sets are disjoint because their first-block stage bits differ. Exchange each input word with its prescribed output and fix every other -bit word. This defines a product of disjoint transpositions.
Retaining input history is the elementary reversible-computation principle associated with Bennett Bennett1973; the gate basis is the classical reversible basis associated with Toffoli Toffoli1980. The bound needed here is proved directly.
Displayed formulas in this passage
VIII-B@3#eq:forward-map · line 1967
VIII-B@3#eq:Q · line 1972