OctoInformBeta

OpenAI preprint, September 2026 · §2. A hierarchy defined by finite local rules

Proposition 2.2: Self-simulating hierarchies over KK for D≥2D \ge 2 and h≥h0≥4h \ge h_0 \ge 4 with alphabet size 210000h2^{10000h}, length-22 rules, and commuting square-zero runs

Local rewriting tables with block embeddings and token decompositions.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Fix a commutative ring KK and an integer dilation factor D≥2D \ge 2, and set qh=2hq_h = 2^h and Lh=2qh+1L_h = 2q_h + 1 for every integer h≥0h \ge 0. To build a family of finitely presented associative KK-algebras Ah(K)A_h(K) from finite local word-rewriting tables over alphabets Σh\Sigma_h together with block substitutions mapping each letter at height DhDh to a block of length LhL_h at height hh, one encodes the local verification tableau of a self-simulating machine into cell states and local transition rules. The question is whether fixed parameters c=10000c = 10000 and k=10k = 10 with rule lengths at most 22 yield such tables for all integers hh from a threshold h0≥4h_0 \ge 4 onward with controlled block embeddings and word structure.

Rewriting Tables, Cuts, and Eligible Intervals

For any alphabet α\alpha, the word monoid α*\alpha^* is the free monoid generated by α\alpha, in which each letter a∈αa \in \alpha embeds as a one-letter word.✦ Given a unital ring KK, the word polynomial algebra K[α*]K[\alpha^*] is the monoid algebra of α*\alpha^* over KK, and the basis monomial of a word w∈α*w \in \alpha^* is the single-term element of K[α*]K[\alpha^*] with coefficient 11 at ww. A word-rewriting table T=(rep,Z)T = (\mathrm{rep}, Z) over α\alpha is a pair consisting of a binary replacement relation rep\mathrm{rep} on α*\alpha^* and a subset Z⊆α*Z \subseteq \alpha^* of zero words.✦ The defining relations RTR_T of TT in K[α*]K[\alpha^*] form the subset (1), RT={v−w:(v,w)∈rep}∪{z:z∈Z},R_T = \{v - w : (v, w) \in \mathrm{rep}\} \cup \{z : z \in Z\},(1) where each word stands for its basis monomial, and RTR_T generates a two-sided ideal ITI_T of K[α*]K[\alpha^*]. The table algebra AT(K)=K[α*]/ITA_T(K) = K[\alpha^*] / I_T of TT over KK is the quotient ring of K[α*]K[\alpha^*] by the congruence of ITI_T; the quotient map K[α*]→AT(K)K[\alpha^*] \to A_T(K) sends the basis monomial of each word w∈α*w \in \alpha^* to its table word [w]T∈AT(K)[w]_T \in A_T(K). When KK is commutative, given a second table U=(repU,ZU)U = (\mathrm{rep}_U, Z_U) over an alphabet β\beta and a monoid homomorphism f:β*→α*f : \beta^* \to \alpha^* satisfying [f(a)]T=[f(b)]T[f(a)]_T = [f(b)]_T whenever (a,b)∈repU(a, b) \in \mathrm{rep}_U and [f(z)]T=0[f(z)]_T = 0 whenever z∈ZUz \in Z_U, table substitution produces a unital KK-algebra homomorphism AU(K)→AT(K)A_U(K) \to A_T(K) sending [w]U[w]_U to [f(w)]T[f(w)]_T.✦

Given a predicate cut\mathrm{cut} on an alphabet α\alpha, a cut-free word in α*\alpha^* is a word w∈α*w \in \alpha^* in which no letter satisfies cut\mathrm{cut}.✦ A cut interval in α*\alpha^* with respect to cut\mathrm{cut} is a word w=au∈α*w = a u \in \alpha^* formed from a letter a∈αa \in \alpha satisfying cut\mathrm{cut} and a cut-free word u∈α*u \in \alpha^*.✦

Given a multiplicative monoid with zero MM and a map f:α→Mf : \alpha \to M, the word evaluation eval(f,w)∈M\mathrm{eval}(f, w) \in M of a word w=a1⋯am∈α*w = a_1 \cdots a_m \in \alpha^* is the product ∏i=1mf(ai)\prod_{i=1}^m f(a_i).✦ Given a predicate eligible\mathrm{eligible} on a set XX, an integer q≥0q \ge 0, and a word v=t0⋯tm−1∈X*v = t_0 \cdots t_{m-1} \in X^*, an eligible interval of parameter qq in vv is a pair of integer indices (a,e)(a, e) satisfying a<e≤ma < e \le m and q≤100(e−a)q \le 100(e - a) for which there exists t∈Xt \in X satisfying eligible\mathrm{eligible} such that ti=tt_i = t for all a≤i<ea \le i < e, with ta−1≠tt_{a-1} \ne t when a>0a > 0 and te≠tt_e \ne t when e<me < m.✦

Finite Table Cells and Local Rules

