The Setting
The library measures space in a calculus of stack machines, which compute a number from a number on a public input, uniformly over an indexed family of instances. Space-bounded complexity states its theorems for Turing machines with read-only input tapes and work tapes, space counted in work bits. The question is whether the first compiles to the second: when the number computed is the code of a label from a finite set, is there one multitape Turing machine that reads the starting number in binary on a read-only argument tape, or reads only the public input when that number is , and halts with the label within a constant times the same space?
Read-only Inputs and Turing Machines
A head direction is one of left , stay and right ✦; its displacement is , and ✦. A read-only head on a word over an alphabet sees between a left endmarker and a right endmarker ✦, and the mark read at a position is (1)✦ Moved left, a head at goes to ; moved right, it goes to unless , where it stays on the right endmarker; under it stays.✦
The machine inputs over with argument tapes indexed by a set are a public word over and, for each , an argument word of bits, written .✦ For a natural number , is the word of its binary digits, least significant first, without leading zeros. For a public word over and a function , the machine input with binary arguments is .✦ The word as public input is the machine input with public word and no argument tapes.✦
A multitape Turing machine over a public input alphabet , with binary argument tapes indexed by and outputs in a set , consists of a finite set of states with a start state , a finite set of work tapes, for each a finite alphabet with a blank symbol, and a transition table.✦ Given the state, the marks under the input heads (one head on the public word and one on each argument word) and the symbol under each work head, the table either halts with an output in or prescribes an action: a next state, a direction for each input head, and for each work tape a symbol to write and a direction to move.
Work tapes are two-way infinite: a work tape over is a content with a head position ✦, and writing and moving in direction replaces by and puts the head at ✦. A configuration of consists of the state, the positions of the input heads and the work tapes.✦ The initial configuration has state , every input head at on the left endmarker, and every work tape blank with its head at .✦ A step applies the table to the current configuration; it halts with the output the table gives, or enters the next state of the action, with the input heads moved and each work tape written and moved as it prescribes.✦
Let be a step map that at each configuration either halts with a label or gives a next configuration, and a property of configurations. A halting run of under from to with label is a sequence of configurations with for , each , included, satisfying , and halting at with label .✦
Space is counted on a window. A window of is a choice, for each work tape , of an interval of cells with and natural numbers.✦ A configuration of lies inside when every work head is in its interval.✦ Tape has bits per symbol, where is the number of binary digits of ✦, and the size of in bits is (2)✦ A multitape Turing machine computes the output on inputs within bits when, for some window whose size (2) is at most , the step of on has a halting run from the initial configuration, under the property of lying inside , with label .
Stack Machines and the Space Calculus
In the calculus, a stack is a word of bits read from its top. A stack operation is keep, push for a bit , or pop, which removes the top bit and leaves an empty stack empty.✦ A stack machine with input alphabet , argument tapes indexed by , stacks indexed by and labels in consists of a finite set of states with a start state and a transition table.✦ Given the state, the marks under the input heads and the top bit of each stack, or none when it is empty, the table either halts with a label in or prescribes an action: a direction for each input head, an operation for each stack and a next state.
A store consists of the positions of the input heads and the contents of the stacks✦, and a configuration of a stack machine is a state with a store✦. The step of a stack machine on a configuration reads the table as for a Turing machine, and an action takes the configuration to the next state, with the input heads moved and each stack changed by its operation.✦ A bounded run within bits is a halting run of the step under the property that every stack has length at most .✦ An execution of the machine on inputs within bits from a store to a store with label is a bounded run on within bits from the start state with that halts with label in some state with .✦
Let be a family of machine inputs over with argument tapes indexed by , a family of space bounds, and families of stores with stacks indexed by , and a family of labels, all indexed by a set . The families , , , and form a stack computation in space when there are a stack machine whose stacks are those of and finitely many extra ones, and a constant , such that for every the machine has an execution on within bits per stack from to , its extra stacks empty at both ends, with label .✦
The number as a stack is the store with no argument tapes, the input head at on the left endmarker and a single stack holding .✦ For a family of words over and families , , of natural numbers, all indexed by , the family is computable from in space on public inputs when the words as public inputs, the numbers as stacks and the numbers as stacks form a stack computation in space , halting with the same label at every index.✦
The Claim
Theorem 1. Let be a set of indices, a family of words over an alphabet , a family of natural numbers, a nonempty finite set of labels with an injective code , and a family of labels, all families indexed by .
If is a family of natural numbers indexed by and the codes are computable from in space on public inputs , there are a multitape Turing machine over with one binary argument tape and outputs in , and a constant , such that for every (3)✦
If the codes are computable from the constant family in space on public inputs , there are a multitape Turing machine over with no argument tapes and outputs in , and a constant , such that for every (4)✦
What Is Checked
The claims (3) and (4) are stated over computability in space by stack computations, with numbers held as stacks of binary digits, and over multitape Turing machines with a read-only public input and binary argument tapes, whose space is the size in bits of a window of cells of the work tapes.