The Setting
Fix a commutative ring and a self-simulating machine hierarchy , together with an integer height at least the threshold of . At height , the hierarchy determines a finite alphabet of raw bitstrings and an associative unital algebra over generated by . Given matrix weights over assigned either to individual letters in or to bounded nonempty words over , the question is how to form the resulting weighted matrix sums of length over and when every such matrix test of dimension at most vanishes for all sufficiently large .
Rewriting Algebras and Matrix Weights
For an alphabet , the free monoid of words is the free monoid generated by under concatenation with identity the empty word ; each word has length and letters .✦ For a finite alphabet and an integer , the set of candidate words is the finite set of all words over of length at most , and the set of words of length , , is the subset of words of length . Given a map from an alphabet into a monoid , the word evaluation of a word is the product in (taking the value on ).✦ Given a chunk alphabet , an alphabet , and a labeling map , the spelled word of a chunk sequence is the concatenation (equal to when ).✦
For a semiring and an index set , the matrix algebra is the set of matrices over , which forms a semiring when is finite, and for an integer , the matrix algebra is with . Given a chunk alphabet , a semiring , an integer , and a matrix weight map , the chunk-sequence weight matrix of a sequence is the matrix product (equal to the identity matrix when ).✦ Given an index set , sets and with a scalar action of on , a matrix , and an element , the tensor product is the matrix over defined entrywise by (1): (1)✦
For a semiring and an alphabet , the monoid algebra of words is the monoid algebra of with coefficients in ✦, and the basis monomial of a word is the single-term element with coefficient at .✦ For an alphabet , a word rewriting table over consists of a binary replacement relation on and a set of zero words .✦ For a ring and a word rewriting table over , the defining two-sided ideal is the two-sided ideal generated by the defining relations ✦, and the table algebra is the quotient ring of by , equipped with the quotient homomorphism assigning to each word its image .
For an integer , the raw bitstring alphabet is the finite set of Boolean vectors of length .✦ For an integer dilation factor , a self-simulating machine hierarchy consists of a binary program and an integer threshold such that every integer satisfies the layout parameter bounds for the self-specialized code of the program and the self-certification equivalence relating tableau satisfiability at height to the local verification table entry at height .✦ Given such a machine hierarchy , a commutative ring , and an integer , the hierarchy clause schedule for the self-specialized code produces a word rewriting table over at data size whose replacement relation and zero-word set encode the raw word replacement and zero-word conditions of that schedule✦, and the machine hierarchy algebra is the table algebra .✦ At height over a commutative ring for a machine hierarchy , the letter map assigns to each raw bitstring the generator corresponding to the one-letter word .✦
The Definition
Definition 1. For a finite alphabet , a semiring , a map , and an integer , the abstract letter sum is the element given by (2): (2)✦ When is a finite chunk alphabet, is a semiring, is a length map, is a weight map, and is an integer, the abstract chunk sum is the element defined by (3): (3)✦ Given a finite index set , a finite alphabet , a semiring acting by scalars on a semiring , maps and , and an integer , the matrix letter sum is the matrix over given by (4): (4)✦ Take a finite index set , a finite chunk alphabet , an alphabet , a semiring acting by scalars on a semiring , maps , , and , and an integer ; the matrix chunk sum is the matrix over defined by (5): (5)✦ At matrix dimension , with a finite chunk alphabet , an alphabet , a semiring acting by scalars on a semiring , maps , , and , an integer , and indices , the chunk sum matrix entry is the element of defined by (6): (6)✦ Let be a self-simulating machine hierarchy with threshold , let be a commutative ring, and let be an integer; an integer dimension bound satisfies the letter vanishing condition over at height if for every finite index set with and every weight map , there exists an integer satisfying (7): (7)✦ Fix a self-simulating machine hierarchy with threshold , a commutative ring , and an integer ; a dimension bound and a label bound satisfy the chunk vanishing condition over at height if for every finite index set with , every finite chunk alphabet , every labeling map satisfying for all , and every weight map , there exists an integer satisfying (8): (8)✦
In the paper, the result reads: a letter test of dimension at level assigns to each with length- sum , a chunk test of dimension and label bound has finite identifiers , nonempty labels with , and weights with length- sum , and a test eventually vanishes if its length- sum is zero for all sufficiently large (with for , for , for , for , for and , for , for , for , and for ). Whereas the paper defines these tests individually for , the library’s definitions build the matrix sums from abstract word and chunk sums over semirings, allow any and finite index sets with , and quantify vanishing universally over all weight maps and bounded nonempty labelings at height .
What Is Checked
The weighted sums and vanishing conditions are stated over finite alphabets, semirings with scalar actions, finite matrix index sets, table algebras of word rewriting tables, and, for eventual vanishing, a commutative ring , a self-simulating machine hierarchy with dilation factor and threshold , an integer height , the raw bitstring alphabet , the hierarchy algebra with its letter map , and nonnegative bounds and .