Write 𝔹={false,true}\mathbb{B} = \{\mathrm{false}, \mathrm{true}\} for the Boolean set and 𝔽2\mathbb{F}_2 for the two-element field. A three-bit register state r∈𝔽23r \in \mathbb{F}_2^3 is a triple of bits indexed by {0,1,2}\{0, 1, 2\}, and a verification task τ=(lτ,Zτ)\tau = (l_\tau, Z_\tau) is a pair consisting of an arity lτ∈{0,…,9}l_\tau \in \{0, \dots, 9\} and a Boolean zero-task flag Zτ∈𝔹Z_\tau \in \mathbb{B}. For an integer capacity q≥0q \ge 0, a cell memory address of capacity qq is either a data address (s,b,p)(s, b, p) specified by a Boolean side s∈𝔹s \in \mathbb{B}, a block index b∈{0,…,9}b \in \{0, \dots, 9\}, and a position 0≤p<q0 \le p < q, or a certificate address pp with 0≤p<q0 \le p < q.✦ A verification clause CC of capacity qq consists of three cell memory addresses (a0,a1,a2)(a_0, a_1, a_2) of capacity qq together with a truth function 𝔽23→𝔹\mathbb{F}_2^3 \to \mathbb{B}.✦ A verification clause schedule SS of capacity qq assigns to each verification task τ\tau a positive clause count countS(τ)∈{1,…,q}\mathrm{count}_S(\tau) \in \{1, \dots, q\} and a family of verification clauses Sτ(j)S_\tau(j) indexed by 0≤j<q0 \le j < q.✦

For capacity q≥0q \ge 0, a block cell position is a core position core(p)\mathrm{core}(p) (0≤p<q0 \le p < q), a palette position palette(x)\mathrm{palette}(x) with color 0≤x<q0 \le x < q, or the terminal position stop\mathrm{stop}; a cell marker is one of the five tags idle, left, boundary, full, or right; and a block metadata record of arity bound kk is a triple (l,Z,b)(l, Z, b) consisting of an arity 0≤l<k0 \le l < k, a zero-task flag Z∈𝔹Z \in \mathbb{B}, and a block index 0≤b≤l0 \le b \le l, projecting to the verification task (l,Z)(l, Z) (with k=10k = 10 and default metadata equal to (0,false,0)(0, \mathrm{false}, 0)). A cell syntactic skeleton cc of capacity qq and arity bound kk is a triple pairing a block cell position, a cell marker, and a block metadata record (l,Z,b)(l, Z, b).✦ A cell syntactic skeleton cc of capacity qq and arity bound kk is initial when b=0b = 0 and its position is core(0)\mathrm{core}(0), terminal when b=lb = l and its position is stop\mathrm{stop}, 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 (a,b)(a, b) of cell syntactic skeletons of capacity qq and arity bound kk is structurally adjacent if their positions are (core(p),core(p+1))(\mathrm{core}(p), \mathrm{core}(p+1)), (core(p),palette(x))(\mathrm{core}(p), \mathrm{palette}(x)) with p+1=qp + 1 = q, (palette(x),palette(y))(\mathrm{palette}(x), \mathrm{palette}(y)), (palette(x),stop)(\mathrm{palette}(x), \mathrm{stop}), or (stop,core(0))(\mathrm{stop}, \mathrm{core}(0)). A cell syntactic skeleton aa of capacity qq and arity bound kk 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 (a,b)(a, b) satisfy internal consistency when their arities and zero-task flags agree, bb is non-initial, aa is non-terminal, and the block index of bb equals that of aa plus 11 when aa is at stop\mathrm{stop} and equals that of aa otherwise.✦ A pair (a,b)(a, b) of cell syntactic skeletons of capacity qq and arity bound kk is a compatible adjacent skeleton pair when (a,b)(a, b) is structurally adjacent and either aa is right-external and bb is left-external, or neither is external, (a,b)(a, b) satisfies internal consistency, aa accepts the marker of bb on the right (allowing left, boundary, or full when the marker of aa is left, and right otherwise), and bb accepts the marker of aa on the left (allowing full or right when the marker of bb is right, and left otherwise).✦

