The Setting
Take a deterministic Turing machine that reads an input word of length with a fixed number of heads, works within cells of a fixed number of binary work tapes, and decides a language . The question is how long it can run before its verdict: whether a polynomial in bounds that time, with constants that depend on the machine and not on the input. The library states such a bound for its model of probabilistic Turing machines, restricted to the ones that ignore their coins.
Machines and Their Runs
A binary word is a finite sequence of bits, and is the length of the word .✦ A language is a set of binary words.✦ The input tape of a word of length has cells to , the word with its two endmarkers, and an input tape symbol is the left endmarker, a bit, or the right endmarker. A head direction is one of the three moves left, stay and right.✦
A probabilistic Turing machine with states , binary work tapes and input heads consists of an initial state, an output for each state , and a transition function .✦ The output is accept, is reject and is no verdict; the states with a verdict are the halting states. From a state , the input symbols under the input heads, the bits under the work heads and a coin bit , the transition function gives a machine action , the instruction for one step: a next state, a bit to write on each work tape, and a direction for each work head and each input head.✦
A machine is deterministic when its transition function ignores the coin: for every state , input symbols and work bits , (1)✦
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 , one coin for each time step.✦ The run of on a word with coin tape is the sequence of configurations on inputs of length , for , in which is the initial configuration of on and is the result of one step of from with coin .✦ We write for the state of .
Space, Deciding and Halting
The space used by the run of on with coin tape through time is the sum, over the work tapes, of the number of distinct cells the tape’s head visits at the times to .✦ With the position of the head of work tape in , (2)✦ A machine works in logarithmic space when there is an integer such that, for every word of length , every coin tape and every time , (3)✦
A machine decides a language when for every word there is a time at which every run on gives the right verdict: (4)✦ where is for and otherwise.
On a word , a machine halts by time when, for every coin tape , the state is a halting state.✦
The polynomial clock with coefficient and exponent is the function of the input length given by (5)✦
The Claim
Theorem 1. Let be a deterministic machine that works in logarithmic space and decides a language . Then there are integers and such that (6)✦
What Is Checked
The claim (6) is stated over probabilistic Turing machines with an input tape between endmarkers, binary work tapes and a coin tape, over their actions, configurations and runs, and over the space (2) a run uses, the logarithmic space bound (3), determinism (1), deciding a language (4), halting by a given time and the polynomial clock (5).