The Setting
How much work space does a deterministic machine need to reproduce steps of a machine with one work tape and read-only input heads? The simulation of this item cuts the work tape positions , as the addresses to , into blocks of cells, for a positive integer parameter , and follows the run as a sequence of block visits, in each of which a controller word enters one block, runs there and leaves. The visits are grouped into epochs, and a circuit over the epochs is evaluated recursively. The item assembles the simulation from tours of block visits with their epoch circuit, the machine tried at every shift of the blocks, and a space allowance with its bound in terms of .
Uniform Computation in Space
Space is counted in work bits, uniformly over an index set. A stack machine has finitely many states, a read-only head on the public input, which reads each symbol framed by a left and a right endmarker, and finitely many stacks of bits; in each step, from its state, the symbol under its head and the top bit of each stack, it either halts with a label or moves its head, keeps, pushes a bit onto or pops each stack, and changes state, and its work space is the greatest length a stack reaches.✦ For families of words over an alphabet and , , of natural numbers, indexed by in a set , the family is computable from in space on , written , when one fixed stack machine, at every index , reads as its public input and turns , written in binary on a stack, into within work bits, for a constant independent of .✦ A family of values in a finite set is computable from in space on when the family of the positions of the in a fixed enumeration of is.✦
For a map from an index set to , computation reindexed by is computation over in which the index has public input and space bound .✦ A quantity , depending on the index and on arguments , is computable along every reindexing when, for every such and every family on , the values are computable from reindexed by whenever and the arguments are.
A family of natural numbers indexed by is linear in when the first inequality below holds for a constant and every index ✦, and fits in space when the second does, being the bit length of : (1)✦
Tours and Their Epoch Circuit
A reference tour consists of a positive integer , a controller width , a positive number of blocks, an initial controller , an initial word for each block , a selection that names for each controller the block it reads and rewrites, and a visit map that sends a controller and the word of its block to the next controller and the block’s new word.✦ The story of a reference tour is the sequence of scenes , each a controller and a word for every block, that starts at and makes one visit per step.✦ With , and epochs, the final controller of is , the controller after all visits. Controllers and words are natural numbers, and words and controller histories are read as digit strings in base , least significant digit first. The tour has finite word bounds when , every , and a visit by a controller below to a word below yields a controller below and a word below .✦ Replaying block of a reference tour under a transcript , a controller history, from a word gives a sequence of pairs of a word and a verdict: the first pair is , and the pair after steps comes from the pair after steps by one replay step at digit of .✦
An evaluation circuit of width with children per node is a set of nodes, each with a base mark, a head child , children , a number of guessed bits, a first value used at base nodes and a value , together with two local rules: a proposal , a number for each node, coordinate , guess and head value , and an admissibility test , a number for each node, coordinate, guess, child index , head value and child value .✦ The modulus of an evaluation circuit of width with children per node is the largest prime with , where is its outer degree, and its register count is , the number of register contents.✦ A call on an evaluation circuit that guesses bits has the frame price , with , , and the node count, width, children per node and modulus of the circuit.✦
The augmented bit at coordinate of a word of width is the binary digit of at place when , the bit when , and when .✦
The epoch circuit of is the evaluation circuit of width with children per node on the vertices of epoch and column : block columns, a start column and history columns.✦ Its base nodes are the vertices of epoch with ✦, and its first value is for and otherwise.✦ The head child of is for and for ✦; its child of index is for , its head child for , and for .✦ A vertex guesses no bits for and bits for .✦ At a history vertex the round is .✦ The proposal is at a block vertex; at the start vertex it is the augmented bit of the digit of at place in base ; at a history vertex it is the augmented bit of with .✦ The admissibility test is at the start vertex and, at a block vertex, for every child index other than ; for child of the block vertex of block it is the augmented bit of the word reached by replaying block under from for steps; at a history vertex it is the verdict of replaying block under the proposed history from for steps.✦ The value of at is read from the story after visits, as the word of block or as the history of the controllers from there on: (2)✦ The target of is , the last history vertex of the last epoch✦, and the coins per epoch of , written , are, with the frame prices of , (3)✦
A family of evaluation circuits is ready on in space from when its widths and child counts are computable from in space , when its node counts and register counts fit in space , and when its local structure is computable along every reindexing from a node and arguments in range: the base mark, number of guessed bits, head child, first value and children of the node, and the proposal and admissibility test at it.✦ A family of reference tours is runnable on in space from when , , and are computable from in space , when the register counts of their epoch circuits fit in space , and when the initial word of a block, the block selected by a controller and the visit of a controller to a word are computable along every reindexing from the block, the controller and the word.✦
The Machine and Its Trial Sites
A multihead machine with sensor over an input alphabet has a finite set of states with a start state and a halting flag on each state, a finite tape alphabet , one work tape, read-only heads, and a program that maps the state, the symbol under the work head and the symbols under the read-only heads to a new state, a write and move on the work tape and a move of each read-only head.✦ The sensor of presents an input word by giving the initial content of the work tape and, at each integer position, the symbol each read-only head reads. The configuration of on at time is the state, work tape content and head positions reached from the start state, with every head at , after moves of the program, a machine in a halting state staying where it is.✦ The outcome is the state at time with its halting flag, and has halted at time when the flag is set.✦
An offset trial site is a cap , a positive parameter and an offset .✦ With , it cuts the addresses to , shifted by , into blocks of cells, the address lying in the home block . A controller of at cap is a word of bits, made of fields of bits each, which hold the tick (a time from to ), the state, the square of the work head and the squares of the read-only heads. The block tour of on at is the reference tour with parameter , controller width and blocks whose initial controller and block words are those of the configuration at time , whose selection sends a controller to the home block of its work head square, and whose visit runs local steps of on the selected block.✦ The final controller of the block tour is denoted .✦ The site is complete for on when the tick of equals ✦, and the readout is the state of with its halting flag.✦ For a site and a content of the work tape, the word of block is the base packing, least significant digit first, of the codes of the symbols in its cells✦: cell of block has the address and holds the symbol at tape position that address minus when the address lies in to , and has code otherwise.✦ The scene of on at at time is the pair of a controller and block words read off the configuration at time : the controller records the tick capped at , the state, and the squares of the work head and of the read-only heads, a head position giving the address clamped to to , and is the base packing of these fields, least significant first, where is the field width; the word of each block is its stored word under the work tape content.✦
An accessor for is a multitape Turing machine with public input alphabet , outputs in and four argument tapes, for a cap, a head tag, a sign and a magnitude.✦ An accessor for gives access within bits on with cap when, for every head tag , naming the work tape or a read-only head, and every position in , run on with , , the sign of and the magnitude of in binary on its argument tapes, it outputs within work bits the symbol that the sensor of gives on at and .✦ Input words , numbers , sites and a space bound form a resources and access kit for an accessor of when , and are computable from in space , when the register counts of the epoch circuits of the tours fit in space , and when, for a constant , the accessor gives access within bits on with cap at every index .✦ A multitape Turing machine computes the output within bits on given inputs when its run from the start state, with the input heads at the left endmarker and every work tape blank with its head at , halts with output while the head of each work tape stays inside an interval of cells whose total size, each cell counted with the bits needed for a symbol of its tape, is at most .✦
The Space Allowance
For a natural number , the scale factor , the integer , the binary logarithm and the space allowance of degree are (4)
The Claim
Theorem 1. For a reference tour with finite word bounds, the final controller is the digit at place , in base , of the value at the target: (5)✦ Let , , be reference tours with finite word bounds, runnable on in space from . Then (6)✦ If, besides, the family is linear in , then the final controllers are computable: (7)✦
Let be a multihead machine with sensor over . If input words , numbers , sites and a space bound form a resources and access kit for an accessor of , then (8)✦ If, besides, the family of these tours is linear in , then the completion bits , equal to for a site complete for on and otherwise, and the readouts are computable: (9)✦ For an input word , a cap and a positive with , there is an offset for which the site is complete for on : (10)✦ For an input word and a site with cap that is complete for on , the readout is the outcome at time : (11)✦ If has halted on at time and at time , then (12)✦
For a natural number , input words and sites whose parameter is the scale factor of the cap, , the tours satisfy, for a constant and every , (13)✦ For every natural number , (14)✦ and if , then (15)✦ and, for every natural number , (16)✦ For real numbers and there are natural numbers and such that, for every natural number , (17)✦
In the paper, the result reads: Lemma 5, applied to the epoch word graph, the epoch circuit here, with , yields the final history and its controller in space ; the offsets are tried with reused storage; and for an unknown running time the caps are tried until the machine halts.
What Is Checked
The claim is stated over reference tours with their story, final controller and finite word bounds; the epoch circuit with its vertex values, target, modulus, register count and coins per epoch; ready families of evaluation circuits and runnable families of tours, with computation in space uniform over an index set; the multihead machine with sensor and its outcomes; offset trial sites with the machine’s block tour, its completion and its readout; accessors and resources and access kits; and the space allowance with , and . Beyond the claim, the library proves of these constructions that the modulus is prime and that the machine’s block tour meets the conditions of a reference tour, every controller selecting one of its blocks.