Over a color set 𝒞\mathcal{C}, a palette checker state is one of three states: idle, passed(x)\mathrm{passed}(x), or head(x)\mathrm{head}(x) for a sought color x∈𝒞x \in \mathcal{C}.✦ An ordered pair (s1,s2)(s_1, s_2) of palette checker states over 𝒞\mathcal{C} is a compatible palette checker pair when both are idle, both are passed(x)\mathrm{passed}(x) for some x∈𝒞x \in \mathcal{C}, s1=passed(x)s_1 = \mathrm{passed}(x) and s2=head(x)s_2 = \mathrm{head}(x), or s1=head(x)s_1 = \mathrm{head}(x) and s2s_2 is idle; a palette checker state ss over 𝒞\mathcal{C} satisfies the terminal palette checker condition when s≠passed(x)s \ne \mathrm{passed}(x) for all x∈𝒞x \in \mathcal{C}.

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 qq is a tuple (s,j,ϕ,r)(s, j, \phi, r) specifying a side s∈𝔹s \in \mathbb{B}, a clause index 0≤j<q0 \le j < q, a phase ϕ\phi, and a three-bit register state rr, with default head state (false,0,acquisition,0)(\mathrm{false}, 0, \mathrm{acquisition}, 0). A finite table cell cc of capacity qq consists of a cell syntactic skeleton of capacity qq and arity bound 1010, a palette checker state over {0,…,q−1}\{0, \dots, q-1\}, a side-indexed pair of data bits in 𝔽2\mathbb{F}_2, a certificate bit in 𝔽2\mathbb{F}_2, and a reading head state. A finite table cell cc of capacity qq 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 head(x)\mathrm{head}(x) for any color xx, and satisfies the cell cut condition when its position is core(0)\mathrm{core}(0) and either its marker is idle or its block index is 00. Reading an address from a cell cc produces an element of 𝔽2\mathbb{F}_2: it equals the data bit of cc on side ss when cc is at core(p)\mathrm{core}(p) matching a data address (s,b,p)(s, b, p) with block index bb, equals the certificate bit of cc when cc is at core(p)\mathrm{core}(p) matching a certificate address pp with block index 00, and equals 00 otherwise; the clause register delta δ(C,c)∈𝔽23\delta(C, c) \in \mathbb{F}_2^3 of a verification clause C=(a0,a1,a2)C = (a_0, a_1, a_2) of capacity qq at a cell cc is the triple formed by reading the three addresses a0,a1,a2a_0, a_1, a_2 from cc. For a schedule SS and data size d≥0d \ge 0, a cell cc is formatted if its skeleton is admissible, non-palette cells have idle checker, core positions p≥dp \ge d 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 00, phase acquisition, and register 00, active-head cells with zero-task flag true have head side false, and full cells have clause 00 in success, clause strictly below countS(τ)\mathrm{count}_S(\tau) for cc’s task τ\tau otherwise, and terminal skeleton in every endpoint phase.✦

For a finite table cell cc of capacity qq, a side s∈𝔹s \in \mathbb{B}, a marker mm, a clause index 0≤j<q0 \le j < q, a phase ϕ\phi, and a register r∈𝔽23r \in \mathbb{F}_2^3, the idle cell idle(c,s)\mathrm{idle}(c, s) is the cell keeping the position and checker of cc while resetting the marker to idle, metadata and head to defaults, certificate to 00, true-side data to 00, and false-side data to the data bit of cc on side ss; the boundary cell boundary(c,s)\mathrm{boundary}(c, s) sets the marker to boundary and head side to ss on the default head; the wing cell wing(c,m)\mathrm{wing}(c, m) sets marker mm with default head; and the full cell full(c,s,j,ϕ,r)\mathrm{full}(c, s, j, \phi, r) sets marker full with head (s,j,ϕ,r)(s, j, \phi, r). Given a bit vector u∈𝔽2du \in \mathbb{F}_2^d, the canonical block blockq(u)\mathrm{block}_q(u) of length 2q+12q + 1 concatenates idle default-metadata default-checker default-head zero-certificate cells with zero true-side data across core(0),…,core(q−1)\mathrm{core}(0), \dots, \mathrm{core}(q-1) (storing uru_r on side false when r<dr < d and 00 otherwise), palette(0),…,palette(q−1)\mathrm{palette}(0), \dots, \mathrm{palette}(q-1), and stop\mathrm{stop} (with zero false-side data outside the core); concatenating canonical blocks across a list of vectors in 𝔽2d\mathbb{F}_2^d defines the encoded cell word map.

Given a schedule SS of capacity qq, the unary cell transition relates single cells at block boundaries across twelve steps: turning an idle initial cell idle(c,s)\mathrm{idle}(c, s) into boundary(c,s)\mathrm{boundary}(c, s), turning a boundary terminal cell boundary(c,s)\mathrm{boundary}(c, s) into full(c,s,0,acquisition,0)\mathrm{full}(c, s, 0, \mathrm{acquisition}, 0), 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 00 at a terminal cell to clause j+1j + 1 in acquisition or to clause 00 in success when j+1=countS(τ)j + 1 = \mathrm{count}_S(\tau), and flipping the head side of a full terminal cell at clause 00 in success with register 00 when the zero-task flag is false. Two finite table cells (a,b)(a, b) of capacity qq satisfy checker compatibility when adjacent palette cells form a compatible palette checker pair and a palette cell before stop\mathrm{stop} satisfies the terminal palette checker condition; an ordered pair (a,b)(a, b) of finite table cells of capacity qq 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 (boundary(a,s),idle(b,s))(\mathrm{boundary}(a, s), \mathrm{idle}(b, s)) into (wing(a,left),boundary(b,s))(\mathrm{wing}(a, \mathrm{left}), \mathrm{boundary}(b, s)) when those resulting skeletons form a compatible pair, shifting a full head between a pair (a,b)(a, b) (whose full-and-right skeletons form a compatible pair) left into aa during read-left or undo-left and right into bb during read-right or undo-right while adding δ(Sτ(j),a)\delta(S_\tau(j), a) to the head register during read-left and undo-right (for the task τ\tau of aa) and preserving the register during read-right and undo-left, creating a checker head(x)\mathrm{head}(x) on an idle-checker palette cell after core(p)\mathrm{core}(p) with p+1=qp + 1 = q, advancing head(x)\mathrm{head}(x) from a palette cell of color v≠xv \ne x to an idle-checker palette cell (leaving passed(x)\mathrm{passed}(x) behind), and swapping two head-free palette cells whose non-color fields agree. Two cell words v,wv, w satisfy the cell-list replacement relation for SS and dd when every cell in vv and ww is formatted and either v=[a],w=[b]v = [a], w = [b] are related in either direction by a unary transition or v=[a,b],w=[a′,b′]v = [a, b], w = [a', b'] are related in either direction by a binary transition.✦

