The Setting
A deterministic machine with one writable tape and read-only heads runs on an input word for at most steps, the cap. Its heads start at position , and in steps none of them leaves the positions to . To evaluate such a run in less space, the writable tape is cut into blocks of consecutive cells, and the machine at time is described by a controller, a short record of its finite control and its heads, together with one number for each block. The item fixes these blocks and numbers, which together form the view of the run at time .
Machines and Runs
A multihead machine with sensor over an input alphabet has a finite set of states with a start state and a set of halting states, a finite tape alphabet , a number of read-only heads besides its writable tape, and a program.✦ A direction is one of left, stay and right✦, whose displacements are , and ✦. An action consists of a next state, a symbol of to write with a direction for the writable head, and a direction for each read-only head; the program gives an action for every state, symbol under the writable head and choice of symbols under the read-only heads.✦ The sensor presents an input word over : for the writable tape or a read-only head and an integer position, it gives the symbol of found there.
A configuration of consists of a state , the writable tape, given by its content and the position of its head, and the positions of the read-only heads.✦ On , the initial configuration is in the start state, with every head at position and the writable tape holding the content the sensor gives for it.✦ The next configuration applies the program’s action for the state , the symbol under the writable head and the symbols the sensor gives on under the read-only heads, except that in a halting state the machine keeps its state, rewrites and moves no head. The new configuration has the action’s state, the action’s symbol written at with the writable head shifted by the displacement of its direction, and each read-only head shifted by the displacement of its own.✦ The configurations of the run of on are (1)✦ and denotes the content of the writable tape of .
Digits and Widths
A natural number is read as a digit string, least significant digit first. In base , the digit of at place and the packing of the first terms of a digit sequence are (2) The index code of an element of a finite set is its position in a fixed enumeration of by ✦, and , the element decoded from a natural number , is the one whose index code is ✦.
For a cap , the field width is the number of binary digits of ✦ and the field base is ✦. A controller is packed into fields of binary digits each; the controller width and the block radix are (3)
The Claim
Definition 1. Let be a multihead machine with sensor over , with states , tape alphabet and read-only heads. The squares of a cap are the addresses (4)✦ the square stands for the displacement (5)✦ and an integer is placed at the square (6)✦
A site is a cap with a positive integer and an offset below , (7)✦ A site has a block width and a number of blocks , given by (8)✦ (9)✦ and a square lies in the home block (10)✦ at the slot (11)✦
A controller of cap consists of a tick , a state , the square of the writable head and the squares of the read-only heads.✦ The controller of a configuration at time is (12)✦ The packing of a controller of cap is the natural number whose digits in the field base, with , are , , and , (13) The parsing of a natural number , with digits , is the controller of cap whose fields are read from the digits of : (14)
For a tape content , the glimpse of cell of block is the index code of the symbol at the cell’s position when the cell is within reach, and that of the filler , the symbol of index code , otherwise: (15)✦ The represented block of block of is the natural number whose digits in the radix are the glimpses of its cells: (16)✦
A scene is a pair of a natural number and a sequence of natural numbers.✦ The view at time of on an input word over the site is the scene of the packed controller of and every represented block of its tape content : (17)✦
In the paper, the result reads: raw controllers of bits hold the state, flags, the elapsed time and the head displacements; for a width and an offset , the physical blocks are for integers ; the blocks are those meeting ; and the represented block of the configuration carries a filler outside .
What Is Checked
The definition is stated over a multihead machine with sensor over , its run on an input word and a site . Of these constructions the library proves that parsing inverts packing: every controller of cap satisfies (18)✦