The Setting
A space bound speaks of a family of computations. A function is computable in space when there is one machine and one constant such that on every input the machine computes and its work storage stays within the constant times , the read-only input not being counted. The library takes the family over an arbitrary index set . At index the machine reads a public input word under the budget ; it is handed a number in binary and must leave a number .
The machine is a deterministic stack machine, with read-only heads on the public input word and on argument words of bits, and with finitely many stacks of bits as its work storage; space is the length a stack reaches. The stacks of a machine are of two kinds: port stacks, which carry the data in and out, and hidden stacks, which are empty at the start and at the end.
Stack Machines
A head direction is one of the three moves (left), (stay) and (right).✦ A symbol with endmarkers over an alphabet is a symbol of , the left endmarker or the right endmarker .✦ A head on a word over stands at a position , and the mark it reads there is (1)✦ A head at position on moves by a direction: leaves it at , takes it to but leaves it at , and takes it to unless , on the right endmarker, where it stays.✦
The machine inputs over an alphabet with argument tapes indexed by a set consist of a public input word and an argument word for each , all of them read-only.✦ The input head positions are a position for the head on and a position for the head on each , all equal to in the home position, where every head starts.✦ At the heads read the marks and , , of (1).✦ An input head advance is a direction for each head✦, and advancing the heads by it moves each one on its own word✦.
A stack is a word over read from the top, and is the empty stack. A stack operation is keep, push for a bit , or pop, four operations in all✦, acting on a stack by (2)✦
A store for argument tapes indexed by and stacks indexed by a set , the stacks and head positions of a machine, consists of input head positions and a stack for each .✦ The top of stack of is the first bit of , or nothing when is empty.✦ A stack change for argument tapes indexed by and stacks indexed by consists of an input head advance and a stack operation for each .✦ Performing a stack change on a store over machine inputs advances the heads of on by the input head advance of the change and applies to each the stack operation of the change for , by (2).✦
A stack machine with input alphabet , argument tapes indexed by , stacks indexed by and halting labels in a set consists of a finite set of states, a start state and a transition table .✦ Given a state, the marks under the input heads and the top of each stack, either halts with a label in or prescribes an action: a stack change and a next state.
Runs Within a Space Bound
A configuration of is a pair of a state and a store.✦ The step of on machine inputs at consults at , at the marks under the heads of and at the tops of the stacks of . The step halts with a label when halts with there; when prescribes an action, the step moves to , with the next state of the action and the result of performing the change of the action on over .✦ A store fits within bits per stack when each of its stacks has length at most .✦
A deterministic halting run of a map , which at each configuration either halts with a label or moves to a next configuration, from to with label under an invariant , is a chain (3)✦ in which moves each to and halts at with label , every , the last included, satisfying . A bounded run of on within bits is a run (3) of the step of on under the invariant that the store fits within bits per stack.✦ An execution of on within bits per stack from a store to a store with label , written , is a bounded run from to with label for some state .✦
The initial store with stack contents has every head at home and on stack .✦ For a store with stacks indexed by and a set , the store with extra stacks indexed by has the head positions and the stacks of and an empty stack for each .✦ A number as a stack is the initial store with no argument tapes and a single stack holding the binary digits of , least significant on top and without leading zeros.✦ A word over as public input is the machine inputs with on the public tape and no argument tapes.✦
The Definition
Definition 1. Let be a set and a family of natural numbers indexed by , the space bound. Let be a family of machine inputs over with argument tapes indexed by , and families of stores with port stacks indexed by , and a family of labels in , all indexed by . The families , , and form a stack computation in space when there are a finite set of hidden stacks, a stack machine with input alphabet , argument tapes indexed by , stacks indexed by and halting labels in , and a constant such that (4)✦ The case of a single port stack is the computation of one number from another. For a family of words over and families and of natural numbers indexed by , is computable from in space on public input when there are a finite set of hidden stacks, a stack machine with input alphabet , no argument tapes, one port stack besides those in and the single halting label , and a constant such that (5)✦ A family of natural numbers indexed by is linear in when there is a constant such that (6)✦ A family of natural numbers indexed by satisfies the bit length bound for when its bit lengths , the numbers of binary digits of the , are linear in , that is, when there is a constant such that (7)✦
What Is Checked
The definitions (4) and (5) are stated over stack machines with read-only heads and stacks of bits, their executions within a bound on the length of every stack, stores extended by empty hidden stacks, numbers written in binary on one stack and words given as public input; (6) and (7) are stated over families of natural numbers alone.