The Setting
A register program computes with registers that hold natural numbers. It changes a register by one at a time, and it consults the input only through the symbol in the input cell whose index a register holds, so that a register is a pointer into the input. Run on with every register zero, such a program produces a number, and the words on which that number is nonzero form a language. The question is whether every language that arises this way lies in the class of languages decided in deterministic logarithmic space when the registers stay below a polynomial in the length of the input.
Machines and the Class
A binary word is a finite sequence of bits✦, and a language is a set of binary words.✦ For an input word of length , the input tape has cells to : cell holds the left endmarker, cell holds the bit for , and cell holds the right endmarker.✦ An input tape symbol is the left endmarker, a bit, or the right endmarker.✦ A head direction is one of the moves left, stay and right.✦
A probabilistic Turing machine with states , binary work tapes and input heads consists of an initial state, a transition function and an output map.✦ The output map gives each state either no verdict or a verdict, accept or reject; the states with a verdict are the halting states. The transition function maps a state, the symbols under the input heads, the bits under the work heads and a coin bit to an action: a next state, a bit to write on each work tape, and a head direction for each work head and each input head.
A configuration of on an input of length consists of a state, a position in for each input head, an integer position for each work head, and the contents of each work tape, a bit at every integer cell.✦ A coin tape is an infinite sequence of bits.✦ The run of on with coin tape is the sequence of configurations in which is the initial configuration of on , with the initial state and every head and tape in its starting position, and is the configuration that the transition function of gives from with coin .✦
The space used through time is the sum, over the work tapes, of the number of distinct cells that the tape’s head visits in .✦ The machine runs in logarithmic space when there is a constant with (1)✦
The machine decides a language when for every word there are a time and a verdict , accept if and reject if not, such that on every coin tape the state of in the run with has verdict .✦ A probabilistic Turing machine is deterministic when its transition function does not depend on the coin bit.✦ The class is the set of languages decided by a deterministic machine that runs in logarithmic space.✦
Register Programs
A store is an assignment of a natural number , the content of register , to every register index ; is the store with every register zero.✦ A store fits below when for every ✦, and it is zero above when for every .✦ Two stores and agree below when for every .✦
Moving register of a store in a head direction gives the store that agrees with off and holds , or at , for the directions left, stay and right.✦ Putting a value into register of gives the store that holds at and agrees with at every other index.✦
A counter command is built by the grammar (2)✦ where is a register index, a head direction and a Boolean test on input tape symbols. The input scan of at a position is the symbol in cell of the input tape when , and the right endmarker when .✦ The test holds at a store when is true on the input scan of at position .✦
For an input and a bound , execution with registers below is the relation between a command and stores and given by the following rules. A step takes to the store obtained by moving register of in direction , when both stores fit below . For a sequence , the command takes to when takes to some and takes to . For commands and , the command takes to when holds at and takes to , or fails at and takes to . For a command , the command takes to when fails at and fits below ; when holds at , it takes to when takes to some and the loop takes to .
Register-computable Expressions
A numeric expression is a function assigning a natural number to every input word and store ✦; a store transformation is a function assigning a store to every and .✦ For a register index , setting register to is the store transformation .✦ A numeric expression is local when there is a such that for every input and all stores and that agree below .✦
There is room for a store transformation at a threshold when there are a counter command and an exponent such that, for every input , every bound and every store that fits below and is zero above , (3)✦ The transformation is operable when there is an such that there is room for at every threshold .✦ A numeric expression is register computable when it is local and, for every register index , setting register to is operable.✦
The Claim
Theorem 1. Let be a register-computable numeric expression and a language such that (4)✦ Then belongs to .✦
The polynomial bound of the question is the bound in (3).
What Is Checked
The claim is stated over the class of languages decided by deterministic machines within the space bound (1), and over register-computable expressions, defined through counter commands (2) executed with registers below as in (3).