The Setting
A deterministic machine has a finite control, one writable tape and a fixed number of read-only heads. What its read-only heads see, and what its writable tape holds at the start, depend on a public input , and a second machine, the accessor, computes the symbol at each position from . Given and a cap in binary, the task is to find the state of at time and whether has halted by then, with as few bits of work space as possible. With no cap given, the question is the final state of on an input on which it halts.
Turing Machines and Work Bits
A Turing machine over an input alphabet consists of a finite set of states with a start state, a read-only public input tape, read-only argument tapes over , finitely many work tapes, tape with a finite alphabet containing a blank, and a transition table.✦ A read-only tape holds its word between a left endmarker at position and a right endmarker at position ✦; its head starts at and never moves past an endmarker. The work tapes are infinite in both directions and start blank with their heads at cell .✦ In one step, from its state, the marks under its read-only heads and the symbols under its work heads, either halts with an output or enters a new state, moves each read-only head by at most one cell, and on each work tape writes a symbol and moves by at most one cell.✦ Numbers on argument tapes are written in binary, least significant bit first, and for a machine with argument tapes, is on the public input with on its th argument tape; has no argument tape.✦
A window for gives each work tape an interval of cells✦, and its size in bits is (1)✦ where is the number of bits per symbol of tape . The machine computes on within work bits, written , if its run from the initial configuration halts with output and some window of at most bits holds every work head throughout the run.✦
The Simulated Machine
A one-tape machine with read-only heads over the input alphabet consists of a finite set of states with a start state and a set of halting states, a finite tape alphabet , a transition function (2)✦ and a sensor , which gives a symbol for every word , every tag and every position , a tag being one of the read-only heads or the writable tape . On input , the writable tape starts with in cell , and every head starts at position .✦ In a state that is not halting, with under the writable head and read-only head at position , the value gives the next state, the symbol written under the writable head with that head’s move, and the moves of the read-only heads; in a halting state nothing changes. If is the state after steps, the outcome of on at time is (3)✦ where the flag is when is halting and when is still running at time . The machine has halted on by time when .
The code of an element of a finite set is its index in a fixed enumeration of that set.✦ An accessor for is a Turing machine over with four argument tapes, whose outputs are symbols of ✦; on the query for the tag and the position under the cap , its argument tapes hold , , the sign bit and .✦ The accessor serves at cap within work bits if (4)✦ For reals and , the pair satisfies the access condition if serves at cap within work bits, where .✦
Allowances and Register Computations
Write for the bit length of and .✦ The scale and, for , the space allowance are (5)
A stack machine over consists of a finite set of states with a start state, read-only heads on a public input and on argument tapes as above, finitely many binary stacks, one of them distinguished as the register, and a transition table.✦ In one step, from its state, the marks under its heads and the top bit of each stack, or the fact that it is empty, the machine either halts with an output or enters a new state, moves its heads by at most one cell, and keeps, pushes a bit onto or pops each stack.✦ A run of a stack machine is within a bound if every stack holds at most bits in every configuration of the run.✦
Let and be families indexed by . The family is computable from in space , written with understood, if there are a single stack machine, with a register stack and finitely many auxiliary stacks, and a single constant such that, for every , the machine on the public input with no argument tape, started with in binary on the register, the auxiliary stacks empty and its input head at the left endmarker, halts with in binary on the register, the auxiliary stacks empty and its input head back at the left endmarker, in a run within .✦ A family of elements of a finite set is computable from in space if .✦ A family is linear in if for one constant and every .✦
The Claim
Theorem 1 (One-tape simulation in two-fifths-power space). Let be a one-tape machine with read-only heads over an input alphabet , and let be an accessor for .
(a) If is finite and are reals, there are a Turing machine with one argument tape, a number and a real such that, for every input and every for which satisfies the access condition, (6)✦
(b) If is finite and are reals, there are a Turing machine with no argument tape, a number and a real such that, for every input for which satisfies the access condition at every , and every time by which has halted on , (7)✦
(c) If and are reals, there are such that, for every input and every for which satisfies the access condition, every tag and every , (8)✦
(d) Let , and let and be families indexed by such that , the family is linear in , and, for one constant and every , the accessor serves at cap within work bits. Then (9)✦
(e) Let , and let and be families indexed by such that, for every , has halted on by time and serves at every cap within work bits. Then, with the constant family, (10)✦
In the paper, the result reads: for a deterministic machine with one writable tape and head, a fixed number of read-only input heads, unit movement and fixed origins for all heads, symbol functions that do not depend on the cap (the sensor here) and a fixed accessor, the finite-control and halting outcome by time can be computed deterministically in work bits, not counting storage for the read-only input, for every public input and supplied binary cap for which the access condition holds, with unrestricted simulation time and without materializing the final writable tape; and if the access condition holds for at every and the machine halts on after steps, its outcome can be computed with no running time supplied in work bits.
What Is Checked
The statements (6) to (10) are made over the one-tape machine with its sensor and outcome , the accessor and the access condition, the work bits of a Turing machine counted over a window, computability in space by a stack machine with a register, and the allowance .