A cell cc satisfies the semantic zero condition for SS 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 cc of capacity qq satisfies the unary zero condition for a schedule SS of capacity qq and data size d≥0d \ge 0 when cc is unformatted, satisfies the semantic zero condition, or sits at palette(x)\mathrm{palette}(x) with checker passed(x)\mathrm{passed}(x); a pair (a,b)(a, b) of cells of capacity qq satisfies the binary zero condition when it is not a compatible adjacent cell pair, both lie at the same palette color xx, or aa lies at palette(x)\mathrm{palette}(x) with checker head(y)\mathrm{head}(y) (y≠xy \ne x) while bb is at stop\mathrm{stop}; 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 ww of capacity qq survives when no reachable cell word contains a cell zero factor; a cell token of capacity qq is a cut interval tt with respect to the cell cut condition such that tbt b survives for some cut cell bb; and the fragment bound B(q)B(q) at capacity qq is given by (2), B(q)=12(17q+3).B(q) = 12(17q + 3).(2)

Raw Bitstring Codec and Table Algebras

For an integer h≥0h \ge 0, the raw alphabet Σh=𝔹10000h\Sigma_h = \mathbb{B}^{10000 h} is the set of Boolean vectors of length 10000h10000 h, and for h>0h > 0 we write Bh=B(qh)B_h = B(q_h). Cell encoding maps a finite table cell cc of capacity qhq_h to a raw letter in Σh\Sigma_h by storing 3232 integer slots (position tag and index, marker tag, arity, block index, checker tag and index, clause index, and phase tag) in little-endian 2h2h-bit blocks across positions 0≤i<64h0 \le i < 64h, storing 512512 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 64h≤i<64h+51264h \le i < 64h + 512, and filling remaining bits in {0,…,10000h−1}\{0, \dots, 10000h - 1\} with false. For h>0h > 0, cell decoding parses those slots and flags back to a candidate cell cc of capacity qhq_h and accepts cc only when encoding cc recovers the raw letter, lifting letterwise to word decoding. Applying color erasure (replacing any palette cell’s color with 00 and leaving other cells unchanged) to the decoded cell gives the non-color field profile ϕh(a)\phi_h(a) of a raw letter a∈Σha \in \Sigma_h (undefined when decoding fails), lifting letterwise to ϕ‾h(w)\bar{\phi}_h(w) for w∈Σh*w \in \Sigma_h^*; a non-color field profile ξ\xi is eligible when ξ\xi is defined and its decoded cell is a head-free palette cell.

Given h>0h > 0, a schedule SS of capacity qhq_h, and a data size d≥0d \ge 0, two words v,w∈Σh*v, w \in \Sigma_h^* satisfy raw word replacement when both decode to cell words satisfying the cell-list replacement relation for SS and dd; a raw letter a∈Σha \in \Sigma_h satisfies raw unary zero when it fails to decode or decodes to a unary-zero cell, while a pair (a,b)(a, b) 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 h>0h > 0, a schedule SS of capacity qhq_h, and a data size d≥0d \ge 0, the codec rewriting table Th(S,d)T_h(S, d) over Σh\Sigma_h 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 [a]Th(S,d)[a]_{T_h(S, d)} for a∈Σha \in \Sigma_h in its table algebra, one-step rewriting →Th(S,d)\to_{T_h(S, d)}, reachability →Th(S,d)*\to^*_{T_h(S, d)}, and surviving word set 𝒮(Th(S,d))⊆Σh*\mathcal{S}(T_h(S, d)) \subseteq \Sigma_h^* of words from which no raw zero factor is reachable. A raw letter a∈Σha \in \Sigma_h satisfies the raw cut condition when aa decodes to a cut cell, and a raw word t∈Σh*t \in \Sigma_h^* is a raw token when tt is the letterwise encoding of a cell token. The codec table entry predicate for (S,d)(S, d) evaluates to true on z∈𝔹z \in \mathbb{B} and raw words v,w∈Σh*v, w \in \Sigma_h^* when z=truez = \mathrm{true}, ww is empty, and vv satisfies the raw zero predicate, or when z=falsez = \mathrm{false} and (v,w)(v, w) satisfies raw word replacement.✦

