The Setting
The machine to be simulated is deterministic, with a finite control, one alphabet, one writable tape infinite in both directions and carrying a single head, and a fixed number of read-only heads. Every head starts at the origin of its tape and moves by at most one cell per step. What the heads read is determined by the input: it fixes what the writable tape holds at the start and what each read-only head finds at each displacement from its origin, and as one function supplies all of this, what different heads see may be correlated in any way.
The library defines this machine, its run on an input, and the outcome of the run at each time .
Tapes, Moves and Configurations
The set of directions consists of , and ✦, and the displacement of a direction is the integer , , .✦
A tape over an alphabet is a pair of a head position and contents ✦, and the symbol under its head is .✦
A write-and-move pair over is a pair of a symbol and a direction .✦ Performing it on a tape gives the tape (1)✦ where takes the value at and agrees with elsewhere.
Let be a set of states, an alphabet and a number of read-only heads. A configuration is a triple of a state , a tape over , which is the writable tape with its head, and the positions of the read-only heads, each measured from that head’s origin.✦
The Claim
Definition 1. Let be a set, whose finite words are the inputs. A multi-head Turing machine over consists of a finite set of states with a start state , a halting flag for each state , a finite alphabet , a number of read-only heads, a program and a sensor .✦ An action is a next state, a write-and-move pair for the writable tape and a direction for each read-only head, an element of (2)✦ The program maps a state, the symbol under the writable head and the symbols under the read-only heads to an action. The sensor gives, for each input , each tag and each displacement , a symbol , where the tag is for the initial writable tape or an index for read-only head . The transition with halting is the map given, for , and , by (3)✦ On input the initial configuration is (4)✦ where is the contents . One step on input takes a configuration , sets and gives (5)✦ The configuration at time on input is , starting from (4) with .✦ The outcome of a state is (6)✦ and the outcome at time on input is for the state of ; its flag is false while the machine is still running at time .✦
In the paper, the result reads: the machine is a fixed deterministic one with finitely many states, a finite alphabet, one writable two-way tape with one head and a fixed number of read-only heads, moving by unit steps from fixed origins, with the symbol at displacement from the origin of tag independent of every space cap; its halting states are absorbing, and its outcome by time , the page’s , is the state of its finite control with the halting flag.
What Is Checked
The definition is stated over directions with their displacements, tapes with the symbol under the head, write-and-move pairs performed as in (1), configurations made of a state, a writable tape and the positions of the read-only heads, and outcomes pairing a state with its halting flag.
The library proves two facts about the run on an input . If the halting flag of the outcome at time is true, then for every (7)✦ For every , the head positions of satisfy (8)✦ where is the interval of integers with .