The Setting
Fix a commutative ring and an integer dilation factor , and set and for every integer . To build a family of finitely presented associative -algebras from finite local word-rewriting tables over alphabets together with block substitutions mapping each letter at height to a block of length at height , one encodes the local verification tableau of a self-simulating machine into cell states and local transition rules. The question is whether fixed parameters and with rule lengths at most yield such tables for all integers from a threshold onward with controlled block embeddings and word structure.
Rewriting Tables, Cuts, and Eligible Intervals
For any alphabet , the word monoid is the free monoid generated by , in which each letter embeds as a one-letter word.✦ Given a unital ring , the word polynomial algebra is the monoid algebra of over , and the basis monomial of a word is the single-term element of with coefficient at . A word-rewriting table over is a pair consisting of a binary replacement relation on and a subset of zero words.✦ The defining relations of in form the subset (1), (1) where each word stands for its basis monomial, and generates a two-sided ideal of . The table algebra of over is the quotient ring of by the congruence of ; the quotient map sends the basis monomial of each word to its table word . When is commutative, given a second table over an alphabet and a monoid homomorphism satisfying whenever and whenever , table substitution produces a unital -algebra homomorphism sending to .✦
Given a predicate on an alphabet , a cut-free word in is a word in which no letter satisfies .✦ A cut interval in with respect to is a word formed from a letter satisfying and a cut-free word .✦
Given a multiplicative monoid with zero and a map , the word evaluation of a word is the product .✦ Given a predicate on a set , an integer , and a word , an eligible interval of parameter in is a pair of integer indices satisfying and for which there exists satisfying such that for all , with when and when .✦
Finite Table Cells and Local Rules
Write for the Boolean set and for the two-element field. A three-bit register state is a triple of bits indexed by , and a verification task is a pair consisting of an arity and a Boolean zero-task flag . For an integer capacity , a cell memory address of capacity is either a data address specified by a Boolean side , a block index , and a position , or a certificate address with .✦ A verification clause of capacity consists of three cell memory addresses of capacity together with a truth function .✦ A verification clause schedule of capacity assigns to each verification task a positive clause count and a family of verification clauses indexed by .✦
For capacity , a block cell position is a core position (), a palette position with color , or the terminal position ; a cell marker is one of the five tags idle, left, boundary, full, or right; and a block metadata record of arity bound is a triple consisting of an arity , a zero-task flag , and a block index , projecting to the verification task (with and default metadata equal to ). A cell syntactic skeleton of capacity and arity bound is a triple pairing a block cell position, a cell marker, and a block metadata record .✦ A cell syntactic skeleton of capacity and arity bound is initial when and its position is , terminal when and its position is , active-head when its marker is boundary or full, and admissible when its marker is not right if initial and not left if terminal. An ordered pair of cell syntactic skeletons of capacity and arity bound is structurally adjacent if their positions are , with , , , or . A cell syntactic skeleton of capacity and arity bound is right-external when its marker is idle, boundary, or non-left at a terminal skeleton, and left-external when its marker is idle or non-right at an initial skeleton. Two skeletons satisfy internal consistency when their arities and zero-task flags agree, is non-initial, is non-terminal, and the block index of equals that of plus when is at and equals that of otherwise.✦ A pair of cell syntactic skeletons of capacity and arity bound is a compatible adjacent skeleton pair when is structurally adjacent and either is right-external and is left-external, or neither is external, satisfies internal consistency, accepts the marker of on the right (allowing left, boundary, or full when the marker of is left, and right otherwise), and accepts the marker of on the left (allowing full or right when the marker of is right, and left otherwise).✦
Over a color set , a palette checker state is one of three states: idle, , or for a sought color .✦ An ordered pair of palette checker states over is a compatible palette checker pair when both are idle, both are for some , and , or and is idle; a palette checker state over satisfies the terminal palette checker condition when for all .
A head computation phase is one of nine stages (acquisition, read-left, read-right, before-gate, after-gate, undo-left, undo-right, finish, or success), among which acquisition, before-gate, after-gate, finish, and success are endpoint phases. A reading head state of capacity is a tuple specifying a side , a clause index , a phase , and a three-bit register state , with default head state . A finite table cell of capacity consists of a cell syntactic skeleton of capacity and arity bound , a palette checker state over , a side-indexed pair of data bits in , a certificate bit in , and a reading head state. A finite table cell of capacity is in the core when its position is a core position, in the palette when its position is a palette position, head-free when its skeleton is not active-head and its checker is not for any color , and satisfies the cell cut condition when its position is and either its marker is idle or its block index is . Reading an address from a cell produces an element of : it equals the data bit of on side when is at matching a data address with block index , equals the certificate bit of when is at matching a certificate address with block index , and equals otherwise; the clause register delta of a verification clause of capacity at a cell is the triple formed by reading the three addresses from . For a schedule and data size , a cell is formatted if its skeleton is admissible, non-palette cells have idle checker, core positions have zero data bits, non-core cells have zero data and certificate bits, idle cells have default metadata, default head, zero true-side data bit, and zero certificate bit, left and right cells have default head, boundary cells have clause , phase acquisition, and register , active-head cells with zero-task flag true have head side false, and full cells have clause in success, clause strictly below for ’s task otherwise, and terminal skeleton in every endpoint phase.✦
For a finite table cell of capacity , a side , a marker , a clause index , a phase , and a register , the idle cell is the cell keeping the position and checker of while resetting the marker to idle, metadata and head to defaults, certificate to , true-side data to , and false-side data to the data bit of on side ; the boundary cell sets the marker to boundary and head side to on the default head; the wing cell sets marker with default head; and the full cell sets marker full with head . Given a bit vector , the canonical block of length concatenates idle default-metadata default-checker default-head zero-certificate cells with zero true-side data across (storing on side false when and otherwise), , and (with zero false-side data outside the core); concatenating canonical blocks across a list of vectors in defines the encoded cell word map.
Given a schedule of capacity , the unary cell transition relates single cells at block boundaries across twelve steps: turning an idle initial cell into , turning a boundary terminal cell into , advancing from acquisition to read-left at a terminal cell, turning from read-left to read-right at an initial cell, exiting from read-right to before-gate at a terminal cell, passing from before-gate to after-gate at a terminal cell when the scheduled clause for the cell’s task and clause index accepts the head register, stepping similarly through undo-left at a terminal cell, undo-right at an initial cell, and finish at a terminal cell, advancing from finish with register at a terminal cell to clause in acquisition or to clause in success when , and flipping the head side of a full terminal cell at clause in success with register when the zero-task flag is false. Two finite table cells of capacity satisfy checker compatibility when adjacent palette cells form a compatible palette checker pair and a palette cell before satisfies the terminal palette checker condition; an ordered pair of finite table cells of capacity is a compatible adjacent cell pair when both their skeletons and checkers are compatible. The binary cell transition relates adjacent cell pairs across eight moves: turning a boundary-and-idle pair into when those resulting skeletons form a compatible pair, shifting a full head between a pair (whose full-and-right skeletons form a compatible pair) left into during read-left or undo-left and right into during read-right or undo-right while adding to the head register during read-left and undo-right (for the task of ) and preserving the register during read-right and undo-left, creating a checker on an idle-checker palette cell after with , advancing from a palette cell of color to an idle-checker palette cell (leaving behind), and swapping two head-free palette cells whose non-color fields agree. Two cell words satisfy the cell-list replacement relation for and when every cell in and is formatted and either are related in either direction by a unary transition or are related in either direction by a binary transition.✦
A cell satisfies the semantic zero condition for when its marker is full and either its phase is acquisition, finish, or success with nonzero register, its phase is after-gate with the scheduled clause rejecting its register, or its phase is success with zero-task flag true.✦ A finite table cell of capacity satisfies the unary zero condition for a schedule of capacity and data size when is unformatted, satisfies the semantic zero condition, or sits at with checker ; a pair of cells of capacity satisfies the binary zero condition when it is not a compatible adjacent cell pair, both lie at the same palette color , or lies at with checker () while is at ; and the cell zero predicate is the predicate holding on such singletons and pairs. Replacing a contiguous factor via cell-list replacement defines a cell rewriting step, whose reflexive-transitive closure is cell reachability; a cell word of capacity survives when no reachable cell word contains a cell zero factor; a cell token of capacity is a cut interval with respect to the cell cut condition such that survives for some cut cell ; and the fragment bound at capacity is given by (2), (2)
Raw Bitstring Codec and Table Algebras
For an integer , the raw alphabet is the set of Boolean vectors of length , and for we write . Cell encoding maps a finite table cell of capacity to a raw letter in by storing integer slots (position tag and index, marker tag, arity, block index, checker tag and index, clause index, and phase tag) in little-endian -bit blocks across positions , storing Boolean flags (zero-task flag, head side, false-side and true-side data bits, certificate bit, and three register bits, padded with false) at positions , and filling remaining bits in with false. For , cell decoding parses those slots and flags back to a candidate cell of capacity and accepts only when encoding recovers the raw letter, lifting letterwise to word decoding. Applying color erasure (replacing any palette cell’s color with and leaving other cells unchanged) to the decoded cell gives the non-color field profile of a raw letter (undefined when decoding fails), lifting letterwise to for ; a non-color field profile is eligible when is defined and its decoded cell is a head-free palette cell.
Given , a schedule of capacity , and a data size , two words satisfy raw word replacement when both decode to cell words satisfying the cell-list replacement relation for and ; a raw letter satisfies raw unary zero when it fails to decode or decodes to a unary-zero cell, while a pair satisfies raw binary zero when both decode to a binary-zero cell pair; and the raw zero predicate holds on singletons satisfying raw unary zero and pairs satisfying raw binary zero. For an integer , a schedule of capacity , and a data size , the codec rewriting table over is the word-rewriting table whose replacement relation is raw word replacement and whose zero set is given by the raw zero predicate, with generators for in its table algebra, one-step rewriting , reachability , and surviving word set of words from which no raw zero factor is reachable. A raw letter satisfies the raw cut condition when decodes to a cut cell, and a raw word is a raw token when is the letterwise encoding of a cell token. The codec table entry predicate for evaluates to true on and raw words when , is empty, and satisfies the raw zero predicate, or when and satisfies raw word replacement.✦
Machine Simulation, Circuits, and Hierarchies
A one-tape Turing machine with tape alphabet , state set , and transition table updates each tape cell label locally from its left, center, and right neighbors: if the center head is present at state , the transition writes the new symbol, keeps the origin mark, and keeps the next state only on stay; if the center head is absent, it keeps symbol and origin while receiving a head moving right from the left neighbor or left from the right neighbor. A stack machine with push, pop, and halt instructions over stack index set , token alphabet , and states compiles into a one-tape machine on multi-track stack symbols (an origin bit and an optional token per stack) and five-mode control states (ready, push-find, pop-find, pop-read, back). A universal stack simulator interprets programs over register indices using simulated registers, front and back tape stacks, and a unary program-counter stack across scanning modes (skip, opcode, and target resolution). For an integer , setting when and equal to the bit-length of otherwise, the prefix encoding of concatenates true bits, one false delimiter bit, and the big-endian binary digits of ; the specialized code of Boolean lists is followed by , , , and . Prepending a bit-reversal and one-hot packet decoder (over the finite packet alphabet of positive packet width) and a wrapper-peeling stage onto the universal stack simulator yields the timed tape machine on register indices (source index , destination index ), fixing its tape alphabet , state set , transition table , blank symbol, origin symbol, Boolean bit symbol, initial state, and accepting output label.
For a tape alphabet and state set , a binary tape label coding of bit width consists of an encoding of labels into Boolean vectors together with a left-inverse decoding; enumerating any finite label set gives its one-hot coding, which for and fixes the bit width and the encoded bit vectors for the blank, initial, accepting, and Boolean bit labels. A combinational not-AND (NAND) circuit of gates on inputs is built inductively from the empty circuit by appending two-input NAND gates drawn from constant Booleans or earlier wire indices, defining Boolean wire evaluation and a list of three-wire defining circuit clauses. A circuit realization of a transition table under a coding of width consists of a -gate NAND circuit on inputs and output wires that computes the encoded local three-cell transition on every -bit input; selecting one realization for fixes the local transition circuit with gate count .
An addressable wire reading of capacity is a Boolean constant or a cell memory address of capacity , an assignment on cell memory addresses of capacity assigns a Boolean to each address, and an addressable clause pairs three wire readings with a truth function , holding under a memory assignment when the truth function yields true on the evaluated wires and compiling to a verification clause (substituting constant wires and converting -valued reads to Booleans). For parameters with , , and , a tableau layout is an origin column subject to the total certificate-count and total clause-count bounds (3), (3) Given a Boolean code , word-length parameter with , positive arity , and zero-task flag , the source input sequence concatenates the fixed header bits (, , , , ) with unnegated references to the (when ) or (when ) data addresses across blocks on side false (and side true when ).✦ Packing tape cell bits () and circuit gate bits () into certificate addresses below defines the tableau clause schedule of capacity , built from four blocks: initial-row clauses fixing column to the initial state bits, columns to the right to the symbol-transformed source input sequence, and remaining columns to blank bits; unit clauses fixing columns and at times to blank bits; lifted local circuit clauses and bidirectional output-equality clauses across interior columns and steps ; and unit clauses fixing column at time to accepting bits. Pairing a data assignment on data addresses with a certificate assignment forms the assembled assignment on all cell memory addresses.✦
For parameters with and , layout admissibility holds when the capacity bounds (3) at hold together with (4), (4)✦ When is layout-admissible for a Boolean code and , choosing , , , and origin produces the source machine tableau layout and its source clause schedule of capacity . Given a data assignment on data addresses of capacity , an arity , a side , and an index , the candidate word reads the bits of at side , block , and positions .✦
For an integer , a self-simulating machine hierarchy of dilation consists of a Boolean program and a threshold such that for every integer , the self-specialized code of makes layout-admissible, and for every verification task and data assignment on data addresses of capacity , there exists a certificate assignment making all tableau clauses of the height- source layout hold under if and only if the codec table entry predicate at height (with the height- source schedule and data size ) returns true on and the candidate word lists and either the empty list when or when . For every integer in a self-simulating machine hierarchy of dilation , the hierarchy schedule is the height- source clause schedule, the hierarchy rewriting table is , and the hierarchy algebra is , writing for . Converting each letter of a word to a vector in , concatenating their canonical blocks of length , and cell-encoding each cell defines the block embedding (carrying each letter into ); the block embedding induces via table substitution a unital -algebra embedding homomorphism . A hierarchy token at height is a raw token for and data size ; the token normal form of a hierarchy token is a chosen word .
The Claim
Theorem 1. Let be an integer and let be a commutative ring. There exists a concrete self-simulating machine hierarchy of dilation with threshold satisfying (5), (5)✦ For every integer , the raw alphabet has size (6), (6)✦ For any integer , verification clause schedule of capacity , and data size , every raw word replacement pair satisfies (7); for any integer , schedule of capacity , and data size , every raw zero word satisfies (8), (7)✦ (8)✦ For any integer in and any word surviving in , the embedded word satisfies (9); at each , there also exists a raw letter whose one-letter word satisfies (10), (9)✦ (10)✦ For every and every hierarchy token at height , its token normal form satisfies (11) and (12), (11)✦ (12)✦ For any integer , schedule of capacity , data size , and surviving word with , there exist a word cut-free for the raw cut condition, a nonempty finite list of raw tokens (), and a cut interval for the raw cut condition satisfying (13), (13)✦ Over any alphabet with cut predicate , if are cut-free and as well as every term of the finite lists and () are cut intervals satisfying , then (14) holds, (14)✦ For any integer , schedule of capacity , data size , and surviving word with , there exist a contiguous factor of and an eligible field profile satisfying (15), (15)✦ For any integer , schedule of capacity , and data size , any raw letters sharing an eligible field profile satisfy (16) in , and any raw letter with an eligible field profile satisfies (17) in , (16)✦ (17)✦ For any integer , schedule of capacity , data size , and word satisfying and in , there exist indices satisfying (18), (18)✦ For any multiplicative monoid with zero , alphabet , map , and word satisfying and for all together with , the letters of satisfy (19), (19)✦
In the paper, the result reads: there are absolute positive integers ( and permitted) such that for any integer there exists giving, for every , a finite alphabet with and a finite table of elementary replacements and zero declarations of length at most defining with three properties: (1) () induces a unital algebra homomorphism preserving nonzero words, and there is a nonzero one-letter word at each parameter; (2) cuts give a bound and finite token list such that every sufficiently long nonzero word decomposes uniquely as with and each token satisfying , , and via internal replacements; (3) eligible runs in nonzero words admit adjacent color transpositions, have pairwise distinct colors, and every sufficiently long nonzero word has an eligible run of length at least . The theorem in the box differs from the paper’s statement by constructing tables and homomorphisms at every integer rather than along the geometric progression , formulating survival and decompositions for words avoiding reachable zero factors alongside algebraic statements in , and separating the cancellation, cut-uniqueness, and interval properties into the claims (5) through (19).
What Is Checked
The claims (5) through (19) are stated over any integer dilation , any commutative ring , any height (nonnegative, positive, at least , or at least the threshold ), any verification clause schedule of capacity , any data size , any cut predicate on an alphabet , any multiplicative monoid with zero , and the self-simulating machine hierarchy constructed from the timed universal stack machine, one-hot tape coding, combinational NAND circuit realization, tableau layout bounds, and raw bitstring cell tables.
For any tableau layout, the total tableau clause count is positive, the tape-coding bit width and packet representation width are positive, and for any machine hierarchy of dilation and any , both and the data size are positive with . The word quotient map into any table algebra is a monoid homomorphism, and the block embedding is a monoid homomorphism sending replacement-related pairs and zero words of to equal and zero elements in .