Machine Simulation, Circuits, and Hierarchies

A one-tape Turing machine with tape alphabet Γ\Gamma, state set QQ, and transition table δ:Q×Γ→Γ×Q×{left,stay,right}\delta : Q \times \Gamma \to \Gamma \times Q \times \{\mathrm{left}, \mathrm{stay}, \mathrm{right}\} updates each tape cell label (𝑠𝑦𝑚𝑏𝑜𝑙,𝑜𝑟𝑖𝑔𝑖𝑛,ℎ𝑒𝑎𝑑)∈Γ×𝔹×({none}∪Q)(\mathit{symbol}, \mathit{origin}, \mathit{head}) \in \Gamma \times \mathbb{B} \times (\{\mathrm{none}\} \cup Q) locally from its left, center, and right neighbors: if the center head is present at state qq, the transition δ(q,𝑠𝑦𝑚𝑏𝑜𝑙)\delta(q, \mathit{symbol}) 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 JJ, token alphabet Γ0\Gamma_0, and states Q0Q_0 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 JJ 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 n≥0n \ge 0, setting b(n)=1b(n) = 1 when n=0n = 0 and equal to the bit-length of nn otherwise, the prefix encoding e(n)e(n) of nn concatenates b(n)b(n) true bits, one false delimiter bit, and the b(n)b(n) big-endian binary digits of nn; the specialized code of Boolean lists (t,v)(t, v) is true\mathrm{true} followed by e(|t|)e(|t|), tt, e(|v|)e(|v|), and vv. 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 J0={0,1,none}J_0 = \{0, 1, \mathrm{none}\} (source index 11, destination index 00), fixing its tape alphabet Γtt\Gamma_{\mathrm{tt}}, state set QttQ_{\mathrm{tt}}, transition table δtt\delta_{\mathrm{tt}}, blank symbol, origin symbol, Boolean bit symbol, initial state, and accepting output label.

For a tape alphabet Γ\Gamma and state set QQ, a binary tape label coding of bit width β>0\beta > 0 consists of an encoding of labels into Boolean vectors 𝔹β\mathbb{B}^\beta together with a left-inverse decoding; enumerating any finite label set gives its one-hot coding, which for Γtt\Gamma_{\mathrm{tt}} and QttQ_{\mathrm{tt}} fixes the bit width β>0\beta > 0 and the encoded bit vectors for the blank, initial, accepting, and Boolean bit labels. A combinational not-AND (NAND) circuit of gg gates on II 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 3g3g three-wire defining circuit clauses. A circuit realization of a transition table δ\delta under a coding of width β\beta consists of a gg-gate NAND circuit on 3β3\beta inputs and β\beta output wires that computes the encoded local three-cell transition on every 3β3\beta-bit input; selecting one realization for δtt\delta_{\mathrm{tt}} fixes the local transition circuit with gate count gg.

An addressable wire reading of capacity qq is a Boolean constant or a cell memory address of capacity qq, an assignment on cell memory addresses of capacity qq assigns a Boolean to each address, and an addressable clause pairs three wire readings with a truth function 𝔹3→𝔹\mathbb{B}^3 \to \mathbb{B}, 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 𝔽2\mathbb{F}_2-valued reads to Booleans). For parameters (q,β,g,m,W)(q, \beta, g, m, W) with β>0\beta > 0, m>0m > 0, and W≥3W \ge 3, a tableau layout is an origin column 0≤o<W0 \le o < W subject to the total certificate-count and total clause-count bounds (3), βWm+g(W−2)(m−1)≤q,2βW+2β(m−1)+(3g+2β)(W−2)(m−1)+β≤q.\beta W m + g(W - 2)(m - 1) \le q, \qquad 2\beta W + 2\beta(m - 1) + (3g + 2\beta)(W - 2)(m - 1) + \beta \le q.(3) Given a Boolean code aa, word-length parameter HH with 0<10000H≤q0 < 10000 H \le q, positive arity l≤10l \le 10, and zero-task flag Z∈𝔹Z \in \mathbb{B}, the source input sequence concatenates the fixed header bits (e(|a|)e(|a|), aa, e(H)e(H), e(l)e(l), ZZ) with unnegated references to the l⋅10000Hl \cdot 10000 H (when Z=trueZ = \mathrm{true}) or 2l⋅10000H2l \cdot 10000 H (when Z=falseZ = \mathrm{false}) data addresses across blocks 0≤i<l0 \le i < l on side false (and side true when Z=falseZ = \mathrm{false}).✦ Packing tape cell bits (m×W×βm \times W \times \beta) and circuit gate bits ((m−1)×(W−2)×g(m - 1) \times (W - 2) \times g) into certificate addresses below qq defines the tableau clause schedule of capacity qq, built from four blocks: initial-row clauses fixing column oo 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 00 and W−1W - 1 at times 1≤t<m1 \le t < m to blank bits; lifted local circuit clauses and bidirectional output-equality clauses across interior columns 1≤j≤W−21 \le j \le W - 2 and steps 0≤t<m−10 \le t < m - 1; and unit clauses fixing column oo at time m−1m - 1 to accepting bits. Pairing a data assignment μ\mu on data addresses with a certificate assignment γ∈𝔹q\gamma \in \mathbb{B}^q forms the assembled assignment μ⊕γ\mu \oplus \gamma on all cell memory addresses.✦

