OctoInformBeta

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

§3 (setting): hierarchy parameters and scalar extension: The rewriting-table algebras Ah(K)A_h(K) over any unital associative ring KK for heights hh above the threshold, with entrywise tensor products X⊗aX \otimes a

Hierarchy algebras above a threshold and matrix tensor maps.

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

Consider a self-simulating computing machine and a unital associative ring of scalars. To each integer height above a threshold, one assigns a rewriting table on finite binary strings and its finitely presented quotient algebra, while pairing a square matrix of scalars with an element acted on by those scalars yields a matrix over the target space.

Rewriting Tables and Algebras

Given an alphabet α\alpha, the free monoid of words α*\alpha^* consists of all finite sequences of letters from α\alpha under concatenation.✦ For a semiring KK, the monoid algebra of words K[α*]K[\alpha^*] is the monoid algebra of α*\alpha^* with coefficients in KK✦, and the basis monomial [w]∈K[α*][w] \in K[\alpha^*] of a word w∈α*w \in \alpha^* is the element with coefficient 11 at ww and 00 elsewhere.✦

A word rewriting table T=(rep,Z)T = (\mathrm{rep}, Z) over α\alpha consists of a binary replacement relation rep\mathrm{rep} on α*\alpha^* and a subset Z⊆α*Z \subseteq \alpha^* of zero words.✦ When KK is a unital associative ring, the set of defining relations RT(K)⊆K[α*]R_T(K) \subseteq K[\alpha^*] of TT in K[α*]K[\alpha^*] is (1): RT(K)={[v]−[w]:v,w∈α*,rep(v,w)}∪{[z]:z∈Z}.R_T(K) = \{ [v] - [w] : v, w \in \alpha^*,\, \mathrm{rep}(v, w) \} \cup \{ [z] : z \in Z \}.(1) The defining two-sided ideal IT(K)⊆K[α*]I_T(K) \subseteq K[\alpha^*] is the two-sided ideal generated by RT(K)R_T(K)✦, and the rewriting-table algebra 𝒜K(T)\mathcal{A}_K(T) of TT over KK is the quotient ring (2): 𝒜K(T)=K[α*]/IT(K).\mathcal{A}_K(T) = K[\alpha^*] / I_T(K).(2)✦

Finite Table Rewriting and Bitstring Encoding

For a nonnegative integer bound qq, a cell memory address is either a data address (s,b,p)(s, b, p) with Boolean side ss, block index b∈{0,…,9}b \in \{0, \dots, 9\}, and integer position pp satisfying 0≤p<q0 \le p < q, or a certificate address pp with 0≤p<q0 \le p < q.✦ A three-bit register state is a tuple in 𝔽23\mathbb{F}_2^3✦, and a verification clause of capacity qq consists of three cell memory addresses indexed by {0,1,2}\{0, 1, 2\} together with a Boolean truth function on 𝔽23\mathbb{F}_2^3.✦ A verification task specification t=(ℓ,z)t = (\ell, z) consists of an arity ℓ∈{0,…,9}\ell \in \{0, \dots, 9\} and a Boolean zero-task flag zz.✦ A verification clause schedule SS of capacity qq assigns to each verification task tt a clause count c(t)c(t) satisfying 1≤c(t)≤q1 \le c(t) \le q together with a family of verification clauses S(t,j)S(t, j) of capacity qq indexed by integers jj with 0≤j<q0 \le j < q.✦

