The Setting
A catalytic small-space computation has, besides its work tape, a large register whose initial contents are arbitrary and which it must hand back unchanged. A recurring task inside such a computation is to decide whether two numbers and , each at most a fixed bound , are equal, when the two can be produced only one at a time.
Here the catalyst is a triple of registers, and the test updates it in four additive steps, each of which involves only one of the two numbers. The question is whether such an update can detect the equality and still be undone.
Registers, Steps and Probes
Fix a natural number , the peak. The bit length of a natural number is when and when .✦ The -th digit of a natural number in base is ✦, and bit of a natural number is . The peak determines the parameters (1)
A proper triple is a triple of natural numbers with (2)✦ Its entries are the three registers of the catalyst: is read through its digits in base as a vector in , as a residue modulo with four digits in base , and as a string of bits.
A number enters through its first digits in base . The digit inner product of numbers and and the mixed inner product of a register with are (3) For a sign , the shifted register is the number below obtained by adding times the digits of to those of , digit by digit modulo : (4)✦
For a sign and natural numbers and , the four steps , , and are the maps on proper triples (5) with the middle entry reduced modulo . Writing and for the signs and , the forward map and the backward map of numbers and are the maps on triples (6)
For a natural number and a position , the flipped number is the number below whose bit , for each , is when and when . For , the probe sends a triple to the bit of at the position given by digit of in base ✦, and the flip is the map on triples that changes that bit: (7)✦
The Claim
Theorem 1 (Restoring equality test). Let be a natural number with the parameters , and of (1), let be a proper triple, and let and be natural numbers. Then (8)✦ If moreover and , and is the middle entry of , then (9)✦ and (10)✦
In the paper, the result reads: if a shared bit vector has arbitrary initial contents, and excursions to two deterministically specified endpoints and return the cursor, with path and result independent of and with nested procedures restoring , then a procedure adds the indicator to a local bit modulo , restores , and needs only constant local data across four endpoint excursions, where and are the numbers written and here.
What Is Checked
The claims (8), (9) and (10) are stated over a peak with the parameters (1), a proper triple (2), natural numbers and , at most in (9) and (10), the forward and backward maps (6) built from the four steps (5) with the inner products (3) and the shifted register (4), and the probes and flips (7).