The Setting
Cut the work tape of a one-tape computation of steps into blocks and run it as a tour, a sequence of visits: at each visit a controller, a word of bits, selects one block, and the visit turns the controller and the content of that block into an outgoing controller and new content for the block.
A proposed transcript of visits, a list of controllers, can be checked one block at a time. Block needs only its own content at the start and the list: it replays the visits of the list that select and compares each outgoing controller with the next entry. The question is whether these local checks together certify the list, and in what space one replay runs.
Tours and Their Runs
A tour consists of positive integers and , a natural number , an initial controller , initial blocks , a selector that sends every natural number to a block index , and a visit map that sends a controller and a block to a pair of an outgoing controller and a new block, controllers and blocks being natural numbers.✦ The radix of a tour is and its block length is .✦
A tour has finite words when its controllers stay below and its blocks below : , for every , and has and whenever and .✦
The reference run of is its sequence of scenes, a scene being a controller together with a sequence of blocks: the scene at visit is with the blocks , and each later scene comes from the one before by one visit.✦ We write for the controller and for the content of block in the scene at visit .
A natural number is read as a list of controllers through its digits in radix , , least significant first.✦ A natural number agrees with the run from visit for visits when its digits are the reference controllers .✦
Local Replay
The replay of block on a list from a block , for entries, is the pair of a buffer and a flag that starts at and takes at entry the step✦ (1)✦ where is when and otherwise. The replay of block from visit is , and it passes when its flag is .✦
Computation in Space
For families of words over an alphabet and , , of natural numbers, all indexed by a set , is computable from in space over , written , when one stack machine, a finite control with a read-only head on the public input and finitely many stacks of bits as work storage, turns at every index a stack holding the bits of into one holding the bits of , least significant first, on public input and within work bits, for a constant independent of .✦ Along a map , families indexed by are computed over in space : instance has public input and space bound .✦
The pairing of natural numbers and is the number whose binary expansion, least significant bit first, writes every bit of preceded by a , then a , then the bits of .✦
The prime of a tour is the largest prime with , where is the outer degree.✦ The evaluation circuit of , the circuit that evaluates its run, has width and children per node.
A family of tours , , is runnable over in space from parameters when, with , , , , and read in :✦
, , and are computable from in space over ;✦
the bit length of is at most a constant multiple of , one constant for every ;✦
the initial blocks, the selector and the visit map are computable at computable arguments: for every map and families , , indexed by with , and computable from in space over , so is , so is when every , and so is for when moreover every , all in the tour .✦
The Claim
Theorem 1 (Local replay). Let be a tour with finite words and reference run , let be a natural number, and let and be natural numbers.
For every block index and block , the buffer of satisfies (2)✦
If agrees with the run from visit for visits, then for every block index , (3)✦
If and the replay of every block from visit for entries passes, then (4)✦
Let , , be tours with finite words forming a family runnable over in space from parameters , let be a map, and let , , , , be families indexed by such that , , , and are computable from in space over and in the tour for every . Then, with the replay in , (5)✦
In the paper, the result reads: for , the replay scans the controller list , applies the visits that select block to a buffer initialized to and conjoins the bitwise checks, continuing after failures, is total and uses workspace and no word evaluation, and for a proposed list with the reference all replay flags equal one if and only if the list is the reference controller list, in which case each buffer is the reference block after visits, the page’s standing for the paper’s .
What Is Checked
The claim is stated over tours with finite words and their reference runs, lists of controllers read through their digits in radix , agreement with the run, and the replay (1) of a block from a visit, and its fourth part over runnable families of tours, the prime of a tour’s evaluation circuit, the pairing of numbers and computability in space over a family of public inputs along a map of index sets.