For a bound qq and arity bound kk, a cell syntactic skeleton consists of a block cell position (either a core position core(p)\mathrm{core}(p) with 0≤p<q0 \le p < q, a palette color palette(x)\mathrm{palette}(x) with 0≤x<q0 \le x < q, or stop\mathrm{stop}), a marker among idle\mathrm{idle}, left\mathrm{left}, boundary\mathrm{boundary}, full\mathrm{full}, and right\mathrm{right}, and block metadata specifying an arity ℓ\ell with 0≤ℓ<k0 \le \ell < k, a Boolean zero-task flag zz, and a block index bb with 0≤b≤ℓ0 \le b \le \ell✦; cell arity metadata specializes this to k=10k = 10✦, with task projection mapping (ℓ,z,b)(\ell, z, b) to (ℓ,z)(\ell, z). A palette checker state over a color set CC is idle\mathrm{idle}, passed(x)\mathrm{passed}(x), or head(x)\mathrm{head}(x) for some x∈Cx \in C.✦ A head computation phase is one of the nine stages acquisition\mathrm{acquisition}, read-left\mathrm{read\text{-}left}, read-right\mathrm{read\text{-}right}, before-gate\mathrm{before\text{-}gate}, after-gate\mathrm{after\text{-}gate}, undo-left\mathrm{undo\text{-}left}, undo-right\mathrm{undo\text{-}right}, finish\mathrm{finish}, and success\mathrm{success}✦, and a reading head state of capacity qq records a Boolean side, a clause index jj with 0≤j<q0 \le j < q, a phase, and a three-bit register.✦ A finite-table cell cc of capacity qq consists of a syntactic skeleton of capacity qq and arity bound 1010, a palette checker state over {0,…,q−1}\{0, \dots, q-1\}, a pair of 𝔽2\mathbb{F}_2 data bits indexed by Boolean side, an 𝔽2\mathbb{F}_2 certificate bit, and a reading head state.✦

