OctoInformBeta

OpenAI preprint, September 2026 · §3. Cancellation and the matrix-nil algebra

Proposition 3.6 [Eventual vanishing of every fixed test]: For a machine hierarchy with large dilation factor over commutative rings of characteristic two, alongside a stopping index

Eventual vanishing of matrix letter and chunk tests.

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

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 nn and summing produces a matrix over the algebra. The questions are whether every such matrix sum vanishes for all sufficiently large nn 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 HH, DD, and nn, the hierarchy height Hn(H,D)H_n(H, D) is the natural number defined by (1): Hn(H,D)=HDn.H_n(H, D) = H D^n.(1)✦

Starting from natural numbers dd and kk, a sequence s:ℕ→ℕs : \mathbb{N} \to \mathbb{N}, and a natural number nn, the hierarchy dimension dn(d,k,s)d_n(d, k, s) is the natural number given recursively by d0(d,k,s)=dd_0(d, k, s) = d and (2): dn+1(d,k,s)=ks(n)kdn(d,k,s).d_{n+1}(d, k, s) = k \, s(n)^k \, d_n(d, k, s).(2)✦

Let α\alpha be an alphabet and RR a semiring, write α*\alpha^* for the free monoid of words over α\alpha, and write R[α*]R[\alpha^*] for its monoid algebra, in which each word w∈α*w \in \alpha^* determines a basis monomial [w][w] with coefficient 11. A word-rewriting table T=(rep,zero)T = (\mathrm{rep}, \mathrm{zero}) over α\alpha consists of a binary replacement relation rep\mathrm{rep} on α*\alpha^* and a subset zero⊆α*\mathrm{zero} \subseteq \alpha^* of zero words.✦ When RR is a ring, the defining relations ℛR(T)⊆R[α*]\mathcal{R}_R(T) \subseteq R[\alpha^*] of TT form the set (3): ℛR(T)={[v]−[w]:rep(v,w)}∪{[z]:z∈zero}.\mathcal{R}_R(T) = \{ [v] - [w] : \mathrm{rep}(v, w) \} \cup \{ [z] : z \in \mathrm{zero} \}.(3)✦ Letting IR(T)⊆R[α*]I_R(T) \subseteq R[\alpha^*] be the two-sided ideal generated by ℛR(T)\mathcal{R}_R(T), the table algebra Alg⁡R(T)\operatorname{Alg}_R(T) is the quotient ring R[α*]/IR(T)R[\alpha^*] / I_R(T) (an associative RR-algebra when RR is commutative), with quotient homomorphism qT:R[α*]→Alg⁡R(T)q_T : R[\alpha^*] \to \operatorname{Alg}_R(T) sending each w∈α*w \in \alpha^* to w¯=qT([w])\overline{w} = q_T([w]).

Matrix Letter and Chunk Tests

For a map f:α→Mf : \alpha \to M from an alphabet α\alpha into a monoid (or ring) MM, the word evaluation eval⁡f(w)\operatorname{eval}_f(w) of a finite list w=(a1,…,am)w = (a_1, \dots, a_m) over α\alpha is the product ∏t=1mf(at)\prod_{t=1}^m f(a_t) in MM (equal to 11 when m=0m = 0). When α\alpha is finite and n∈ℕn \in \mathbb{N}, write 𝒲≤n(α)\mathcal{W}_{\le n}(\alpha) for the finite set of candidate words over α\alpha of length at most nn.✦ Over a ring RR, the abstract letter sum of f:α→Rf : \alpha \to R at length nn is the sum in RR of eval⁡f(w)\operatorname{eval}_f(w) over all w∈𝒲≤n(α)w \in \mathcal{W}_{\le n}(\alpha) of length nn; for a finite chunk alphabet Γ\Gamma, a length map ℓ:Γ→ℕ\ell : \Gamma \to \mathbb{N}, a weight map g:Γ→Rg : \Gamma \to R, and m∈ℕm \in \mathbb{N}, the abstract chunk sum is the sum in RR of eval⁡g(s)\operatorname{eval}_g(s) over all lists s=(c1,…,cr)∈𝒲≤m(Γ)s = (c_1, \dots, c_r) \in \mathcal{W}_{\le m}(\Gamma) satisfying ∑j=1rℓ(cj)=m\sum_{j=1}^r \ell(c_j) = m.

