The Setting
Take a machine with one work tape and read-only heads, run for steps on an input word . In that time its work head stays among the positions in , written as the addresses to . Shift the addresses by an offset and cut them into blocks of cells, for a block parameter . A visit runs while its work head stays in one block, with the rest of the configuration kept in a controller of some number of bits, and the run becomes a sequence of visits, each to the block that holds the work head. The question is whether these visits reproduce the run, and how many of them it takes to reach time for some offset. Selecting the block and making a visit are to be computable in small space.
The machine is a multihead machine with sensor over an input alphabet : it has a finite set of states with a start state and halting states, a finite tape alphabet , read-only heads, and a program that maps the state and the symbols under all heads to a new state, a symbol to write and a move for the work head, and a move for each read-only head.✦ Its sensor presents the input word , giving for the work tape or a read-only head and an integer position the symbol of found there: the initial content of the work tape, or what that head reads. The configuration of on at time is its state, its work tape with the head position, and its read-only head positions after steps from the start state with all heads at ; a step in a halting state changes nothing.✦
A block site consists of a time bound , a block parameter and an offset ; its blocks have slots, and there are of them.✦ The home block of an address in at is the block , in which sits at slot ; slot of block holds the address when this lies in .
Scenes, Visits and Tours
Fix enumerations of and , whose positions are the codes of states and symbols, and let be the bit length of .✦ The controller of on at time is the number whose fields of bits, least significant first, hold the tick , the code of the state, the address of the work head and the addresses of the read-only heads, a position having the address clamped to . A controller has bits, and is the block radix. The block word of block at time is the -digit number in base whose digit is the code of the symbol in the cell at address , and when slot holds no address.✦ The scene at time is the pair of and the sequence of block words.✦
The block of the head at time is the home block of the work head’s address at time .✦ The crossing count is the number of steps before that change the block of the head: (1)✦
A controller records, in its fields, a tick , a state, a work head address and read-only head addresses.✦ The selected block of a controller is the home block of at .✦ The local step on block is the map on pairs of a controller and a block word that leaves the pair unchanged unless and , and acts as follows when both hold.✦ It makes one move of in the recorded state, reading under the work head the symbol coded by digit of , and under each read-only head the symbol the sensor gives at its address.✦ It returns the controller with the tick raised by one, the new state and each head address moved one cell in its direction within , together with with that digit replaced by the code of the written symbol. The sweep of steps from a controller and a block word is the -fold iterate of the local step on the block that selects, and the visit is the sweep of steps: (2)✦
A block tour with parameters , and consists of an initial controller, an initial block word for each index, a selector mapping controllers to block indices below , and a visit map mapping a controller and a block word to a controller and a block word; its radix is and its blocks have digits.✦ A scene of the tour is a controller together with a block word for each index .✦ The step of the tour sends a scene to the scene obtained by visiting the selected block and writing it back: (3)✦ The story of a block tour is the sequence of scenes of the tour in which is the initial controller with the initial block words and .✦ The tour of on at is the block tour with the parameters , and of , initial scene , selector and visit map ; denotes the controller of its scene .✦ In a block tour with parameter , an epoch is a group of visits, and the first visits make up its epochs.
Computing in Small Space
For families indexed by of words and numbers , and , the family is computable from in space , written , when one fixed stack machine, at every index , reads as its public input and turns a stack holding the bits of into one holding the bits of , least significant first, within work bits, for a constant independent of .✦ The pair of two numbers is the number whose binary digits, least significant first, are those of , each preceded by a , then a , then those of .✦
A multitape Turing machine gives access within bits on when, for the work tape or a read-only head and every position , it computes within work bits, from public input and, in binary on its argument tapes, , the head and the sign and magnitude of , the symbol the sensor of gives for that head at .✦
Let be the largest prime with for , the prime modulus of the circuit of width that evaluates the story of the tour of on at over the field of elements.✦ Families , , and block sites form a kit for with an accessor machine when , and are computable from in space , the bit length of is at most a constant times , and gives access to the sensor within bits for a constant .✦
The Claim
Theorem 1. Let be a multihead machine with sensor, an input word and a block site, with scenes , block of the head , crossing count and block radix . The tour of on at has bounded words: (4)✦ If and , then (5)✦ If and , then for every there is a time with and (6)✦ If , there is a time with and (7)✦ For every there is a time with (8)✦ For every and every , (9)✦ If , there is an offset with (10)✦ Let finally families , , and form a kit for with an accessor machine , and let be a family of numbers with . Then (11)✦ If moreover is a family of numbers with , and , with the block radix and the number of digits of a block at , and is the visit of on , then (12)✦
In the paper, the result reads: some offset has at most block crossings in the capped computation, and for it at most visits reach the halt or timeout; for every offset there are total maps and on raw words, standing for and , such that a visit changes only the selected block, agrees with the capped computation on represented actual data, and is computable in work bits.
What Is Checked
The claim is stated over the scenes of on at a block site , the crossing count (1), the local step and the visit (2), and the tour of on at with its step (3) and its story; (11) and (12) are stated over computability in space under a kit. The library also states, for the sweep started from the scene at time on the block that its controller selects, that each iteration advances the simulated run by exactly one tick as long as neither time nor a block crossing has been reached, that once the head leaves block the sweep rests at the scene just after that crossing, and that no block other than is changed.✦