Cells of capacity qq carry a compatibility relation on adjacent pairs; given also a verification clause schedule SS of capacity qq and a nonnegative integer data size dd, cells carry a formatting condition depending on SS and dd, along with unary and binary transition relations determined by SS. Two cell lists uu and vv satisfy the cell-list replacement relation for SS and dd when every cell in uu and vv is formatted and either u=[a]u = [a] and v=[b]v = [b] are related in either direction by a unary transition, or u=[a,b]u = [a, b] and v=[a′,b′]v = [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\mathrm{full} and either its phase is acquisition\mathrm{acquisition}, finish\mathrm{finish}, or success\mathrm{success} with a nonzero register, its phase is after-gate\mathrm{after\text{-}gate} and the truth function of the scheduled clause for the cell’s projected task and head clause index evaluates to false\mathrm{false} on its head register, or its phase is success\mathrm{success} and its zero-task flag is true\mathrm{true}.✦ A cell cc satisfies the unary zero condition for SS and dd when cc fails cell formatting, satisfies the semantic zero condition, or has position palette(x)\mathrm{palette}(x) with checker state passed(x)\mathrm{passed}(x).✦ An ordered pair (a,b)(a, b) of cells satisfies the binary zero condition when it is not a compatible adjacent pair, when both cells have the same palette color xx, or when aa has position palette(x)\mathrm{palette}(x) with checker state head(y)\mathrm{head}(y) for y≠xy \ne x while bb has position stop\mathrm{stop}.✦

For a nonnegative integer height hh, set qh=2hq_h = 2^h and let Σh={0,1}10000h\Sigma_h = \{0, 1\}^{10000 h} be the alphabet of raw bitstrings of length 10000h10000 h.✦ Cell encoding maps each cell of capacity qhq_h to a raw bitstring in Σh\Sigma_h; for h>0h > 0, cell decoding parses a bitstring w∈Σhw \in \Sigma_h to a candidate cell cc of capacity qhq_h and returns cc if ww equals the encoding of cc and fails otherwise✦, while word decoding maps a word over Σh\Sigma_h to the corresponding cell list when every letter decodes and fails otherwise.✦ Given h>0h > 0, a schedule SS of capacity qhq_h, and a data size dd, two words u,v∈Σh*u, v \in \Sigma_h^* satisfy the raw word replacement relation if both decode to cell lists related by the cell-list replacement relation for SS and dd.✦ A letter a∈Σha \in \Sigma_h satisfies the raw unary zero condition if decoding aa fails or yields a cell satisfying the unary zero condition✦, two letters a,b∈Σha, b \in \Sigma_h satisfy the raw binary zero condition if both decode to cells satisfying the binary zero condition✦, and a word w∈Σh*w \in \Sigma_h^* satisfies the zero raw word predicate if ww has length one with a raw unary zero letter or length two with a raw binary zero pair.✦ For h>0h > 0, SS of capacity qhq_h, and data size dd, the codec algebra table 𝒯(h,S,d)\mathcal{T}(h, S, d) is the word rewriting table over Σh\Sigma_h whose replacement relation is raw word replacement and whose zero set consists of all words satisfying the zero raw word predicate.✦ Given also a Boolean selector zz and words u,v∈Σh*u, v \in \Sigma_h^*, the codec table entry entryh,S,d(z,u,v)\mathrm{entry}_{h, S, d}(z, u, v) evaluates to true\mathrm{true} if z=truez = \mathrm{true} with vv empty and uu a zero raw word, or if z=falsez = \mathrm{false} with (u,v)(u, v) in raw word replacement, and to false\mathrm{false} otherwise.✦

Self-simulating Machine Hierarchies

Fix a self-interpreting one-tape Turing machine with finite tape alphabet and state set, equipped with a one-hot binary tape-label coding of bit width β\beta and a combinational NOT-AND (NAND) circuit realization of its local three-cell transition having gg gates. Under this coding, the blank cell label, initial state label, accepting state label, and Boolean bit labels have fixed β\beta-bit encodings.

Write len⁡2(m)\operatorname{len}_2(m) for the binary length of a nonnegative integer mm, equal to 11 when m=0m = 0 and ⌊log⁡2m⌋+1\lfloor \log_2 m \rfloor + 1 when m>0m > 0.✦ For nonnegative integers β,g\beta, g and integers T≥1T \ge 1, W≥2W \ge 2, the total certificate variable count is Ccert(β,g,T,W)=βWT+g(W−2)(T−1)C_{\mathrm{cert}}(\beta, g, T, W) = \beta W T + g(W - 2)(T - 1)✦ and the total tableau clause count is Ccl(β,g,T,W)=2βW+2β(T−1)+(3g+2β)(W−2)(T−1)+βC_{\mathrm{cl}}(\beta, g, T, W) = 2\beta W + 2\beta(T - 1) + (3g + 2\beta)(W - 2)(T - 1) + \beta.✦ A tableau layout of parameters (q,β,g,T,W)(q, \beta, g, T, W) specifies an origin column oo with 0≤o<W0 \le o < W subject to β>0\beta > 0, T>0T > 0, W≥3W \ge 3, Ccert(β,g,T,W)≤qC_{\mathrm{cert}}(\beta, g, T, W) \le q, and Ccl(β,g,T,W)≤qC_{\mathrm{cl}}(\beta, g, T, W) \le q.✦ For a dilation factor DD, integer height hh, and code length nn, set Th=2⌊h/5⌋T_h = 2^{\lfloor h/5 \rfloor} and Wh=4ThW_h = 4 T_h; the layout parameter bounds predicate holds for (β,g,D,h,n)(\beta, g, D, h, n) when 64h+512≤10000h64h + 512 \le 10000 h, 10≤22h10 \le 2^{2h}, qh≤22hq_h \le 2^{2h}, 10000Dh≤qh10000 D h \le q_h, Ccert(β,g,Th,Wh)≤qhC_{\mathrm{cert}}(\beta, g, T_h, W_h) \le q_h, Ccl(β,g,Th,Wh)≤qhC_{\mathrm{cl}}(\beta, g, T_h, W_h) \le q_h, and (3) holds: n+2len⁡2(n)+2len⁡2(Dh)+12+20(10000Dh)<⌊Th/4⌋.n + 2\operatorname{len}_2(n) + 2\operatorname{len}_2(D h) + 12 + 20(10000 D h) < \lfloor T_h / 4 \rfloor.(3)✦

When the layout parameter bounds hold for (β,g,D,h,|a|)(\beta, g, D, h, |a|) of a finite Boolean sequence aa and 10000Dh>010000 D h > 0, the source machine tableau layout constructs a tableau layout of parameters (qh,β,g,Th,Wh)(q_h, \beta, g, T_h, W_h) with origin column 2Th2 T_h, and compiling the initial, boundary, local NAND circuit transition, and acceptance constraints gives a family of Ccl(β,g,Th,Wh)C_{\mathrm{cl}}(\beta, g, T_h, W_h) three-wire addressable clauses and a verification clause schedule Sched⁡(a,D,h)\operatorname{Sched}(a, D, h) of capacity qhq_h. For each task t=(ℓ,z)t = (\ell, z), the initial row assigns to each tape position and bit index either a fixed Boolean value or a reference to a data address (encoding aa, DhD h, the augmented arity ℓ+1\ell + 1, the zero-task flag zz, and the input data blocks). Given a Boolean data assignment 𝑑𝑎𝑡𝑎\mathit{data} on data addresses of capacity qhq_h and a Boolean certificate vector 𝑐𝑒𝑟𝑡:{0,…,qh−1}→{false,true}\mathit{cert} : \{0, \dots, q_h - 1\} \to \{\mathrm{false}, \mathrm{true}\}, the assembled assignment combines 𝑑𝑎𝑡𝑎\mathit{data} and 𝑐𝑒𝑟𝑡\mathit{cert} on all cell memory addresses of capacity qhq_h to test satisfaction of every indexed tableau clause. For a Boolean data assignment 𝑑𝑎𝑡𝑎\mathit{data} on data addresses of capacity qq, nonnegative integers H,qH, q with 10000H≤q10000 H \le q, arity ℓ≤10\ell \le 10, Boolean side ss, and block index ii with 0≤i<ℓ0 \le i < \ell, the candidate word ws,i(H)(𝑑𝑎𝑡𝑎)∈ΣHw^{(H)}_{s, i}(\mathit{data}) \in \Sigma_H of 𝑑𝑎𝑡𝑎\mathit{data} has jj-th entry 𝑑𝑎𝑡𝑎(s,i,j)\mathit{data}(s, i, j) for 0≤j<10000H0 \le j < 10000 H.✦

Fix a dilation factor D≥2D \ge 2. A self-simulating machine hierarchy AA with dilation DD consists of a finite Boolean sequence PP (its program) and an integer threshold h0≥4h_0 \ge 4 satisfying two conditions for the self-specialized code aAa_A obtained from PP by prefix-encoded specialization of PP to itself. First, for every integer h≥h0h \ge h_0, the tuple (β,g,D,h,|aA|)(\beta, g, D, h, |a_A|) satisfies the layout parameter bounds, yielding the hierarchy clause schedule Sh(A)=Sched⁡(aA,D,h)S_h(A) = \operatorname{Sched}(a_A, D, h) of capacity qhq_h. Second, for every integer h≥h0h \ge h_0, every task t=(ℓ,z)t = (\ell, z), and every Boolean data assignment 𝑑𝑎𝑡𝑎\mathit{data} on data addresses of capacity qhq_h, let ufalse∈ΣDh*u_{\mathrm{false}} \in \Sigma_{D h}^* be the (ℓ+1)(\ell + 1)-letter word of candidate words wfalse,i(Dh)(𝑑𝑎𝑡𝑎)w^{(D h)}_{\mathrm{false}, i}(\mathit{data}) (0≤i≤ℓ0 \le i \le \ell), and let utrue(z)∈ΣDh*u_{\mathrm{true}}(z) \in \Sigma_{D h}^* be empty when z=truez = \mathrm{true} and the (ℓ+1)(\ell + 1)-letter word of candidate words wtrue,i(Dh)(𝑑𝑎𝑡𝑎)w^{(D h)}_{\mathrm{true}, i}(\mathit{data}) when z=falsez = \mathrm{false}; then there exists a Boolean certificate vector 𝑐𝑒𝑟𝑡\mathit{cert} on {0,…,qh−1}\{0, \dots, q_h - 1\} satisfying every height-hh tableau clause under the assembled assignment if and only if the self-certification condition (4) holds: entryDh,Sched⁡(aA,D,Dh),10000D2h(z,ufalse,utrue(z))=true.\mathrm{entry}_{D h,\, \operatorname{Sched}(a_A, D, D h),\, 10000 D^2 h} \bigl(z,\, u_{\mathrm{false}},\, u_{\mathrm{true}}(z)\bigr) = \mathrm{true}.(4)

The Definition

Definition 1. Let AA be a self-simulating machine hierarchy with dilation factor D≥2D \ge 2 and threshold h0≥4h_0 \ge 4. For every integer h≥h0h \ge h_0, the hierarchy rewriting table Th(A)T_h(A) over the raw bitstring alphabet Σh\Sigma_h is the codec algebra table (5): Th(A)=𝒯(h,Sh(A),10000Dh).T_h(A) = \mathcal{T}\bigl(h,\, S_h(A),\, 10000 D h\bigr).(5)✦ For any unital associative ring KK and any integer h≥h0h \ge h_0, the machine hierarchy algebra Ah(K)A_h(K) of AA is the rewriting-table algebra (6): Ah(K)=𝒜K(Th(A)).A_h(K) = \mathcal{A}_K\bigl(T_h(A)\bigr).(6)✦ For any index set ι\iota, any scalars KK acting on a set BB via (c,b)↦c⋅b(c, b) \mapsto c \cdot b, any ι×ι\iota \times \iota matrix XX with entries in KK, and any element a∈Ba \in B, the tensor product X⊗aX \otimes a is the ι×ι\iota \times \iota matrix over BB defined entrywise by (7): (X⊗a)ij=Xij⋅a(i,j∈ι).(X \otimes a)_{ij} = X_{ij} \cdot a \qquad (i, j \in \iota).(7)✦

In the paper, the result reads: fix D>10(c+1)(k+1)D > 10(c+1)(k+1) and put hj=h0Djh_j = h_0 D^j, qj=2hjq_j = 2^{h_j}, Lj=2qj+1L_j = 2q_j + 1, Σj=Σhj\Sigma_j = \Sigma_{h_j}, and Aj(K)=Ahj(K)A_j(K) = A_{h_j}(K) over a field KK of characteristic two, with Ej:Aj+1(K)→Aj(K)E_j : A_{j+1}(K) \to A_j(K) and Md(K)⊗KAj(K)=Md(Aj(K))M_d(K) \otimes_K A_j(K) = M_d(A_j(K)). Unlike the paper’s subsequence hj=h0Djh_j = h_0 D^j and characteristic-two field, (5) and (6) apply at every integer h≥h0h \ge h_0 and over any unital associative ring KK, while (7) defines the matrix tensor map (X,a)↦X⊗a(X, a) \mapsto X \otimes a entrywise.

What Is Checked

The definitions (5) and (6) are stated over a self-simulating machine hierarchy AA with dilation factor D≥2D \ge 2 and threshold h0≥4h_0 \ge 4, an integer height h≥h0h \ge h_0, and an arbitrary unital associative ring KK, while (7) is stated over an arbitrary index set ι\iota and any scalar action of a set KK on a set BB. For these constructions, the library also proves that the coding bit width β\beta and the total clause count of any tableau layout are positive, and that for every h≥h0h \ge h_0 both hh and the data block size 10000Dh10000 D h are positive.