Let KK be a ring, AA a KK-algebra, and ι\iota a finite index set, writing Mι(K)M_\iota(K) and Mι(A)M_\iota(A) for the ι×ι\iota \times \iota matrix rings over KK and AA. The tensor product X⊗a∈Mι(A)X \otimes a \in M_\iota(A) of a matrix X∈Mι(K)X \in M_\iota(K) and an element a∈Aa \in A is the matrix with (i,j)(i, j)-entry Xij⋅aX_{ij} \cdot a for all i,j∈ιi, j \in \iota.✦ For a finite alphabet α\alpha, a matrix weight W:α→Mι(K)W : \alpha \to M_\iota(K), a map f:α→Af : \alpha \to A, and n∈ℕn \in \mathbb{N}, the matrix letter sum Lf(W,n)∈Mι(A)L_f(W, n) \in M_\iota(A) is the abstract letter sum of length nn for a↦W(a)⊗f(a)a \mapsto W(a) \otimes f(a), given by (4): Lf(W,n)=∑w∈𝒲≤n(α)|w|=neval⁡a↦W(a)⊗f(a)(w).L_f(W, n) = \sum_{\substack{w \in \mathcal{W}_{\le n}(\alpha) \\ |w| = n}} \operatorname{eval}_{a \mapsto W(a) \otimes f(a)}(w).(4)✦ For a finite chunk alphabet Γ\Gamma, a labeling map ℓ\ell assigning a finite list ℓ(c)\ell(c) over α\alpha to each c∈Γc \in \Gamma, a matrix weight W:Γ→Mι(K)W : \Gamma \to M_\iota(K), and n∈ℕn \in \mathbb{N}, the matrix chunk sum Cf(ℓ,W,n)∈Mι(A)C_f(\ell, W, n) \in M_\iota(A) is the abstract chunk sum of target length nn for chunk lengths c↦|ℓ(c)|c \mapsto |\ell(c)| and weights c↦W(c)⊗eval⁡f(ℓ(c))c \mapsto W(c) \otimes \operatorname{eval}_f(\ell(c)), given by (5): Cf(ℓ,W,n)=∑s=(c1,…,cr)∈𝒲≤n(Γ)∑j=1r|ℓ(cj)|=neval⁡c↦W(c)⊗eval⁡f(ℓ(c))(s).C_f(\ell, W, n) = \sum_{\substack{s = (c_1, \dots, c_r) \in \mathcal{W}_{\le n}(\Gamma) \\ \sum_{j=1}^r |\ell(c_j)| = n}} \operatorname{eval}_{c \mapsto W(c) \otimes \operatorname{eval}_f(\ell(c))}(s).(5)✦

Finite-table Rewriting and the Machine Hierarchy

For a capacity bound q∈ℕq \in \mathbb{N}, a data bit address is a triple (s,b,p)(s, b, p) consisting of a Boolean side ss, a block index b∈{0,…,9}b \in \{0, \dots, 9\}, and a position p<qp < q; a cell memory address is either a data bit address or a certificate address at a position p<qp < q. A three-bit register state is a map {0,1,2}→𝔽2\{0, 1, 2\} \to \mathbb{F}_2, and a verification task is a pair specifying an arity in {0,…,9}\{0, \dots, 9\} and a Boolean zero-task flag. A verification clause of capacity qq consists of three cell memory addresses together with a Boolean truth function on three-bit register states; a verification clause schedule SS of capacity qq assigns to each verification task a positive clause count at most qq together with a family of verification clauses indexed by task and index below qq.

