The Setting
Cut the tape of a one-tape machine into blocks and follow its run block by block, as a sequence of visits: each visit rewrites one block and hands a controller, the part of the configuration kept outside the blocks, to the next. To simulate a long run in little space, one lays the run out as a circuit of short words, each determined from a few others by local rules, and evaluates it. The question is the layout: which moments of the run become vertices, what each vertex holds, and which vertex is the target. The library answers it for any run of block visits, which it calls a tour, with the epoch circuit of the tour.
Tours and Their Stories
Controllers and words are natural numbers, read as digit strings with the least significant digit first. A reference tour on blocks consists of a positive integer , a controller width in bits, an initial controller , an initial word for each block , a selection naming for each controller the one block it reads and rewrites, and a visit map sending a controller and the word of that block to the next controller and the block’s new word; the number is positive, and every selected block has index below : (1)✦
Blocks are written in the radix , the number of controllers of bits.✦ A tour has digits per block, epochs of visits, and circuit width , the number of bits in controllers: (2)✦ (3)✦ (4)✦
In the simulation of a run of steps, is the scale factor , two to the power ✦, where is the bit length of divided by five and rounded up: (5)✦ It satisfies for every .
A scene is a pair of a controller and a sequence of words, being the word held by block : (6)✦
One step of is a visit. On a scene the controller selects the block , the visit map returns the next controller and the block’s new word , and the new scene has controller and the words , those of with the word of block replaced by : (7)✦
The story of is the sequence of scenes that starts from the initial controller and words and makes one visit per term, being the controller and the word of block after visits: (8)✦
In base , the digit of a number at place is ✦, and digits pack into the number ✦. The controller history of from visit over steps packs the controllers of the story at visits through : (9)✦
Evaluation Circuits
An evaluation circuit of width with children per node consists of the nodes , some of them marked as base nodes, together with the following data. Each node has a head child , children for , a number of guessed bits, a first value , the value prescribed at a base node, and a semantic value , the value the node is meant to carry. Its two local rules are a proposal , a number for each node , coordinate , guess and head value , and an admissibility test , a number for each node, coordinate, guess, child index , head value and child value .
A word of width is augmented to the sequence of its augmented bits : the binary digit of at place for , the bit for , and for .✦
The Definition
Definition 1. Let be a reference tour. The vertices of its epoch circuit are the numbers below : (10)✦ They are laid out in epochs of columns: vertex lies in epoch and column ✦, and denotes the vertex , taken modulo ✦. In each epoch, column holds the array vertex of block , column the start vertex, and column , for , the history vertex of round ; the round index of is .
The value of an array vertex is the word of its block after visits, and the value of a vertex in a column , of round index , packs the epoch’s incoming controller and the first outgoing ones: (11)✦
The head of an array vertex or of a start vertex is the history vertex of round in the previous epoch, and the head of the history vertex of round is the vertex of round index in its own epoch: (12)✦
Each child of an array vertex is the vertex of the same block in the previous epoch, each child of a start vertex is its head, and child of a history vertex is the vertex in column of its epoch: (13)✦
The set of base vertices consists of the array vertices and the start vertex of epoch , the vertices with .✦ The first value is the initial word for and the initial controller otherwise.✦ A vertex in a column up to has guessed bits, and a history vertex has guessed bits, the length of controllers.✦
A transcript is a number whose digits in base are read as successive controllers. A replay step of block is a map taking a word, a verdict (a truth value) and a digit of a transcript to a new word and a new verdict. Replaying block under a transcript from a word gives a sequence of pairs of a word and a verdict: it starts from with the verdict true, and its term is one replay step, at digit of , from its term ; write and for the word and the verdict of term .✦
The round proposal at the history vertex of round , from a head value and a guess , is the number whose lowest digits are those of and whose higher digits are those of .✦
The proposal is at an array vertex; at a start vertex it is the augmented bit of the digit of at place , and at a history vertex the augmented bit of .✦ The admissibility test is at a start vertex, and at an array vertex for every child . For child of the array vertex of block it is the augmented bit of , and at the history vertex of round it is the verdict , read as or .
The epoch circuit of is the evaluation circuit of width with children per node on the vertices , with these base vertices, first values, guessed bits and rules, head , children and semantic value : (14)✦ The target of is the history vertex of round in the last epoch: (15)✦
In the paper, the result reads: , and epochs of visits in rounds of ; words of width , with bits per tape symbol; array words , the represented block after visits, and history words , the epoch’s incoming controller and the first outgoing ones; base, checkpoint and extraction rules; and the target .
What Is Checked
The definition is stated over a reference tour (1) with its story of scenes (8) and its controller histories (9), and over evaluation circuits, of which the epoch circuit (14) is one.