The Setting
A deterministic machine with one writable tape runs for steps on a public word , and a simulator is to reproduce the run in two-fifths-power space, a power of with exponent (1)✦
Simulators are deterministic multitape machines with read-only input tapes, and their space is counted in work bits, cells times bits per symbol, the read-only tapes never counted. The tapes of reach them through an accessor, a second machine that computes from the symbol at a given position of a given tape of . The access condition holds the accessor to space polylogarithmic in , the logarithm of every bound being (2)✦
Machines and Their Space
A machine of the model has a public alphabet , a set of argument tapes and a set of output labels. It has a finite set of states with a start state and a finite set of work tapes, tape infinite in both directions over a finite alphabet with a blank symbol. It reads a public word over and a binary word on each argument tape, each framed by a left endmarker and a right endmarker . A move of a head is left, stay or right✦, a displacement of , or ✦. The transition function reads the state, the marks under the read-only heads and the symbols under the work heads; it either halts with a label in or gives a new state, a move for each read-only head, and for each work tape a symbol to write and a move: (3)✦ where and are the marks a read-only head can see. We write for the set of these machines.
An input is a public word with a binary word for each argument tape.✦ A read-only word lies at positions , with at and at ✦, and a move left from or right from leaves its head in place✦. For numbers , the input writes each in binary, least significant bit first, as the word , (4)✦ and a machine without argument tapes runs on its public word alone, (5)✦
A work tape is a content with a head position✦, starting blank with the head at cell ✦; a step writes the chosen symbol in the head’s cell and then moves the head✦. A configuration of is a tuple consisting of a state, the positions of the read-only heads and the work tapes; the initial configuration has state and every read-only head on its left endmarker, the work tapes as they start. On an input , a step from applies to what the heads see, written : it halts when and otherwise performs the action, giving the next configuration .✦
Tape stores (6)✦ bits per cell. A window gives each work tape an interval of cells with ✦; a configuration lies in when every work head is in its interval✦, and the size of in bits is (7)✦
A machine outputs on an input within bits, written , when the following holds: (8)✦
The Simulated Machine and Its Accessor
The simulated machine has a finite set of states with a begin state and a set of halting states, a finite alphabet , one writable tape and further heads that only read. Its program maps the state, the symbol under the writable head and the symbols under the other heads to a new state, a symbol to write and a move for the writable head, and a move for each other head. A tag is the writable tape or one of the read-only heads✦; the tags are numbered in a fixed order, being the number of ✦. The tapes of on a public word are given by its sensor: for a tag and a position , is the symbol at on the tape tagged .
An accessor of has four argument tapes, (9)✦ and is a machine with public alphabet and output labels , (10)✦
For a natural number , called the cap and bounding the positions asked for, a tag and a position , let be the assignment of numbers to the four argument tapes given by (11); the accessor is run on . (11)✦ where is when and otherwise.
Let be a public word and and natural numbers. An accessor of gives the tapes of on up to the cap within bits if every tag and every position with satisfy (12)✦
The Definition
Definition 1 (Access condition). Let be a machine with one writable tape, read-only heads and sensor , an accessor of , and real numbers, a public word and a natural number. The accessor meets the access condition with constants and on at the cap when every tag and every position with satisfy (13)✦
In the paper, the result reads: space counts work bits, the read-only input excluded; the simulator gets and a binary cap ; and the access condition for asks that for every tag and every with the accessor, run on , halt with using at most bits, the constants and in the place of and .
What Is Checked
The access condition (13) is stated over a machine with one writable tape, read-only heads and a sensor, an accessor of the model (3) with the four argument tapes (9), real constants and , a public word and a cap , with space measured in bits by windows (7) and bounds in (2).