For parameters (β,g,D,h,n)(\beta, g, D, h, n) with m=2⌊h/5⌋m = 2^{\lfloor h/5 \rfloor} and W=4mW = 4m, layout admissibility holds when the capacity bounds (3) at qh=2hq_h = 2^h hold together with (4), 64h+512≤10000h,10≤22h,qh≤22h,10000Dh≤qh,n+2b(n)+2b(Dh)+12+20(10000Dh)<⌊m/4⌋.\begin{aligned} 64h + 512 \le 10000h, \qquad 10 \le 2^{2h}, \qquad q_h \le 2^{2h}, \qquad 10000 D h \le q_h, \\ n + 2 b(n) + 2 b(Dh) + 12 + 20(10000 D h) < \lfloor m/4 \rfloor. \end{aligned}(4)✦ When (β,g,D,h,|a|)(\beta, g, D, h, |a|) is layout-admissible for a Boolean code aa and 10000Dh>010000 D h > 0, choosing q=qhq = q_h, m=2⌊h/5⌋m = 2^{\lfloor h/5 \rfloor}, W=4mW = 4m, and origin o=2mo = 2m produces the source machine tableau layout and its source clause schedule of capacity qhq_h. Given a data assignment μ\mu on data addresses of capacity q≥10000Hq \ge 10000 H, an arity l≤10l \le 10, a side s∈𝔹s \in \mathbb{B}, and an index 0≤i<l0 \le i < l, the candidate word wH,i(μ,s)∈ΣHw_{H,i}(\mu, s) \in \Sigma_H reads the bits of μ\mu at side ss, block ii, and positions 0≤j<10000H0 \le j < 10000 H.✦

For an integer D≥2D \ge 2, a self-simulating machine hierarchy ℋ\mathcal{H} of dilation DD consists of a Boolean program PP and a threshold h0≥4h_0 \ge 4 such that for every integer h≥h0h \ge h_0, the self-specialized code aa of (P,P)(P, P) makes (β,g,D,h,|a|)(\beta, g, D, h, |a|) layout-admissible, and for every verification task τ=(lτ,Zτ)\tau = (l_\tau, Z_\tau) and data assignment μ\mu on data addresses of capacity qhq_h, there exists a certificate assignment γ∈𝔹qh\gamma \in \mathbb{B}^{q_h} making all tableau clauses of the height-hh source layout hold under μ⊕γ\mu \oplus \gamma if and only if the codec table entry predicate at height DhD h (with the height-DhDh source schedule and data size 10000D2h10000 D^2 h) returns true on ZτZ_\tau and the candidate word lists (wDh,0(μ,false),…,wDh,lτ(μ,false))(w_{Dh,0}(\mu, \mathrm{false}), \dots, w_{Dh,l_\tau}(\mu, \mathrm{false})) and either the empty list when Zτ=trueZ_\tau = \mathrm{true} or (wDh,0(μ,true),…,wDh,lτ(μ,true))(w_{Dh,0}(\mu, \mathrm{true}), \dots, w_{Dh,l_\tau}(\mu, \mathrm{true})) when Zτ=falseZ_\tau = \mathrm{false}. For every integer h≥h0h \ge h_0 in a self-simulating machine hierarchy ℋ\mathcal{H} of dilation DD, the hierarchy schedule ShS_h is the height-hh source clause schedule, the hierarchy rewriting table is Th=Th(Sh,10000Dh)T_h = T_h(S_h, 10000 D h), and the hierarchy algebra is Ah(K)=ATh(K)A_h(K) = A_{T_h}(K), writing [w]Ah(K)[w]_{A_h(K)} for [w]Th[w]_{T_h}. Converting each letter of a word w∈ΣDh*w \in \Sigma_{Dh}^* to a vector in 𝔽210000Dh\mathbb{F}_2^{10000 D h}, concatenating their canonical blocks blockqh\mathrm{block}_{q_h} of length Lh=2qh+1L_h = 2q_h + 1, and cell-encoding each cell defines the block embedding Eh:ΣDh*→Σh*E_h : \Sigma_{Dh}^* \to \Sigma_h^* (carrying each letter into ΣhLh\Sigma_h^{L_h}); the block embedding EhE_h induces via table substitution a unital KK-algebra embedding homomorphism ιh:ADh(K)→Ah(K)\iota_h : A_{Dh}(K) \to A_h(K). A hierarchy token at height h≥h0h \ge h_0 is a raw token t∈Σh*t \in \Sigma_h^* for ShS_h and data size 10000Dh10000 D h; the token normal form of a hierarchy token tt is a chosen word ut∈ΣDh*u_t \in \Sigma_{Dh}^*.