A finite-table cell of capacity qq 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 1010, zero-task flag, and block index at most the arity), a palette checker state (idle, passed, or a head seeking a color below qq), a pair of 𝔽2\mathbb{F}_2 data bits, an 𝔽2\mathbb{F}_2 certificate bit, and a reading head (side, clause index below qq, one of nine computation phases, and a three-bit register).✦ Given a schedule SS of capacity qq and a data size d∈ℕd \in \mathbb{N}, two cell lists satisfy the cell-list replacement relation when every cell in either list satisfies the cell formatting condition for (S,d)(S, d) 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 (S,d)(S, d) if it fails cell formatting, satisfies a semantic head-failure condition for SS, 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 h∈ℕh \in \mathbb{N}, the space Rawh\mathrm{Raw}_h of raw bitstrings is the set of Boolean vectors of length 10000h10000 h.✦ When h>0h > 0, cell encoding embeds cells of capacity 2h2^h into Rawh\mathrm{Raw}_h, 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 Rawh\mathrm{Raw}_h; 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 SS of capacity 2h2^h and a data size d∈ℕd \in \mathbb{N}, these relations define the algebra table 𝒯h(S,d)\mathcal{T}_h(S, d) over Rawh\mathrm{Raw}_h, together with the Boolean table entry predicate entry⁡h,S,d(z,v,w)\operatorname{entry}_{h, S, d}(z, v, w), which decides whether ww is empty and vv is a zero raw word when zz is true, and whether (v,w)(v, w) satisfies raw word replacement when zz 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 β\beta, and a combinational two-input not-and (NAND) circuit with gg gates realizes its local three-cell transition function. Given two Boolean lists tt and vv, their program specialization spec⁡(t,v)\operatorname{spec}(t, v) is the Boolean list obtained by prepending a true bit to the prefix encoding of |t||t|, tt, the prefix encoding of |v||v|, and vv, where the prefix encoding of m∈ℕm \in \mathbb{N} concatenates ℓbin(m)\ell_{\mathrm{bin}}(m) true bits, a false bit, and the binary digits of mm, with ℓbin(0)=1\ell_{\mathrm{bin}}(0) = 1 and ℓbin(m)\ell_{\mathrm{bin}}(m) equal to the binary bit-length of mm for m>0m > 0.

Given natural numbers q,β′,g′,T,Wq, \beta', g', T, W with β′>0\beta' > 0, T>0T > 0, and W≥3W \ge 3, a tableau layout of capacity qq specifies an origin column below WW such that both the certificate variable count β′WT+g′(W−2)(T−1)\beta' W T + g'(W - 2)(T - 1) and the tableau clause count 2β′W+2β′(T−1)+(3g′+2β′)(W−2)(T−1)+β′2\beta' W + 2\beta'(T - 1) + (3g' + 2\beta')(W - 2)(T - 1) + \beta' are at most qq.✦ For parameters β′,g′,D,h,n∈ℕ\beta', g', D, h, n \in \mathbb{N} with T=2⌊h/5⌋T = 2^{\lfloor h/5 \rfloor} and W=4TW = 4T, the layout parameter bounds Fits⁡(β′,g′,D,h,n)\operatorname{Fits}(\beta', g', D, h, n) require 64h+512≤10000h64h + 512 \le 10000h, 10≤22h10 \le 2^{2h}, 2h≤22h2^h \le 2^{2h}, 10000Dh≤2h10000 D h \le 2^h, certificate and clause counts for (β′,g′,T,W)(\beta', g', T, W) at most 2h2^h, and (6): n+2ℓbin(n)+2ℓbin(Dh)+12+20(10000Dh)<⌊T/4⌋.n + 2\ell_{\mathrm{bin}}(n) + 2\ell_{\mathrm{bin}}(Dh) + 12 + 20(10000 D h) < \lfloor T/4 \rfloor.(6)✦

