The Setting
A reference tour is a block computation given by a positive integer , a controller width of bits, a positive number of blocks, an initial controller , an initial word for each block , a selection that names for each controller the block it reads and rewrites, and a visit map that sends a controller and the word of that block to the next controller and the block’s new word.✦ The story of a reference tour is the sequence of scenes , where is the controller and the words of all blocks after visits, with and one visit from each scene to the next.✦
The epoch circuit of reads the story every visits, over epochs. Its vertices are the numbers for an epoch and a column , so that a vertex has epoch and column . In column stands the array vertex of block , whose value is the word held by block after visits. Column , for , holds the start vertex when and the history vertex of round otherwise. The round index of a vertex in column is , and that of an array vertex is . With , the value of the vertex in epoch and column is the controller history , written in base .
A recursive evaluation of descends from a vertex to the vertices its value depends on, and each descent costs work space for a frame, more when the frame holds guessed controllers; the space used is that of the heaviest chain of descents. Instead of enumerating chains, one puts a potential on the vertices: coins that pay for each descent out of the vertex it starts from.
Circuits, Prices and Meters
An evaluation circuit of width with children per node has nodes , some of them marked as base nodes.✦ Each node has a head child , children , a number of guessed bits, a first value prescribed at base nodes and a semantic value, and the circuit has two local rules, each a number for every node and coordinate: a proposal, from a guess and the value of the head, and an admissibility test, from a guess, a child index and the values of the head and of that child.✦ The outer degree of is ✦, and the circuit modulus of is the largest prime with ✦.
The price of a frame with guessed bits in is (1)✦ where is the bit length of .
A coin meter for is an assignment of a natural number of coins to each node of that pays for every step down from a node that is not a base node: for the cheap step to the head child, and for the expensive step to each child with .✦ We write for the set of coin meters for .
As an evaluation circuit, has width , the bits of controllers, and children per node.✦ The base nodes of are the vertices of epoch in the columns .✦ The head of a vertex in epoch and column is , the history vertex of round one epoch earlier, when , and , one round back in the same epoch, when with .✦ Every child of an array vertex is , the same block one epoch earlier; every child of the start vertex is its head; and the child of index of a history vertex is , the array vertex of block in the same epoch.✦ A history vertex guesses bits, controllers of bits, and every other vertex guesses none.✦
The augmented bit at coordinate of a word of width is the binary digit of at place when , the bit when , and when .✦
The first value of at a vertex is the initial word in a column and the initial controller elsewhere✦, and its semantic value is the value of the vertex in the story. Replaying block of under a transcript , a number read as digits in base , from a word gives a sequence of pairs of a word and a verdict: its first term is with the verdict true, and each next term comes from the previous one by one replay step at the next digit of , where a replay step applies the visit map to that digit and the current word and sets the verdict according to whether the selection sends that digit to block . The local rules of replay blocks: at an array vertex, the test on child replays block from the value of that child for visits under the head’s value, and every other child is admitted; at the start vertex, the proposal is the digit of the head’s value at place in base and every child is admitted; at a history vertex of round , the test on child replays block from the value of that child for visits under the history whose lowest digits in base are those of the head’s value and whose higher digits are the guess.
The Coins
The easy price of is the price of a frame with no guessed bits, (2)✦ and its hard price is the price of a frame that holds the guess of a history vertex, (3)✦
The budget of one epoch is one hard price and easy ones, (4)✦
The coins of are the assignment that gives a vertex in epoch , column and round index the number (5)✦
The Claim
Theorem 1. Let be a reference tour, with epoch circuit , easy price , budget and coins . For every vertex of that is not a base node, (6)✦ moreover, (7)✦ and for every vertex of , (8)✦
A dependency path from a vertex is a chain of descents, and its weight is the sum of the prices of its descents. In the paper, the result reads: every dependency path from the final history has weight , where is the time simulated.
What Is Checked
The claim is stated over a reference tour and its epoch circuit , with the base nodes, heads , children and guessed bits of its vertices, over the price of (1) and the coin meters of an evaluation circuit, and over the coins of (5), built from the prices (2) and (3) and the budget (4).