The Setting
Over a commutative ring of characteristic two, one associates to each height of a self-simulating Turing machine hierarchy a quotient associative algebra generated by raw bitstrings encoding local configurations.
Given square matrices weighting either single generator bitstrings or bounded-length words of bitstrings, multiplying tensor-weighted generators along all words of total length and summing produces a matrix over the algebra. The questions are whether every such matrix sum vanishes for all sufficiently large once the hierarchy’s dilation factor and height exceed suitable bounds, and what growth condition on a sequence of dimensions forces the squared dimension eventually to fall below an exponential tower.
Hierarchy Growth and Word-rewriting Algebras
Given natural numbers , , and , the hierarchy height is the natural number defined by (1): (1)✦
Starting from natural numbers and , a sequence , and a natural number , the hierarchy dimension is the natural number given recursively by and (2): (2)✦
Let be an alphabet and a semiring, write for the free monoid of words over , and write for its monoid algebra, in which each word determines a basis monomial with coefficient . A word-rewriting table over consists of a binary replacement relation on and a subset of zero words.✦ When is a ring, the defining relations of form the set (3): (3)✦ Letting be the two-sided ideal generated by , the table algebra is the quotient ring (an associative -algebra when is commutative), with quotient homomorphism sending each to .
Matrix Letter and Chunk Tests
For a map from an alphabet into a monoid (or ring) , the word evaluation of a finite list over is the product in (equal to when ). When is finite and , write for the finite set of candidate words over of length at most .✦ Over a ring , the abstract letter sum of at length is the sum in of over all of length ; for a finite chunk alphabet , a length map , a weight map , and , the abstract chunk sum is the sum in of over all lists satisfying .
Let be a ring, a -algebra, and a finite index set, writing and for the matrix rings over and . The tensor product of a matrix and an element is the matrix with -entry for all .✦ For a finite alphabet , a matrix weight , a map , and , the matrix letter sum is the abstract letter sum of length for , given by (4): (4)✦ For a finite chunk alphabet , a labeling map assigning a finite list over to each , a matrix weight , and , the matrix chunk sum is the abstract chunk sum of target length for chunk lengths and weights , given by (5): (5)✦
Finite-table Rewriting and the Machine Hierarchy
For a capacity bound , a data bit address is a triple consisting of a Boolean side , a block index , and a position ; a cell memory address is either a data bit address or a certificate address at a position . A three-bit register state is a map , and a verification task is a pair specifying an arity in and a Boolean zero-task flag. A verification clause of capacity consists of three cell memory addresses together with a Boolean truth function on three-bit register states; a verification clause schedule of capacity assigns to each verification task a positive clause count at most together with a family of verification clauses indexed by task and index below .
A finite-table cell of capacity is a state tuple consisting of a block syntactic skeleton (a core, palette, or stop position, one of five markers, and metadata recording arity below , zero-task flag, and block index at most the arity), a palette checker state (idle, passed, or a head seeking a color below ), a pair of data bits, an certificate bit, and a reading head (side, clause index below , one of nine computation phases, and a three-bit register).✦ Given a schedule of capacity and a data size , two cell lists satisfy the cell-list replacement relation when every cell in either list satisfies the cell formatting condition for and the two lists are either singletons related in either direction by a unary transition or two-cell lists related in either direction by a binary transition.✦ A cell satisfies the unary zero condition for if it fails cell formatting, satisfies a semantic head-failure condition for , or lies at a palette position already passed by its checker; two cells satisfy the binary zero condition if they fail adjacent cell-pair compatibility, share the same palette position, or pair a palette cell seeking a distinct color with a stop cell.
For a height , the space of raw bitstrings is the set of Boolean vectors of length .✦ When , cell encoding embeds cells of capacity into , and partial decoding recovers a cell (and wordwise a cell list) whenever re-encoding reproduces the raw bitstring. Lifting cell-list replacement along word decoding, with undecodable words excluded, gives the raw word replacement relation on lists over ; a raw list satisfies the zero raw word predicate if it is a singleton whose letter either fails to decode or decodes to a unary zero cell, or a two-letter word decoding to a binary zero cell pair. For a schedule of capacity and a data size , these relations define the algebra table over , together with the Boolean table entry predicate , which decides whether is empty and is a zero raw word when is true, and whether satisfies raw word replacement when is false.
The timed one-tape Turing machine compiled from the wrapped-input universal stack machine (whose input decoder reads instruction tokens via one-hot bit packets of a fixed packet bit width for any finite register index set) has its labels encoded by a one-hot binary tape coding of bit width , and a combinational two-input not-and (NAND) circuit with gates realizes its local three-cell transition function. Given two Boolean lists and , their program specialization is the Boolean list obtained by prepending a true bit to the prefix encoding of , , the prefix encoding of , and , where the prefix encoding of concatenates true bits, a false bit, and the binary digits of , with and equal to the binary bit-length of for .
Given natural numbers with , , and , a tableau layout of capacity specifies an origin column below such that both the certificate variable count and the tableau clause count are at most .✦ For parameters with and , the layout parameter bounds require , , , , certificate and clause counts for at most , and (6): (6)✦
Given a Boolean code and parameters satisfying with , the source machine tableau layout has capacity , time , width , and origin column .✦ Compiling the three-wire addressable clauses that constrain the initial row (built from , , and the encoded blank, initial, accepting, and Boolean-bit symbols), boundary cells, local NAND circuit transitions, and final acceptance yields the source machine clause schedule of capacity . A data assignment on data bit addresses of capacity and a Boolean certificate vector of length assemble into an assignment on cell memory addresses of capacity ; meanwhile, whenever satisfy and , the candidate word for a data assignment of capacity at Boolean side and block is the raw bitstring in with -th entry for .
A self-simulating machine hierarchy of dilation factor consists of a Boolean program and a threshold such that, for , every height satisfies and the self-certification equivalence: for every verification task of arity and every data assignment of capacity , there exists a Boolean certificate vector of length satisfying every clause of under the assembled assignment if and only if , where is the zero-task flag of , is the list of the false-side candidate words in , and is the empty list when is true and the list of the true-side candidate words in otherwise.✦ At any height and for any commutative ring , let be the hierarchy clause schedule, let be the hierarchy rewriting table, let be the machine hierarchy algebra, and let map each to the word image .
With , , a height , and a dimension bound fixed, a letter test at height with dimension bound is a sequence associated with a finite index set satisfying and a matrix weight . For , a -bounded chunk test at height with dimension bound is a sequence associated with a finite index set satisfying , a finite chunk alphabet , a labeling map sending each to a nonempty list over of length at most , and a matrix weight .
The Claim
Theorem 1. Let be a self-simulating machine hierarchy with dilation factor and threshold , let be a commutative ring of characteristic two, and fix a height and an integer . For every letter test at height with dimension bound , there exists an index satisfying (7): (7)✦
For every integer and every -bounded chunk test at height with dimension bound , there exists an index satisfying (8): (8)✦
For any natural numbers , , , , and and any sequence satisfying , , and for every , there exists an index (a stopping index) satisfying (9): (9)✦
In the paper, the result reads: over every field of characteristic two, every letter test at level zero eventually vanishes, and the same is true of every level-zero chunk test with any fixed finite label bound. The library extends the setting from fields to commutative rings of characteristic two, states the vanishing at every height whenever , and adjoins (9).
What Is Checked
Claims (7) and (8) are stated over any commutative ring of characteristic two, any self-simulating machine hierarchy with dilation factor , any height , and any dimension bound (together with any bound in (8)), using matrix letter and chunk sums over the hierarchy clause schedule , rewriting table , machine hierarchy algebra , and letter map on ; claim (9) is stated over arbitrary natural numbers , , , , and and sequences satisfying , , and , in terms of the hierarchy height and hierarchy dimension .
The library proves that every height , the data size , the tape-coding bit width , the tableau clause count of any tableau layout, and the packet bit width of input instruction tokens are all positive.