Given a Boolean code aa and parameters D,h∈ℕD, h \in \mathbb{N} satisfying Fits⁡(β,g,D,h,|a|)\operatorname{Fits}(\beta, g, D, h, |a|) with 10000Dh>010000 D h > 0, the source machine tableau layout has capacity 2h2^h, time T=2⌊h/5⌋T = 2^{\lfloor h/5 \rfloor}, width W=4TW = 4T, and origin column 2T2T.✦ Compiling the three-wire addressable clauses that constrain the initial row (built from aa, DhD h, 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 Ssrc(a,D,h)S_{\mathrm{src}}(a, D, h) of capacity 2h2^h. A data assignment data\mathrm{data} on data bit addresses of capacity 2h2^h and a Boolean certificate vector cert\mathrm{cert} of length 2h2^h assemble into an assignment on cell memory addresses of capacity 2h2^h; meanwhile, whenever H,q,l∈ℕH, q, l \in \mathbb{N} satisfy 0<10000H≤q0 < 10000 H \le q and 0<l≤100 < l \le 10, the candidate word for a data assignment data\mathrm{data} of capacity qq at Boolean side ss and block i<li < l is the raw bitstring in RawH\mathrm{Raw}_H with jj-th entry data(s,i,j)\mathrm{data}(s, i, j) for j<10000Hj < 10000 H.

A self-simulating machine hierarchy AA of dilation factor D≥2D \ge 2 consists of a Boolean program PP and a threshold h0≥4h_0 \ge 4 such that, for a=spec⁡(P,P)a = \operatorname{spec}(P, P), every height h≥h0h \ge h_0 satisfies Fits⁡(β,g,D,h,|a|)\operatorname{Fits}(\beta, g, D, h, |a|) and the self-certification equivalence: for every verification task tt of arity lt<10l_t < 10 and every data assignment data\mathrm{data} of capacity 2h2^h, there exists a Boolean certificate vector cert\mathrm{cert} of length 2h2^h satisfying every clause of Ssrc(a,D,h)S_{\mathrm{src}}(a, D, h) under the assembled assignment if and only if entry⁡Dh,Ssrc(a,D,Dh),10000D2h(zt,v,w)=true\operatorname{entry}_{Dh,\, S_{\mathrm{src}}(a, D, Dh),\, 10000 D^2 h}(z_t, v, w) = \mathrm{true}, where ztz_t is the zero-task flag of tt, vv is the list of the lt+1l_t + 1 false-side candidate words in RawDh\mathrm{Raw}_{Dh}, and ww is the empty list when ztz_t is true and the list of the lt+1l_t + 1 true-side candidate words in RawDh\mathrm{Raw}_{Dh} otherwise.✦ At any height h≥h0h \ge h_0 and for any commutative ring KK, let Sh=Ssrc(a,D,h)S_h = S_{\mathrm{src}}(a, D, h) be the hierarchy clause schedule, let 𝒯h=𝒯h(Sh,10000Dh)\mathcal{T}_h = \mathcal{T}_h(S_h, 10000 D h) be the hierarchy rewriting table, let Ah(K)=Alg⁡K(𝒯h)A_h(K) = \operatorname{Alg}_K(\mathcal{T}_h) be the machine hierarchy algebra, and let λh:Rawh→Ah(K)\lambda_h : \mathrm{Raw}_h \to A_h(K) map each r∈Rawhr \in \mathrm{Raw}_h to the word image (r)¯\overline{(r)}.

With AA, KK, a height h≥h0h \ge h_0, and a dimension bound d∈ℕd \in \mathbb{N} fixed, a letter test at height hh with dimension bound dd is a sequence n↦Lλh(W,n)n \mapsto L_{\lambda_h}(W, n) associated with a finite index set ι\iota satisfying |ι|≤d|\iota| \le d and a matrix weight W:Rawh→Mι(K)W : \mathrm{Raw}_h \to M_\iota(K). For b∈ℕb \in \mathbb{N}, a bb-bounded chunk test at height hh with dimension bound dd is a sequence n↦Cλh(ℓ,W,n)n \mapsto C_{\lambda_h}(\ell, W, n) associated with a finite index set ι\iota satisfying |ι|≤d|\iota| \le d, a finite chunk alphabet Γ\Gamma, a labeling map ℓ\ell sending each c∈Γc \in \Gamma to a nonempty list over Rawh\mathrm{Raw}_h of length at most bb, and a matrix weight W:Γ→Mι(K)W : \Gamma \to M_\iota(K).

The Claim

Theorem 1. Let AA be a self-simulating machine hierarchy with dilation factor D>10(10000+1)(10+1)D > 10(10000 + 1)(10 + 1) and threshold h0h_0, let KK be a commutative ring of characteristic two, and fix a height h≥h0h \ge h_0 and an integer d≥0d \ge 0. For every letter test n↦Lλh(W,n)n \mapsto L_{\lambda_h}(W, n) at height hh with dimension bound dd, there exists an index N∈ℕN \in \mathbb{N} satisfying (7): Lλh(W,n)=0(n≥N).L_{\lambda_h}(W, n) = 0 \qquad (n \ge N).(7)✦

For every integer b>0b > 0 and every bb-bounded chunk test n↦Cλh(ℓ,W,n)n \mapsto C_{\lambda_h}(\ell, W, n) at height hh with dimension bound dd, there exists an index N∈ℕN \in \mathbb{N} satisfying (8): Cλh(ℓ,W,n)=0(n≥N).C_{\lambda_h}(\ell, W, n) = 0 \qquad (n \ge N).(8)✦

For any natural numbers HH, D′D', d′d', kk, and cc and any sequence s:ℕ→ℕs : \mathbb{N} \to \mathbb{N} satisfying H≥1H \ge 1, D′>10(c+1)(k+1)D' > 10(c + 1)(k + 1), and s(n)≤2cHn(H,D′)s(n) \le 2^{c H_n(H, D')} for every n∈ℕn \in \mathbb{N}, there exists an index n∈ℕn \in \mathbb{N} (a stopping index) satisfying (9): 400kdn(d′,k,s)2<2Hn(H,D′).400 k \, d_n(d', k, s)^2 < 2^{H_n(H, D')}.(9)✦

