The Setting
Consider a self-simulating computing machine and a unital associative ring of scalars. To each integer height above a threshold, one assigns a rewriting table on finite binary strings and its finitely presented quotient algebra, while pairing a square matrix of scalars with an element acted on by those scalars yields a matrix over the target space.
Rewriting Tables and Algebras
Given an alphabet , the free monoid of words consists of all finite sequences of letters from under concatenation.✦ For a semiring , the monoid algebra of words is the monoid algebra of with coefficients in ✦, and the basis monomial of a word is the element with coefficient at and elsewhere.✦
A word rewriting table over consists of a binary replacement relation on and a subset of zero words.✦ When is a unital associative ring, the set of defining relations of in is (1): (1) The defining two-sided ideal is the two-sided ideal generated by ✦, and the rewriting-table algebra of over is the quotient ring (2): (2)✦
Finite Table Rewriting and Bitstring Encoding
For a nonnegative integer bound , a cell memory address is either a data address with Boolean side , block index , and integer position satisfying , or a certificate address with .✦ A three-bit register state is a tuple in ✦, and a verification clause of capacity consists of three cell memory addresses indexed by together with a Boolean truth function on .✦ A verification task specification consists of an arity and a Boolean zero-task flag .✦ A verification clause schedule of capacity assigns to each verification task a clause count satisfying together with a family of verification clauses of capacity indexed by integers with .✦
For a bound and arity bound , a cell syntactic skeleton consists of a block cell position (either a core position with , a palette color with , or ), a marker among , , , , and , and block metadata specifying an arity with , a Boolean zero-task flag , and a block index with ✦; cell arity metadata specializes this to ✦, with task projection mapping to . A palette checker state over a color set is , , or for some .✦ A head computation phase is one of the nine stages , , , , , , , , and ✦, and a reading head state of capacity records a Boolean side, a clause index with , a phase, and a three-bit register.✦ A finite-table cell of capacity consists of a syntactic skeleton of capacity and arity bound , a palette checker state over , a pair of data bits indexed by Boolean side, an certificate bit, and a reading head state.✦
Cells of capacity carry a compatibility relation on adjacent pairs; given also a verification clause schedule of capacity and a nonnegative integer data size , cells carry a formatting condition depending on and , along with unary and binary transition relations determined by . Two cell lists and satisfy the cell-list replacement relation for and when every cell in and is formatted and either and are related in either direction by a unary transition, or and are related in either direction by a binary transition.✦ A cell satisfies the semantic zero condition for when its marker is and either its phase is , , or with a nonzero register, its phase is and the truth function of the scheduled clause for the cell’s projected task and head clause index evaluates to on its head register, or its phase is and its zero-task flag is .✦ A cell satisfies the unary zero condition for and when fails cell formatting, satisfies the semantic zero condition, or has position with checker state .✦ An ordered pair of cells satisfies the binary zero condition when it is not a compatible adjacent pair, when both cells have the same palette color , or when has position with checker state for while has position .✦
For a nonnegative integer height , set and let be the alphabet of raw bitstrings of length .✦ Cell encoding maps each cell of capacity to a raw bitstring in ; for , cell decoding parses a bitstring to a candidate cell of capacity and returns if equals the encoding of and fails otherwise✦, while word decoding maps a word over to the corresponding cell list when every letter decodes and fails otherwise.✦ Given , a schedule of capacity , and a data size , two words satisfy the raw word replacement relation if both decode to cell lists related by the cell-list replacement relation for and .✦ A letter satisfies the raw unary zero condition if decoding fails or yields a cell satisfying the unary zero condition✦, two letters satisfy the raw binary zero condition if both decode to cells satisfying the binary zero condition✦, and a word satisfies the zero raw word predicate if has length one with a raw unary zero letter or length two with a raw binary zero pair.✦ For , of capacity , and data size , the codec algebra table is the word rewriting table over whose replacement relation is raw word replacement and whose zero set consists of all words satisfying the zero raw word predicate.✦ Given also a Boolean selector and words , the codec table entry evaluates to if with empty and a zero raw word, or if with in raw word replacement, and to otherwise.✦
Self-simulating Machine Hierarchies
Fix a self-interpreting one-tape Turing machine with finite tape alphabet and state set, equipped with a one-hot binary tape-label coding of bit width and a combinational NOT-AND (NAND) circuit realization of its local three-cell transition having gates. Under this coding, the blank cell label, initial state label, accepting state label, and Boolean bit labels have fixed -bit encodings.
Write for the binary length of a nonnegative integer , equal to when and when .✦ For nonnegative integers and integers , , the total certificate variable count is ✦ and the total tableau clause count is .✦ A tableau layout of parameters specifies an origin column with subject to , , , , and .✦ For a dilation factor , integer height , and code length , set and ; the layout parameter bounds predicate holds for when , , , , , , and (3) holds: (3)✦
When the layout parameter bounds hold for of a finite Boolean sequence and , the source machine tableau layout constructs a tableau layout of parameters with origin column , and compiling the initial, boundary, local NAND circuit transition, and acceptance constraints gives a family of three-wire addressable clauses and a verification clause schedule of capacity . For each task , the initial row assigns to each tape position and bit index either a fixed Boolean value or a reference to a data address (encoding , , the augmented arity , the zero-task flag , and the input data blocks). Given a Boolean data assignment on data addresses of capacity and a Boolean certificate vector , the assembled assignment combines and on all cell memory addresses of capacity to test satisfaction of every indexed tableau clause. For a Boolean data assignment on data addresses of capacity , nonnegative integers with , arity , Boolean side , and block index with , the candidate word of has -th entry for .✦
Fix a dilation factor . A self-simulating machine hierarchy with dilation consists of a finite Boolean sequence (its program) and an integer threshold satisfying two conditions for the self-specialized code obtained from by prefix-encoded specialization of to itself. First, for every integer , the tuple satisfies the layout parameter bounds, yielding the hierarchy clause schedule of capacity . Second, for every integer , every task , and every Boolean data assignment on data addresses of capacity , let be the -letter word of candidate words (), and let be empty when and the -letter word of candidate words when ; then there exists a Boolean certificate vector on satisfying every height- tableau clause under the assembled assignment if and only if the self-certification condition (4) holds: (4)
The Definition
Definition 1. Let be a self-simulating machine hierarchy with dilation factor and threshold . For every integer , the hierarchy rewriting table over the raw bitstring alphabet is the codec algebra table (5): (5)✦ For any unital associative ring and any integer , the machine hierarchy algebra of is the rewriting-table algebra (6): (6)✦ For any index set , any scalars acting on a set via , any matrix with entries in , and any element , the tensor product is the matrix over defined entrywise by (7): (7)✦
In the paper, the result reads: fix and put , , , , and over a field of characteristic two, with and . Unlike the paper’s subsequence and characteristic-two field, (5) and (6) apply at every integer and over any unital associative ring , while (7) defines the matrix tensor map entrywise.
What Is Checked
The definitions (5) and (6) are stated over a self-simulating machine hierarchy with dilation factor and threshold , an integer height , and an arbitrary unital associative ring , while (7) is stated over an arbitrary index set and any scalar action of a set on a set . For these constructions, the library also proves that the coding bit width and the total clause count of any tableau layout are positive, and that for every both and the data block size are positive.