The Claim

Theorem 1. Let D≥2D \ge 2 be an integer and let KK be a commutative ring. There exists a concrete self-simulating machine hierarchy ℋ(D)\mathcal{H}(D) of dilation DD with threshold h0≥4h_0 \ge 4 satisfying (5), ℋ(D) is a self-simulating machine hierarchy of dilation D with threshold h0≥4.\mathcal{H}(D) \text{ is a self-simulating machine hierarchy of dilation } D \text{ with threshold } h_0 \ge 4.(5)✦ For every integer h≥0h \ge 0, the raw alphabet Σh\Sigma_h has size (6), |Σh|=210000h.|\Sigma_h| = 2^{10000 h}.(6)✦ For any integer h≥4h \ge 4, verification clause schedule SS of capacity qhq_h, and data size d≥0d \ge 0, every raw word replacement pair (v,w)(v, w) satisfies (7); for any integer h>0h > 0, schedule SS of capacity qhq_h, and data size d≥0d \ge 0, every raw zero word zz satisfies (8), |v|=|w|and1≤|v|≤2,|v| = |w| \quad \text{and} \quad 1 \le |v| \le 2,(7)✦ 1≤|z|≤2.1 \le |z| \le 2.(8)✦ For any integer h≥h0h \ge h_0 in ℋ(D)\mathcal{H}(D) and any word w∈ΣDh*w \in \Sigma_{Dh}^* surviving in TDhT_{Dh}, the embedded word Eh(w)E_h(w) satisfies (9); at each h≥h0h \ge h_0, there also exists a raw letter c∈Σhc \in \Sigma_h whose one-letter word satisfies (10), Eh(w)∈𝒮(Th),E_h(w) \in \mathcal{S}(T_h),(9)✦ c∈𝒮(Th).c \in \mathcal{S}(T_h).(10)✦ For every h≥h0h \ge h_0 and every hierarchy token tt at height hh, its token normal form ut∈ΣDh*u_t \in \Sigma_{Dh}^* satisfies (11) and (12), 1≤|ut|≤10,|t|=Lh|ut|,t→Th*Eh(ut),1 \le |u_t| \le 10, \qquad |t| = L_h |u_t|, \qquad t \to^*_{T_h} E_h(u_t),(11)✦ [t]Ah(K)=ιh([ut]ADh(K)).[t]_{A_h(K)} = \iota_h\bigl([u_t]_{A_{Dh}(K)}\bigr).(12)✦ For any integer h≥4h \ge 4, schedule SS of capacity qhq_h, data size d≥0d \ge 0, and surviving word w∈𝒮(Th(S,d))w \in \mathcal{S}(T_h(S, d)) with |w|>2Bh|w| > 2 B_h, there exist a word p∈Σh*p \in \Sigma_h^* cut-free for the raw cut condition, a nonempty finite list of raw tokens t1,…,trt_1, \dots, t_r (r≥1r \ge 1), and a cut interval s∈Σh*s \in \Sigma_h^* for the raw cut condition satisfying (13), w=pt1⋯trs,|p|≤Bh,|s|≤Bh.w = p \, t_1 \cdots t_r \, s, \qquad |p| \le B_h, \qquad |s| \le B_h.(13)✦ Over any alphabet α\alpha with cut predicate cut\mathrm{cut}, if p,p′∈α*p, p' \in \alpha^* are cut-free and s,s′s, s' as well as every term of the finite lists (t1,…,tr)(t_1, \dots, t_r) and (t1′,…,tr′′)(t'_1, \dots, t'_{r'}) (r,r′≥0r, r' \ge 0) are cut intervals satisfying pt1⋯trs=p′t1′⋯tr′′s′p \, t_1 \cdots t_r \, s = p' \, t'_1 \cdots t'_{r'} \, s', then (14) holds, p=p′,(t1,…,tr)=(t1′,…,tr′′),s=s′.p = p', \qquad (t_1, \dots, t_r) = (t'_1, \dots, t'_{r'}), \qquad s = s'.(14)✦ For any integer h≥4h \ge 4, schedule SS of capacity qhq_h, data size d≥0d \ge 0, and surviving word w∈𝒮(Th(S,d))w \in \mathcal{S}(T_h(S, d)) with |w|>2Bh|w| > 2 B_h, there exist a contiguous factor vv of ww and an eligible field profile ξ\xi satisfying (15), |v|≥2,100|v|≥qh,ϕh(a)=ξ for every letter a of v.|v| \ge 2, \qquad 100 |v| \ge q_h, \qquad \phi_h(a) = \xi \text{ for every letter } a \text{ of } v.(15)✦ For any integer h≥4h \ge 4, schedule SS of capacity qhq_h, and data size d≥0d \ge 0, any raw letters x,y∈Σhx, y \in \Sigma_h sharing an eligible field profile ξ\xi satisfy (16) in ATh(S,d)(K)A_{T_h(S, d)}(K), and any raw letter x∈Σhx \in \Sigma_h with an eligible field profile satisfies (17) in ATh(S,d)(K)A_{T_h(S, d)}(K), [x]Th(S,d)[y]Th(S,d)=[y]Th(S,d)[x]Th(S,d),[x]_{T_h(S, d)} [y]_{T_h(S, d)} = [y]_{T_h(S, d)} [x]_{T_h(S, d)},(16)✦ [x]Th(S,d)2=0.[x]_{T_h(S, d)}^2 = 0.(17)✦ For any integer h≥4h \ge 4, schedule SS of capacity qhq_h, data size d≥0d \ge 0, and word w∈Σh*w \in \Sigma_h^* satisfying |w|≥2Bh+1|w| \ge 2 B_h + 1 and eval(c↦[c]Th(S,d),w)≠0\mathrm{eval}(c \mapsto [c]_{T_h(S, d)}, w) \ne 0 in ATh(S,d)(K)A_{T_h(S, d)}(K), there exist indices a,ea, e satisfying (18), (a,e) is an eligible interval of parameter qh in ϕ‾h(w).(a, e) \text{ is an eligible interval of parameter } q_h \text{ in } \bar{\phi}_h(w).(18)✦ For any multiplicative monoid with zero MM, alphabet α\alpha, map f:α→Mf : \alpha \to M, and word w=a1⋯am∈α*w = a_1 \cdots a_m \in \alpha^* satisfying f(ai)f(aj)=f(aj)f(ai)f(a_i) f(a_j) = f(a_j) f(a_i) and f(ai)2=0f(a_i)^2 = 0 for all 1≤i,j≤m1 \le i, j \le m together with eval(f,w)≠0\mathrm{eval}(f, w) \ne 0, the letters of ww satisfy (19), ai≠ajfor all 1≤i<j≤m.a_i \ne a_j \quad \text{for all } 1 \le i < j \le m.(19)✦

In the paper, the result reads: there are absolute positive integers c,kc, k (c=10000c = 10000 and k=10k = 10 permitted) such that for any integer D≥2D \ge 2 there exists h0h_0 giving, for every h∈{h0,h0D,h0D2,…}h \in \{h_0, h_0 D, h_0 D^2, \dots\}, a finite alphabet Σh\Sigma_h with |Σh|≤2ch|\Sigma_h| \le 2^{ch} and a finite table of elementary replacements and zero declarations of length at most kk defining Ah(K)A_h(K) with three properties: (1) Eh:ΣDh→ΣhLhE_h : \Sigma_{Dh} \to \Sigma_h^{L_h} (Lh=2qh+1L_h = 2q_h + 1) induces a unital algebra homomorphism ADh(K)→Ah(K)A_{Dh}(K) \to A_h(K) preserving nonzero words, and there is a nonzero one-letter word at each parameter; (2) cuts give a bound BhB_h and finite token list 𝒯h\mathcal{T}_h such that every sufficiently long nonzero word decomposes uniquely as pt1⋯trsp t_1 \cdots t_r s with |p|,|s|≤Bh|p|, |s| \le B_h and each token tt satisfying 1≤|ut|≤k1 \le |u_t| \le k, |t|=Lh|ut||t| = L_h |u_t|, and [t]Ah(K)=[Eh(ut)]Ah(K)[t]_{A_h(K)} = [E_h(u_t)]_{A_h(K)} 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 qh/100q_h / 100. The theorem in the box differs from the paper’s statement by constructing tables and homomorphisms at every integer h≥h0h \ge h_0 rather than along the geometric progression {h0Dm:m≥0}\{h_0 D^m : m \ge 0\}, formulating survival and decompositions for words avoiding reachable zero factors alongside algebraic statements in Ah(K)A_h(K), 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 D≥2D \ge 2, any commutative ring KK, any height hh (nonnegative, positive, at least 44, or at least the threshold h0≥4h_0 \ge 4), any verification clause schedule SS of capacity qh=2hq_h = 2^h, any data size d≥0d \ge 0, any cut predicate on an alphabet α\alpha, any multiplicative monoid with zero MM, 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 β\beta and packet representation width are positive, and for any machine hierarchy of dilation D≥2D \ge 2 and any h≥h0h \ge h_0, both hh and the data size 10000Dh10000 D h are positive with Dh≥h0D h \ge h_0. The word quotient map into any table algebra is a monoid homomorphism, and the block embedding Eh:ΣDh*→Σh*E_h : \Sigma_{Dh}^* \to \Sigma_h^* is a monoid homomorphism sending replacement-related pairs and zero words of TDhT_{Dh} to equal and zero elements in Ah(K)A_h(K).