In the paper, the result reads: over every field KK 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 KK of characteristic two, states the vanishing at every height h≥h0h \ge h_0 whenever D>10(10000+1)(10+1)D > 10(10000 + 1)(10 + 1), and adjoins (9).

What Is Checked

Claims (7) and (8) are stated over any commutative ring KK of characteristic two, any self-simulating machine hierarchy AA with dilation factor D>10(10000+1)(10+1)D > 10(10000 + 1)(10 + 1), any height h≥h0h \ge h_0, and any dimension bound d∈ℕd \in \mathbb{N} (together with any bound b>0b > 0 in (8)), using matrix letter and chunk sums over the hierarchy clause schedule ShS_h, rewriting table 𝒯h\mathcal{T}_h, machine hierarchy algebra Ah(K)A_h(K), and letter map λh\lambda_h on Rawh\mathrm{Raw}_h; claim (9) is stated over arbitrary natural numbers HH, D′D', d′d', kk, and cc and sequences s:ℕ→ℕs : \mathbb{N} \to \mathbb{N} satisfying H≥1H \ge 1, D′>10(c+1)(k+1)D' > 10(c + 1)(k + 1), and s(n)≤2cHn(H,D′)s(n) \le 2^{c H_n(H, D')}, in terms of the hierarchy height Hn(H,D′)H_n(H, D') and hierarchy dimension dn(d′,k,s)d_n(d', k, s).

The library proves that every height h≥h0h \ge h_0, the data size 10000Dh10000 D h, the tape-coding bit width β\beta, the tableau clause count of any tableau layout, and the packet bit width of input instruction tokens are all positive.