The Setting
Take a unital associative algebra over equipped with an augmentation homomorphism . Can be infinite and finitely presented while carrying a length grading and satisfying the condition that every finite square matrix over is nilpotent? A self-simulating Turing machine whose local verification transitions form a rewriting system over binary strings yields an algebra of this kind. These notes set out the definitions behind that construction and the theorem stated over them.
Word Rewriting Algebras and Matrix Nilpotence
For an alphabet , the free monoid of words is the free monoid generated by , with empty word and word length for .✦ Given a map into a monoid , the word evaluation of is the product in , with .✦
Over a semiring and an alphabet , the monoid algebra of words is the monoid algebra .✦ Inside , the basis monomial of a word is the single-term element with coefficient at and elsewhere.✦
A word rewriting table over an alphabet is a pair consisting of a binary replacement relation on and a subset of zero words.✦ For a ring , the defining relations in form the subset (1)✦ The defining two-sided ideal of over is the two-sided ideal of generated by in (1). The table algebra of over is the quotient ring (2)✦ The algebra quotient map of the table algebra is the quotient homomorphism onto (2), and the word image in of is .✦
Call a word rewriting table over homogeneous when for all words satisfying .✦ For an alphabet and a ring , the free-monoid augmentation is the monoid homomorphism sending every letter of to .✦ When is homogeneous and , the table algebra augmentation is a -algebra homomorphism for any commutative ring .✦
Given a word rewriting table over and a commutative ring , the word grading homomorphism is the monoid homomorphism mapping each word to .✦ When is homogeneous, the algebra grading homomorphism is a -algebra homomorphism (3)✦
Given a ring and a ring homomorphism , the kernel is matrix-nil (and is nil for every integer ) if for every integer , every matrix whose entries satisfy satisfies for some integer .✦
Finite-table Rewriting and Bitstring Coding
A verification task is a pair consisting of a block arity and a Boolean zero-task flag .✦ Given an integer capacity , a cell memory address is either a data address with side , block index , and position , or a certificate address .✦ Over , a three-bit register is a map .✦ A verification clause of capacity consists of three cell memory addresses indexed by together with a Boolean truth function on three-bit registers. A verification clause schedule of capacity is a family assigning to each verification task a clause count satisfying and a family of verification clauses indexed by and .✦
Each block metadata record consists of an arity , a zero-task flag , and a block index , with task projection . A cell syntactic skeleton of capacity consists of a position (core , palette color , or stop), a marker (idle, left wing, boundary, full, or right wing), and a block metadata record.✦ A cell syntactic skeleton of capacity is admissible when no initial skeleton ( at core ) has the right-wing marker and no terminal skeleton ( at stop) has the left-wing marker, and it carries an active head when its marker is boundary or full.✦ Over colors below , a palette checker state is idle, passed seeking a color, or an active head seeking a color.✦ A reading head state of capacity records a side bit, a clause index , a three-bit register, and one of nine head computation phases (acquisition, left read, right read, before-gate, after-gate, left undo, right undo, finish, or success), among which acquisition, before-gate, after-gate, finish, and success are the endpoint phases.
A finite-table cell of capacity consists of a syntactic skeleton, a palette checker state, side-indexed data bits in , a certificate bit in , and a reading head state; such a cell is head-free if its skeleton carries no active head marker and its checker is not a checker head.✦ Reading a cell memory address from a cell returns its data bit on matching core position and block, its certificate bit on matching core position at block , and elsewhere, so each verification clause yields a three-bit register delta from . For a schedule of capacity and data size , a finite-table cell of capacity satisfies the cell formatting condition if its skeleton is admissible, its checker is idle off palette positions, its data and certificate bits vanish off the core (with data bits vanishing at core positions ), and its marker constrains its metadata and head fields: idle cells carry arity , zero-task flag , block , side , clause , acquisition phase, zero register, zero true-side data, and zero certificate; left and right wings carry side , clause , acquisition phase, and zero register; boundary cells carry clause , acquisition phase, and zero register; active heads with zero-task metadata take side ; and full cells take clause in success, a clause below otherwise, and terminal skeletons at endpoint phases.✦
Two finite-table cells and of capacity form a compatible adjacent cell pair when their positions are adjacent (core before , core before palette, palette before palette or stop, or stop before core ), their external or internal markers and block metadata agree across the boundary, and their palette checkers satisfy adjacent and terminal compatibility.✦ The symmetric cell-list replacement relation on formatted singletons and pairs is generated by twelve unary transitions at block ends and eight binary transitions on adjacent pairs: they sweep a reading head across a block to accumulate clause register deltas, test the clause truth function at the before-gate phase, advance clauses to success and pivot the side flag for nonzero tasks, create or advance palette checker heads, and swap head-free palette cells.✦ On a single finite-table cell of capacity , the unary zero condition for and holds if fails formatting, exhibits a semantic failure (nonzero register at acquisition, finish, or success, false clause evaluation at after-gate, or success on a zero-task cell), or has a palette color already marked passed .✦ On two finite-table cells and of capacity , the binary zero condition holds if they do not form a compatible adjacent pair, repeat the same palette color, or place a palette checker head seeking at color immediately before stop.✦
For an integer and capacity , a raw bitstring of height is a Boolean vector of length , and the set of such bitstrings is denoted .✦ The cell encoding map sends each finite-table cell of capacity to binary slots of bits and flag bits in , and cell decoding recovers a cell from when re-encoding yields , extending letterwise to words in . The raw replacement relation and the raw zero predicate on are obtained by lifting cell-list replacement and the unary and binary zero conditions to decoded words, marking undecodable singletons as zero and rejecting lengths other than and . Given an integer , a schedule of capacity , and data size , the codec algebra table over is the word rewriting table with the raw replacement relation and the raw zero predicate (with single-letter generators for any ring ) together with a Boolean table entry selector testing either zero-word membership or replacement.
Self-simulating Machine Hierarchies
Over a tape alphabet and state set , a tape cell label records a symbol in , a Boolean origin mark, and an optional active head state in .✦ A Turing machine transition function sends each state and symbol to a command specifying a written symbol, a next state, and a head motion (left, stay, or right), defining a local three-cell update rule on adjacent tape labels. Using three stack registers (source, destination, and auxiliary), a stack machine compiler translates a stack program on multi-track tape symbols into a one-tape Turing machine, yielding a concrete timed tape transition function over a finite alphabet and finite state set that interprets a universal stack machine fed by a prefix-wrapper decoder and an input decoder reading fixed-width bit packets (whose packet bit width is the cardinality of the set of optional universal stack tokens).
When and are finite, a binary tape label coding of bit width encodes tape cell labels as -bit Boolean vectors with a left inverse✦, and the one-hot coding of and fixes a coding of bit width . Given an input count and gate count , a combinational not-and (NAND) circuit is an ordered sequence of two-input NAND gates wired from the inputs and earlier gates, generating three-wire circuit clauses; a circuit realization of the encoded -bit local transition function fixes a gate count and a combinational NAND circuit with output wires evaluating .
Take parameters with , , , an origin column , and capacity bounding both the certificate variable count and the tableau clause count . An addressable tableau layout assigns cell memory addresses to tape cells of bits and gate blocks of bits, and compiles a schedule of three-wire verification clauses enforcing the initial row, blank boundaries, local NAND transitions, and accepting origin bits against a Boolean assignment assembled from data addresses and a certificate vector in . For a natural number , let be if and the binary bit length of otherwise✦, let be its prefix-free encoding ( true bits, one false delimiter, and the binary digits of )✦, and for Boolean words and , let program specialization prepend a true bit to .✦
Given bit width , gate count , dilation , height , and code length , with and , the layout parameter bounds predicate requires , , , , both the certificate and clause counts to be at most , and (4)✦ When holds for a Boolean program and , the source machine clause schedule of capacity instantiates the tableau layout at origin with the local NAND circuit, the one-hot encodings of the timed tape blank label, initial origin label, accepting output label, and Boolean bit labels, and the initial input row encoding , , and for each verification task the arity , zero-task flag , and the data addresses.✦
For an integer dilation , a self-simulating machine hierarchy consists of a Boolean program and a threshold height such that the self-specialized code satisfies from (4) at every height , and for every verification task and every Boolean assignment on data bit addresses of capacity , there exists a certificate vector satisfying every clause of under the assembled assignment if and only if the codec table entry selector for at height and data size accepts the candidate raw words of length in extracted from (testing the false-side word under the raw zero predicate when , and the pair of false-side and true-side words under the raw replacement relation when ).✦ Every integer admits a self-simulating machine hierarchy of dilation .✦
Given a self-simulating machine hierarchy of dilation and an integer , let be the hierarchy clause schedule✦ and be the hierarchy rewriting table over .✦ For any ring , the machine hierarchy algebra is the table algebra (5)✦ For every , the hierarchy rewriting table is homogeneous✦ and every word in its zero set is nonempty✦, so every commutative ring yields a -algebra augmentation .✦ Letting send each raw bitstring to its single-letter generator in (5), the positive span is the -submodule (6)✦
The Concrete Algebra
Fix the concrete dilation factor ✦, let be the concrete self-simulating machine hierarchy of dilation ✦, and let be its threshold height.✦ The concrete algebra is the machine hierarchy algebra of over at height , (7)✦ The augmentation of in (7) is the hierarchy augmentation .✦ The grading homomorphism of is the -algebra homomorphism obtained by applying (3) to over , (8)✦
The Claim
Theorem 1. For the concrete -algebra with augmentation and every integer , (9)✦ For any self-simulating machine hierarchy with dilation , any integer , and every integer , (10)✦ If is a self-simulating machine hierarchy with dilation , , is a commutative ring of characteristic , and is a matrix over a finite index set with all entries in the positive span of (6), then (11)✦ For any self-simulating machine hierarchy of dilation , any nontrivial ring , and any integer , (12)✦ For every integer , every verification clause schedule of capacity , every integer , and every ring , (13)✦
In the paper, the result reads: there is an infinite, finitely presented, graded unital associative -algebra (, ) such that is nil for every integer , where stands for . Instead of decomposing as a direct sum , the library equips with the polynomial-valued grading (8) and formulates the remaining properties through (9), (10), (11), (12), and (13).
What Is Checked
Claim (9) is stated over the concrete -algebra of (7) and its augmentation at threshold height of the machine hierarchy with dilation . Claims (10), (11), and (12) are stated over an arbitrary self-simulating machine hierarchy of dilation and height , with for (10) and (11), a commutative ring of characteristic and the positive span (6) for (11), and a nontrivial ring for (12). Claim (13) is stated over any integer , verification clause schedule of capacity , integer , and ring , while (3) and (8) are defined for homogeneous word rewriting tables and for .
For those constructions, the library also establishes that ✦, that and are positive for all , and that the coding bit width and the input-decoder packet bit width are positive, as is the tableau clause count of any layout.✦