Theorem: Forward decoder and exact reversible extension

There is a finite NOT–CNOT–Toffoli circuit whose action on the declared forward domain is

It acts identically on internal matter and returns its clean work to zero.

A sufficient total bit-carrier reserve is

A constructive upper bound on elementary NOT, CNOT, and Toffoli gates is

This bound is not asserted optimal.

Proof. On the $2B$ geometric/current-history bits, exchange each string $(g,0)$ with $(f(g),g)$, and fix all other strings. These pairs are disjoint: the first components have different modes, and the second component of the output identifies its input. This defines a permutation.

A transposition of two $N$-bit strings can be implemented along a Gray path of at most $N$ edges by at most $2N-1$ adjacent-string transpositions. Each adjacent transposition is a NOT on one target controlled on the other $N-1$ bits. Convert negative controls with NOT gates, compute the conjunction of the controls with $N-2$ clean work bits, flip the target, and uncompute. This uses at most $4N-5$ elementary gates for $N\ge 2$. Set $N=2B$ and sum over the $2^r-1$ pairs.

Finally, six CNOTs per name copy its basis-coded current location into the blank location-history block. The current and retained-history blocks require $2B+12n$ bits, and the clean conjunction reserve is $2B-2$. The decoder reads $f(g)$, which is precisely the stated outgoing germ with the spent permission.