OctoInformBeta

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

§2 (setting): word-relation algebra presentations, encoded blocks, and cuts: Quotient presentations over a ring KK and 10000h10000h-bit local cell tables with cuts and hierarchy embeddings

Word-relation algebra presentations and fixed-width encoded cells.

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

Take an associative algebra over a ring KK presented by replacement rules between words and zero declarations on words over a finite alphabet. To simulate local verification machines inside such an algebra, letters must represent cells arranged into blocks, while each cell packs into a bit vector of length 10000h10000h at scale hh so that malformed bit patterns vanish and block words lift across scales.

Words and Monoid Algebras

For an alphabet Σ\Sigma, the free monoid Σ*\Sigma^* consists of all finite words over Σ\Sigma under concatenation.✦ Given a semiring KK, the monoid algebra K[Σ*]K[\Sigma^*] is the free KK-module on Σ*\Sigma^* with multiplication extending word concatenation✦, and the basis monomial [w]∈K[Σ*][w] \in K[\Sigma^*] of a word w∈Σ*w \in \Sigma^* is the element with coefficient 11 at ww and 00 elsewhere.✦

For a ring KK, a binary relation RR on Σ*\Sigma^*, and a subset Z⊆Σ*Z \subseteq \Sigma^*, the defining relation set ℛK(R,Z)\mathcal{R}_K(R, Z) is the subset of K[Σ*]K[\Sigma^*] given by (1), ℛK(R,Z)={[v]−[w]∣(v,w)∈R}∪{[z]∣z∈Z}⊆K[Σ*],\mathcal{R}_K(R, Z) = \{ [v] - [w] \mid (v, w) \in R \} \cup \{ [z] \mid z \in Z \} \subseteq K[\Sigma^*],(1) and the defining ideal IK(R,Z)I_K(R, Z) is the two-sided ideal of K[Σ*]K[\Sigma^*] generated by ℛK(R,Z)\mathcal{R}_K(R, Z).

Skeletons, Checkers, and Schedules

For n∈ℕn \in \mathbb{N}, write [0,n)={i∈ℕ∣i<n}[0, n) = \{i \in \mathbb{N} \mid i < n\}, and set 𝔹={false,true}\mathbb{B} = \{\mathrm{false}, \mathrm{true}\}. Given q∈ℕq \in \mathbb{N}, the set Posq\mathrm{Pos}_q of cell positions consists of core positions C(p)C(p) with p∈[0,q)p \in [0, q), palette positions P(a)P(a) with color a∈[0,q)a \in [0, q), and the stop position SS.✦ The set Mark\mathrm{Mark} of transaction markers consists of the five symbols idle\mathrm{idle}, left\mathrm{left}, boundary\mathrm{boundary}, full\mathrm{full}, and right\mathrm{right}.✦ For k∈ℕk \in \mathbb{N}, a metadata record m∈Metadatakm \in \mathrm{Metadata}_k is a triple (ar(m),ζ(m),blk(m))(\mathrm{ar}(m), \zeta(m), \mathrm{blk}(m)) consisting of an arity ar(m)∈[0,k)\mathrm{ar}(m) \in [0, k), a zero-task flag ζ(m)∈𝔹\zeta(m) \in \mathbb{B}, and a block index blk(m)∈[0,ar(m)+1)\mathrm{blk}(m) \in [0, \mathrm{ar}(m) + 1). A syntactic skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} is a triple (pos(s),mark(s),meta(s))∈Posq×Mark×Metadatak(\mathrm{pos}(s), \mathrm{mark}(s), \mathrm{meta}(s)) \in \mathrm{Pos}_q \times \mathrm{Mark} \times \mathrm{Metadata}_k, with ar(s)\mathrm{ar}(s), ζ(s)\zeta(s), and blk(s)\mathrm{blk}(s) denoting those of meta(s)\mathrm{meta}(s), and with s[μ]s[\mu] denoting ss with marker replaced by μ∈Mark\mu \in \mathrm{Mark}.✦

A skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} is initial when blk(s)=0\mathrm{blk}(s) = 0 and pos(s)=C(p)\mathrm{pos}(s) = C(p) with p=0p = 0✦, terminal when blk(s)=ar(s)\mathrm{blk}(s) = \mathrm{ar}(s) and pos(s)=S\mathrm{pos}(s) = S✦, active-headed when mark(s)∈{boundary,full}\mathrm{mark}(s) \in \{\mathrm{boundary}, \mathrm{full}\}, and admissible when mark(s)=right\mathrm{mark}(s) = \mathrm{right} implies ss is not initial and mark(s)=left\mathrm{mark}(s) = \mathrm{left} implies ss is not terminal.✦ A skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} is left-external if mark(s)=idle\mathrm{mark}(s) = \mathrm{idle} or both mark(s)≠right\mathrm{mark}(s) \neq \mathrm{right} and ss is initial, and right-external if mark(s)∈{idle,boundary}\mathrm{mark}(s) \in \{\mathrm{idle}, \mathrm{boundary}\} or both mark(s)≠left\mathrm{mark}(s) \neq \mathrm{left} and ss is terminal. A skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} accepts a left marker μ∈Mark\mu \in \mathrm{Mark} when μ∈{full,right}\mu \in \{\mathrm{full}, \mathrm{right}\} if mark(s)=right\mathrm{mark}(s) = \mathrm{right} and μ=left\mu = \mathrm{left} otherwise, and accepts a right marker μ∈Mark\mu \in \mathrm{Mark} when μ∈{left,boundary,full}\mu \in \{\mathrm{left}, \mathrm{boundary}, \mathrm{full}\} if mark(s)=left\mathrm{mark}(s) = \mathrm{left} and μ=right\mu = \mathrm{right} otherwise. Two skeletons (s,s′)∈Skelq,k2(s, s') \in \mathrm{Skel}_{q, k}^2 are structurally adjacent when (pos(s),pos(s′))(\mathrm{pos}(s), \mathrm{pos}(s')) is (C(p),C(p+1))(C(p), C(p+1)) with p+1<qp+1 < q, (C(p),P(x))(C(p), P(x)) with p+1=qp+1 = q, (P(x),P(y))(P(x), P(y)), (P(x),S)(P(x), S), or (S,C(0))(S, C(0)) with 0<q0 < q, and are internally consistent when ar(s)=ar(s′)\mathrm{ar}(s) = \mathrm{ar}(s'), ζ(s)=ζ(s′)\zeta(s) = \zeta(s'), blk(s′)=blk(s)+1\mathrm{blk}(s') = \mathrm{blk}(s) + 1 if pos(s)=S\mathrm{pos}(s) = S and blk(s′)=blk(s)\mathrm{blk}(s') = \mathrm{blk}(s) otherwise, s′s' is not initial, and ss is not terminal. A pair of skeletons (s,s′)∈Skelq,k2(s, s') \in \mathrm{Skel}_{q, k}^2 forms a compatible skeleton pair when ss and s′s' are structurally adjacent and either both ss is right-external and s′s' is left-external, or neither holds, ss accepts mark(s′)\mathrm{mark}(s') on the right, s′s' accepts mark(s)\mathrm{mark}(s) on the left, and (s,s′)(s, s') is internally consistent.

Over a color set CC, a palette-checker state χ∈Check(C)\chi \in \mathrm{Check}(C) is idle\mathrm{idle}, pass(x)\mathrm{pass}(x) for x∈Cx \in C, or head(x)\mathrm{head}(x) for x∈Cx \in C; write Checkq=Check([0,q))\mathrm{Check}_q = \mathrm{Check}([0, q)).✦ A pair (χ,χ′)∈Check(C)2(\chi, \chi') \in \mathrm{Check}(C)^2 is palette-compatible when it equals (idle,idle)(\mathrm{idle}, \mathrm{idle}), (pass(x),pass(x))(\mathrm{pass}(x), \mathrm{pass}(x)), (pass(x),head(x))(\mathrm{pass}(x), \mathrm{head}(x)), or (head(x),idle)(\mathrm{head}(x), \mathrm{idle}) for some x∈Cx \in C. A state χ∈Check(C)\chi \in \mathrm{Check}(C) satisfies the terminal checker condition when χ=idle\chi = \mathrm{idle} or χ=head(x)\chi = \mathrm{head}(x) for some x∈Cx \in C.

The scalar conversion map β:𝔹→𝔽2\beta : \mathbb{B} \to \mathbb{F}_2 sends false↦0\mathrm{false} \mapsto 0 and true↦1\mathrm{true} \mapsto 1, with inverse β−1:𝔽2→𝔹\beta^{-1} : \mathbb{F}_2 \to \mathbb{B} sending 1↦true1 \mapsto \mathrm{true} and 0↦false0 \mapsto \mathrm{false}, and componentwise lift scalarsn:𝔹[0,n)→𝔽2[0,n)\mathrm{scalars}_n : \mathbb{B}^{[0, n)} \to \mathbb{F}_2^{[0, n)}. A register state r∈Regr \in \mathrm{Reg} is a vector in 𝔽2[0,3)\mathbb{F}_2^{[0, 3)}. The set Phase\mathrm{Phase} of head phases consists of nine symbols acq\mathrm{acq} (acquisition), rL\mathrm{rL} (read-left), rR\mathrm{rR} (read-right), bG\mathrm{bG} (before-gate), aG\mathrm{aG} (after-gate), uL\mathrm{uL} (undo-left), uR\mathrm{uR} (undo-right), fin\mathrm{fin} (finish), and suc\mathrm{suc} (success), among which the endpoint phases are {acq,bG,aG,fin,suc}\{\mathrm{acq}, \mathrm{bG}, \mathrm{aG}, \mathrm{fin}, \mathrm{suc}\}. A reading-head state H∈HeadqH \in \mathrm{Head}_q is a tuple (side(H),cl(H),ph(H),reg(H))∈𝔹×[0,q)×Phase×Reg(\mathrm{side}(H), \mathrm{cl}(H), \mathrm{ph}(H), \mathrm{reg}(H)) \in \mathbb{B} \times [0, q) \times \mathrm{Phase} \times \mathrm{Reg}, with default head head0=(false,0,acq,0)\mathrm{head}_0 = (\mathrm{false}, 0, \mathrm{acq}, 0) when q>0q > 0.✦ An address α∈Addrq\alpha \in \mathrm{Addr}_q is either a data address data(σ,b,p)\mathrm{data}(\sigma, b, p) with σ∈𝔹\sigma \in \mathbb{B}, b∈[0,10)b \in [0, 10), and p∈[0,q)p \in [0, q), or a certificate address cert(p)\mathrm{cert}(p) with p∈[0,q)p \in [0, q). A task t∈Taskt \in \mathrm{Task} is a pair (a,ζ)∈[0,10)×𝔹(a, \zeta) \in [0, 10) \times \mathbb{B}. A verification clause γ∈Clauseq\gamma \in \mathrm{Clause}_q consists of an address triple addrγ:[0,3)→Addrq\mathrm{addr}_\gamma : [0, 3) \to \mathrm{Addr}_q and a truth function τγ:𝔽2[0,3)→𝔹\tau_\gamma : \mathbb{F}_2^{[0, 3)} \to \mathbb{B}✦, and a schedule 𝒮\mathcal{S} on qq consists of a positive clause count cnt𝒮:Task→{1,…,q}\mathrm{cnt}_{\mathcal{S}} : \mathrm{Task} \to \{1, \dots, q\} together with an assignment 𝒮:Task×[0,q)→Clauseq\mathcal{S} : \mathrm{Task} \times [0, q) \to \mathrm{Clause}_q.

The Definition

Definition 1. A word-relation presentation TT over an alphabet Σ\Sigma is a pair T=(→T,ZT)T = (\to_T, Z_T) of a replacement relation →T⊆Σ*×Σ*\to_T \subseteq \Sigma^* \times \Sigma^* and a zero set ZT⊆Σ*Z_T \subseteq \Sigma^* given by (2): T=(→T,ZT),→T⊆Σ*×Σ*,ZT⊆Σ*.T = (\to_T,\, Z_T), \qquad {\to_T} \subseteq \Sigma^* \times \Sigma^*, \quad Z_T \subseteq \Sigma^*.(2)✦ The replacement reachability relation ≡T\equiv_T on Σ*\Sigma^* associated with TT is the monoid congruence closure defined by (3): ≡T=⋂{∼⊆Σ*×Σ*|∼ is a monoid congruence on Σ* and →T⊆∼}.{\equiv_T} = \bigcap \bigl\{\, {\sim} \subseteq \Sigma^* \times \Sigma^* \;\mathrel{\big|}\; {\sim} \text{ is a monoid congruence on } \Sigma^* \text{ and } {\to_T} \subseteq {\sim} \,\bigr\}.(3)✦ A word w∈Σ*w \in \Sigma^* vanishes in TT, written VanT(w)\mathrm{Van}_T(w), under the condition (4): VanT(w)⇔∃p,z,s∈Σ*,z∈ZT and w≡Tpzs.\mathrm{Van}_T(w) \iff \exists\, p, z, s \in \Sigma^*,\quad z \in Z_T \text{ and } w \equiv_T p z s.(4)✦ For a ring KK, let ℛK(T)=ℛK(→T,ZT)\mathcal{R}_K(T) = \mathcal{R}_K(\to_T, Z_T) and IK(T)=IK(→T,ZT)I_K(T) = I_K(\to_T, Z_T) from (1); the presented KK-algebra 𝒜K(T)\mathcal{A}_K(T) of TT is the quotient ring given by (5): 𝒜K(T)=K[Σ*]/IK(T).\mathcal{A}_K(T) = K[\Sigma^*] / I_K(T).(5)✦

The space Meta\mathrm{Meta} of cell metadata of bound ten is given by (6): Meta=Metadata10,\mathrm{Meta} = \mathrm{Metadata}_{10},(6)✦ with default metadata meta0=(0,false,0)∈Meta\mathrm{meta}_0 = (0, \mathrm{false}, 0) \in \mathrm{Meta}✦ and task projection task(m)=(ar(m),ζ(m))∈Task\mathrm{task}(m) = (\mathrm{ar}(m), \zeta(m)) \in \mathrm{Task}.✦ Using Meta\mathrm{Meta} from (6), for q∈ℕq \in \mathbb{N} the alphabet 𝒞q\mathcal{C}_q of finite-table cells consists of quintuples described by (7): c=(skel(c),chk(c),datac,cert(c),head(c))∈Skelq,10×Checkq×𝔽2𝔹×𝔽2×Headq.c = (\mathrm{skel}(c),\, \mathrm{chk}(c),\, \mathrm{data}_c,\, \mathrm{cert}(c),\, \mathrm{head}(c)) \in \mathrm{Skel}_{q,10} \times \mathrm{Check}_q \times \mathbb{F}_2^{\mathbb{B}} \times \mathbb{F}_2 \times \mathrm{Head}_q.(7)✦ For c∈𝒞qc \in \mathcal{C}_q, write pos(c)\mathrm{pos}(c), mark(c)\mathrm{mark}(c), meta(c)\mathrm{meta}(c), ar(c)\mathrm{ar}(c), ζ(c)\zeta(c), and blk(c)\mathrm{blk}(c) for the components of skel(c)\mathrm{skel}(c), and task(c)=task(meta(c))\mathrm{task}(c) = \mathrm{task}(\mathrm{meta}(c)); call cc a core cell when pos(c)=C(p)\mathrm{pos}(c) = C(p) for some pp✦, a palette cell when pos(c)=P(a)\mathrm{pos}(c) = P(a) for some aa✦, and head-free when skel(c)\mathrm{skel}(c) is not active-headed and chk(c)≠head(x)\mathrm{chk}(c) \neq \mathrm{head}(x) for all x∈[0,q)x \in [0, q).✦ Reading an address α∈Addrq\alpha \in \mathrm{Addr}_q from a cell c∈𝒞qc \in \mathcal{C}_q gives read(α,c)∈𝔽2\mathrm{read}(\alpha, c) \in \mathbb{F}_2, equal to datac(σ)\mathrm{data}_c(\sigma) when α=data(σ,b,p)\alpha = \mathrm{data}(\sigma, b, p), pos(c)=C(r)\mathrm{pos}(c) = C(r), blk(c)=b\mathrm{blk}(c) = b, and r=pr = p, equal to cert(c)\mathrm{cert}(c) when α=cert(p)\alpha = \mathrm{cert}(p), pos(c)=C(r)\mathrm{pos}(c) = C(r), blk(c)=0\mathrm{blk}(c) = 0, and r=pr = p, and 00 otherwise; for a clause γ∈Clauseq\gamma \in \mathrm{Clause}_q, the register delta δ(γ,c)∈Reg\delta(\gamma, c) \in \mathrm{Reg} has ii-th entry read(addrγ(i),c)\mathrm{read}(\mathrm{addr}_\gamma(i), c).

For c∈𝒞qc \in \mathcal{C}_q, χ′∈Checkq\chi' \in \mathrm{Check}_q, x,j∈[0,q)x, j \in [0, q), σ∈𝔹\sigma \in \mathbb{B}, ϕ∈Phase\phi \in \mathrm{Phase}, r∈Regr \in \mathrm{Reg}, and μ∈Mark\mu \in \mathrm{Mark}, update operations define cells in 𝒞q\mathcal{C}_q as follows: setChk(c,χ′)\mathrm{setChk}(c, \chi') sets checker state to χ′\chi'✦; setCol(c,x)\mathrm{setCol}(c, x) sets position to P(x)P(x)✦; full(c,σ,j,ϕ,r)\mathrm{full}(c, \sigma, j, \phi, r) sets skeleton marker to full\mathrm{full} and head to (σ,j,ϕ,r)(\sigma, j, \phi, r)✦; and for q>0q > 0, wing(c,μ)\mathrm{wing}(c, \mu) sets skeleton marker to μ\mu and head to head0\mathrm{head}_0, bdry(c,σ)\mathrm{bdry}(c, \sigma) sets skeleton marker to boundary\mathrm{boundary} and head to (σ,0,acq,0)(\sigma, 0, \mathrm{acq}, 0), and idle(c,σ)\mathrm{idle}(c, \sigma) keeps pos(c)\mathrm{pos}(c) and chk(c)\mathrm{chk}(c) while setting skeleton marker to idle\mathrm{idle}, metadata to meta0\mathrm{meta}_0, data to (false↦datac(σ),true↦0)(\mathrm{false} \mapsto \mathrm{data}_c(\sigma), \mathrm{true} \mapsto 0), certificate to 00, and head to head0\mathrm{head}_0.

Relative to a schedule 𝒮\mathcal{S} on q>0q > 0 and a bound d∈ℕd \in \mathbb{N}, a cell c∈𝒞qc \in \mathcal{C}_q is formatted when: skel(c)\mathrm{skel}(c) is admissible; chk(c)=idle\mathrm{chk}(c) = \mathrm{idle} whenever cc is not a palette cell; datac=0\mathrm{data}_c = 0 identically whenever pos(c)=C(p)\mathrm{pos}(c) = C(p) with p≥dp \ge d; datac=0\mathrm{data}_c = 0 and cert(c)=0\mathrm{cert}(c) = 0 whenever cc is not a core cell; meta(c)=meta0\mathrm{meta}(c) = \mathrm{meta}_0, head(c)=head0\mathrm{head}(c) = \mathrm{head}_0, datac(true)=0\mathrm{data}_c(\mathrm{true}) = 0, and cert(c)=0\mathrm{cert}(c) = 0 whenever mark(c)=idle\mathrm{mark}(c) = \mathrm{idle}; head(c)=head0\mathrm{head}(c) = \mathrm{head}_0 whenever mark(c)∈{left,right}\mathrm{mark}(c) \in \{\mathrm{left}, \mathrm{right}\}; cl(head(c))=0\mathrm{cl}(\mathrm{head}(c)) = 0, ph(head(c))=acq\mathrm{ph}(\mathrm{head}(c)) = \mathrm{acq}, and reg(head(c))=0\mathrm{reg}(\mathrm{head}(c)) = 0 whenever mark(c)=boundary\mathrm{mark}(c) = \mathrm{boundary}; side(head(c))=false\mathrm{side}(\mathrm{head}(c)) = \mathrm{false} whenever skel(c)\mathrm{skel}(c) is active-headed and ζ(c)=true\zeta(c) = \mathrm{true}; and whenever mark(c)=full\mathrm{mark}(c) = \mathrm{full}, one has cl(head(c))=0\mathrm{cl}(\mathrm{head}(c)) = 0 if ph(head(c))=suc\mathrm{ph}(\mathrm{head}(c)) = \mathrm{suc}, cl(head(c))<cnt𝒮(task(c))\mathrm{cl}(\mathrm{head}(c)) < \mathrm{cnt}_{\mathcal{S}}(\mathrm{task}(c)) if ph(head(c))≠suc\mathrm{ph}(\mathrm{head}(c)) \neq \mathrm{suc}, and skel(c)\mathrm{skel}(c) terminal if ph(head(c))\mathrm{ph}(\mathrm{head}(c)) is an endpoint phase. Two cells (u,v)∈𝒞q2(u, v) \in \mathcal{C}_q^2 satisfy checker compatibility when (chk(u),chk(v))(\mathrm{chk}(u), \mathrm{chk}(v)) is palette-compatible whenever both are palette cells and chk(u)\mathrm{chk}(u) satisfies the terminal checker condition whenever uu is a palette cell and pos(v)=S\mathrm{pos}(v) = S✦; a pair of cells (u,v)∈𝒞q2(u, v) \in \mathcal{C}_q^2 forms a compatible cell pair when (skel(u),skel(v))(\mathrm{skel}(u), \mathrm{skel}(v)) is a compatible skeleton pair and (u,v)(u, v) is checker-compatible.

Given a schedule 𝒮\mathcal{S} on q>0q > 0, the directed single-cell transition relation →1\to_1 on 𝒞q\mathcal{C}_q is the binary relation generated for c∈𝒞qc \in \mathcal{C}_q, σ∈𝔹\sigma \in \mathbb{B}, j,j′∈[0,q)j, j' \in [0, q), and r∈Regr \in \mathrm{Reg} by: when skel(c)\mathrm{skel}(c) is initial, idle(c,σ)→1bdry(c,σ)\mathrm{idle}(c, \sigma) \to_1 \mathrm{bdry}(c, \sigma), full(c,σ,j,rL,r)→1full(c,σ,j,rR,r)\mathrm{full}(c, \sigma, j, \mathrm{rL}, r) \to_1 \mathrm{full}(c, \sigma, j, \mathrm{rR}, r), and full(c,σ,j,uL,r)→1full(c,σ,j,uR,r)\mathrm{full}(c, \sigma, j, \mathrm{uL}, r) \to_1 \mathrm{full}(c, \sigma, j, \mathrm{uR}, r); and when skel(c)\mathrm{skel}(c) is terminal, bdry(c,σ)→1full(c,σ,0,acq,0)\mathrm{bdry}(c, \sigma) \to_1 \mathrm{full}(c, \sigma, 0, \mathrm{acq}, 0), full(c,σ,j,acq,r)→1full(c,σ,j,rL,r)\mathrm{full}(c, \sigma, j, \mathrm{acq}, r) \to_1 \mathrm{full}(c, \sigma, j, \mathrm{rL}, r), full(c,σ,j,rR,r)→1full(c,σ,j,bG,r)\mathrm{full}(c, \sigma, j, \mathrm{rR}, r) \to_1 \mathrm{full}(c, \sigma, j, \mathrm{bG}, r), full(c,σ,j,aG,r)→1full(c,σ,j,uL,r)\mathrm{full}(c, \sigma, j, \mathrm{aG}, r) \to_1 \mathrm{full}(c, \sigma, j, \mathrm{uL}, r), full(c,σ,j,uR,r)→1full(c,σ,j,fin,r)\mathrm{full}(c, \sigma, j, \mathrm{uR}, r) \to_1 \mathrm{full}(c, \sigma, j, \mathrm{fin}, r), full(c,σ,j,bG,r)→1full(c,σ,j,aG,r)\mathrm{full}(c, \sigma, j, \mathrm{bG}, r) \to_1 \mathrm{full}(c, \sigma, j, \mathrm{aG}, r) when τ𝒮(task(c),j)(r)=true\tau_{\mathcal{S}(\mathrm{task}(c), j)}(r) = \mathrm{true}, full(c,σ,j,fin,0)→1full(c,σ,j′,acq,0)\mathrm{full}(c, \sigma, j, \mathrm{fin}, 0) \to_1 \mathrm{full}(c, \sigma, j', \mathrm{acq}, 0) when j+1=j′j + 1 = j', full(c,σ,j,fin,0)→1full(c,σ,0,suc,0)\mathrm{full}(c, \sigma, j, \mathrm{fin}, 0) \to_1 \mathrm{full}(c, \sigma, 0, \mathrm{suc}, 0) when j+1=cnt𝒮(task(c))j + 1 = \mathrm{cnt}_{\mathcal{S}}(\mathrm{task}(c)), and full(c,σ,0,suc,0)→1full(c,¬σ,0,suc,0)\mathrm{full}(c, \sigma, 0, \mathrm{suc}, 0) \to_1 \mathrm{full}(c, \neg \sigma, 0, \mathrm{suc}, 0) when ζ(c)=false\zeta(c) = \mathrm{false}.

Directed two-cell transitions →2\to_2 on 𝒞q2\mathcal{C}_q^2 are generated for u,v∈𝒞qu, v \in \mathcal{C}_q, σ∈𝔹\sigma \in \mathbb{B}, j∈[0,q)j \in [0, q), and r∈Regr \in \mathrm{Reg} by: (bdry(u,σ),idle(v,σ))→2(wing(u,left),bdry(v,σ))(\mathrm{bdry}(u, \sigma), \mathrm{idle}(v, \sigma)) \to_2 (\mathrm{wing}(u, \mathrm{left}), \mathrm{bdry}(v, \sigma)) when (skel(u)[left],skel(v)[boundary])(\mathrm{skel}(u)[\mathrm{left}], \mathrm{skel}(v)[\mathrm{boundary}]) is a compatible skeleton pair; writing Δ=δ(𝒮(task(u),j),u)\Delta = \delta(\mathcal{S}(\mathrm{task}(u), j), u), the four moves (wing(u,left),full(v,σ,j,rL,r))→2(full(u,σ,j,rL,r+Δ),wing(v,right))(\mathrm{wing}(u, \mathrm{left}), \mathrm{full}(v, \sigma, j, \mathrm{rL}, r)) \to_2 (\mathrm{full}(u, \sigma, j, \mathrm{rL}, r + \Delta), \mathrm{wing}(v, \mathrm{right})), (full(u,σ,j,rR,r),wing(v,right))→2(wing(u,left),full(v,σ,j,rR,r))(\mathrm{full}(u, \sigma, j, \mathrm{rR}, r), \mathrm{wing}(v, \mathrm{right})) \to_2 (\mathrm{wing}(u, \mathrm{left}), \mathrm{full}(v, \sigma, j, \mathrm{rR}, r)), (wing(u,left),full(v,σ,j,uL,r))→2(full(u,σ,j,uL,r),wing(v,right))(\mathrm{wing}(u, \mathrm{left}), \mathrm{full}(v, \sigma, j, \mathrm{uL}, r)) \to_2 (\mathrm{full}(u, \sigma, j, \mathrm{uL}, r), \mathrm{wing}(v, \mathrm{right})), and (full(u,σ,j,uR,r),wing(v,right))→2(wing(u,left),full(v,σ,j,uR,r+Δ))(\mathrm{full}(u, \sigma, j, \mathrm{uR}, r), \mathrm{wing}(v, \mathrm{right})) \to_2 (\mathrm{wing}(u, \mathrm{left}), \mathrm{full}(v, \sigma, j, \mathrm{uR}, r + \Delta)) when (skel(u)[full],skel(v)[right])(\mathrm{skel}(u)[\mathrm{full}], \mathrm{skel}(v)[\mathrm{right}]) is a compatible skeleton pair; (u,setChk(v,idle))→2(u,setChk(v,head(x)))(u, \mathrm{setChk}(v, \mathrm{idle})) \to_2 (u, \mathrm{setChk}(v, \mathrm{head}(x))) when pos(u)=C(p)\mathrm{pos}(u) = C(p) with p+1=qp + 1 = q, vv is a palette cell, and x∈[0,q)x \in [0, q); (setChk(u,head(x)),setChk(v,idle))→2(setChk(u,pass(x)),setChk(v,head(x)))(\mathrm{setChk}(u, \mathrm{head}(x)), \mathrm{setChk}(v, \mathrm{idle})) \to_2 (\mathrm{setChk}(u, \mathrm{pass}(x)), \mathrm{setChk}(v, \mathrm{head}(x))) when pos(u)=P(y)\mathrm{pos}(u) = P(y), vv is a palette cell, and y≠xy \neq x; and (u,v)→2(v,u)(u, v) \to_2 (v, u) when pos(u)=P(x)\mathrm{pos}(u) = P(x), pos(v)=P(y)\mathrm{pos}(v) = P(y), v=setCol(u,y)v = \mathrm{setCol}(u, y), and both uu and vv are head-free. For a schedule 𝒮\mathcal{S} on q>0q > 0 and a bound d∈ℕd \in \mathbb{N}, the cell replacement relation Rep𝒮,d\mathrm{Rep}_{\mathcal{S}, d} on 𝒞q*\mathcal{C}_q^* is the binary relation holding for cell words v,w∈𝒞q*v, w \in \mathcal{C}_q^* when every cell occurring in vv or ww is formatted for (𝒮,d)(\mathcal{S}, d) and either v=av = a, w=bw = b with a→1ba \to_1 b or b→1ab \to_1 a, or v=a1a2v = a_1 a_2, w=b1b2w = b_1 b_2 with (a1,a2)→2(b1,b2)(a_1, a_2) \to_2 (b_1, b_2) or (b1,b2)→2(a1,a2)(b_1, b_2) \to_2 (a_1, a_2).

A cell c∈𝒞qc \in \mathcal{C}_q is a semantic zero for 𝒮\mathcal{S}, written SZ𝒮(c)\mathrm{SZ}_{\mathcal{S}}(c), when mark(c)=full\mathrm{mark}(c) = \mathrm{full} and either ph(head(c))∈{acq,fin,suc}\mathrm{ph}(\mathrm{head}(c)) \in \{\mathrm{acq}, \mathrm{fin}, \mathrm{suc}\} with reg(head(c))≠0\mathrm{reg}(\mathrm{head}(c)) \neq 0, or ph(head(c))=aG\mathrm{ph}(\mathrm{head}(c)) = \mathrm{aG} with τ𝒮(task(c),cl(head(c)))(reg(head(c)))=false\tau_{\mathcal{S}(\mathrm{task}(c), \mathrm{cl}(\mathrm{head}(c)))} (\mathrm{reg}(\mathrm{head}(c))) = \mathrm{false}, or ph(head(c))=suc\mathrm{ph}(\mathrm{head}(c)) = \mathrm{suc} with ζ(c)=true\zeta(c) = \mathrm{true}. For a schedule 𝒮\mathcal{S} on q>0q > 0 and a bound d∈ℕd \in \mathbb{N}, the unary zero predicate UZ𝒮,d\mathrm{UZ}_{\mathcal{S}, d} on 𝒞q\mathcal{C}_q holds for a cell c∈𝒞qc \in \mathcal{C}_q when cc fails formatting for (𝒮,d)(\mathcal{S}, d), SZ𝒮(c)\mathrm{SZ}_{\mathcal{S}}(c) holds, or pos(c)=P(x)\mathrm{pos}(c) = P(x) and chk(c)=pass(x)\mathrm{chk}(c) = \mathrm{pass}(x) for some x∈[0,q)x \in [0, q). The binary zero relation BZ\mathrm{BZ} on 𝒞q2\mathcal{C}_q^2 holds for a cell pair (u,v)∈𝒞q2(u, v) \in \mathcal{C}_q^2 when (u,v)(u, v) fails to be a compatible cell pair, pos(u)=pos(v)=P(x)\mathrm{pos}(u) = \mathrm{pos}(v) = P(x) for some x∈[0,q)x \in [0, q), or pos(u)=P(x)\mathrm{pos}(u) = P(x), chk(u)=head(y)\mathrm{chk}(u) = \mathrm{head}(y), and pos(v)=S\mathrm{pos}(v) = S for some x≠yx \neq y.

For h∈ℕh \in \mathbb{N}, write qh=2hq_h = 2^h; the alphabet Rawh\mathrm{Raw}_h of raw bit vectors of width 10000h10000h is given by (8): Rawh=𝔹[0,10000h).\mathrm{Raw}_h = \mathbb{B}^{[0, 10000h)}.(8)✦ Assign integer tags to positions via C(⋅)↦0C(\cdot) \mapsto 0, P(⋅)↦1P(\cdot) \mapsto 1, S↦2S \mapsto 2 (with index pp, aa, or 00), to markers idle,left,boundary,full,right\mathrm{idle}, \mathrm{left}, \mathrm{boundary}, \mathrm{full}, \mathrm{right} via 0,1,2,3,40, 1, 2, 3, 4, to checker states idle,pass(x),head(x)\mathrm{idle}, \mathrm{pass}(x), \mathrm{head}(x) via tags 0,1,20, 1, 2 (with index 0,x,x0, x, x), and to the nine phases in order via 0,…,80, \dots, 8. For c∈𝒞qhc \in \mathcal{C}_{q_h}, let ints(c)∈ℕ[0,32)\mathrm{ints}(c) \in \mathbb{N}^{[0, 32)} place position tag, position index, marker tag, ar(c)\mathrm{ar}(c), blk(c)\mathrm{blk}(c), checker tag, checker index, cl(head(c))\mathrm{cl}(\mathrm{head}(c)), and phase tag of ph(head(c))\mathrm{ph}(\mathrm{head}(c)) in entries 00 to 88 and 00 in entries 99 to 3131, and let flags(c)∈𝔹[0,512)\mathrm{flags}(c) \in \mathbb{B}^{[0, 512)} place ζ(c)\zeta(c), side(head(c))\mathrm{side}(\mathrm{head}(c)), β−1(datac(false))\beta^{-1}(\mathrm{data}_c(\mathrm{false})), β−1(datac(true))\beta^{-1}(\mathrm{data}_c(\mathrm{true})), β−1(cert(c))\beta^{-1}(\mathrm{cert}(c)), and β−1(reg(head(c))i)\beta^{-1}(\mathrm{reg}(\mathrm{head}(c))_i) for i∈[0,3)i \in [0, 3) in entries 00 to 77 and false\mathrm{false} in entries 88 to 511511. Given n∈ℕ[0,32)n \in \mathbb{N}^{[0, 32)} and f∈𝔹[0,512)f \in \mathbb{B}^{[0, 512)}, the writer writeh(n,f)∈Rawh\mathrm{write}_h(n, f) \in \mathrm{Raw}_h sets index k∈[0,10000h)k \in [0, 10000h) to the (kmod⁡2h)(k \bmod 2h)-th binary bit (as true\mathrm{true} for 11 and false\mathrm{false} for 00) of n⌊k/2h⌋n_{\lfloor k / 2h \rfloor} for k<64hk < 64h, to fk−64hf_{k - 64h} for 64h≤k<64h+51264h \le k < 64h + 512, and to false\mathrm{false} for k≥64h+512k \ge 64h + 512✦; the cell encoding map ench:𝒞qh→Rawh\mathrm{enc}_h : \mathcal{C}_{q_h} \to \mathrm{Raw}_h is defined by (9): ench(c)=writeh(ints(c),flags(c)).\mathrm{enc}_h(c) = \mathrm{write}_h\bigl(\mathrm{ints}(c),\, \mathrm{flags}(c)\bigr).(9)✦

For h>0h > 0 and w∈Rawhw \in \mathrm{Raw}_h, writing βℕ(false)=0\beta_{\mathbb{N}}(\mathrm{false}) = 0 and βℕ(true)=1\beta_{\mathbb{N}}(\mathrm{true}) = 1, the partial parser parseh(w)\mathrm{parse}_h(w) reads little-endian 2h2h-bit integers ns=∑i=02h−1βℕ(w(s(2h)+i))2in_s = \sum_{i=0}^{2h-1} \beta_{\mathbb{N}}(w(s(2h)+i)) 2^i for s∈[0,32)s \in [0, 32) and flags fj=w(64h+j)f_j = w(64h + j) for j∈[0,512)j \in [0, 512), returning the cell in 𝒞qh\mathcal{C}_{q_h} whose integer and flag entries match n0,…,n8n_0, \dots, n_8 and f0,…,f7f_0, \dots, f_7 (applying β\beta to f2,…,f7f_2, \dots, f_7) whenever n0∈{0,1,2}n_0 \in \{0, 1, 2\} (with n1<qhn_1 < q_h if n0<2n_0 < 2 and n1=0n_1 = 0 if n0=2n_0 = 2), n2<5n_2 < 5, n3<10n_3 < 10, n4<n3+1n_4 < n_3 + 1, n5∈{0,1,2}n_5 \in \{0, 1, 2\} (with n6=0n_6 = 0 if n5=0n_5 = 0 and n6<qhn_6 < q_h otherwise), n7<qhn_7 < q_h, and n8<9n_8 < 9, and undefined otherwise. Using (9), the partial decoding map dech:Rawh⇀𝒞qh\mathrm{dec}_h : \mathrm{Raw}_h \rightharpoonup \mathcal{C}_{q_h} is defined by (10): dech(w)={cif parseh(w)=c and w=ench(c),undefinedotherwise,\mathrm{dec}_h(w) = \begin{cases} c & \text{if } \mathrm{parse}_h(w) = c \text{ and } w = \mathrm{enc}_h(c), \\ \text{undefined} & \text{otherwise,} \end{cases}(10)✦ with letterwise lift dech*:Rawh*⇀𝒞qh*\mathrm{dec}_h^* : \mathrm{Raw}_h^* \rightharpoonup \mathcal{C}_{q_h}^*. For a schedule 𝒮\mathcal{S} on qhq_h and d∈ℕd \in \mathbb{N}, raw replacement reph,𝒮,d\mathrm{rep}_{h, \mathcal{S}, d} is the binary relation on Rawh*\mathrm{Raw}_h^* holding for words v,wv, w when dech*(v)=a\mathrm{dec}_h^*(v) = a and dech*(w)=b\mathrm{dec}_h^*(w) = b are defined and satisfy Rep𝒮,d(a,b)\mathrm{Rep}_{\mathcal{S}, d}(a, b); raw unary zero UZh,𝒮,draw\mathrm{UZ}_{h, \mathcal{S}, d}^{\mathrm{raw}} is the predicate on Rawh\mathrm{Raw}_h holding for aa when dech(a)\mathrm{dec}_h(a) is undefined or dech(a)=c\mathrm{dec}_h(a) = c with UZ𝒮,d(c)\mathrm{UZ}_{\mathcal{S}, d}(c); raw binary zero BZhraw\mathrm{BZ}_h^{\mathrm{raw}} is the relation on Rawh2\mathrm{Raw}_h^2 holding for (a,b)(a, b) when dech(a)=c\mathrm{dec}_h(a) = c and dech(b)=c′\mathrm{dec}_h(b) = c' are defined with BZ(c,c′)\mathrm{BZ}(c, c'); and zeroh,𝒮,d\mathrm{zero}_{h, \mathcal{S}, d} is the subset of Rawh*\mathrm{Raw}_h^* consisting of words v=av = a with UZh,𝒮,draw(a)\mathrm{UZ}_{h, \mathcal{S}, d}^{\mathrm{raw}}(a) and v=abv = ab with BZhraw(a,b)\mathrm{BZ}_h^{\mathrm{raw}}(a, b). Using (2) and (10), for a schedule 𝒮\mathcal{S} on qhq_h and a bound d∈ℕd \in \mathbb{N}, the raw word-algebra presentation Th(𝒮,d)T_h(\mathcal{S}, d) over Rawh\mathrm{Raw}_h is given by (11): Th(𝒮,d)=(reph,𝒮,d,{w∈Rawh*∣zeroh,𝒮,d(w)}).T_h(\mathcal{S}, d) = \bigl(\mathrm{rep}_{h, \mathcal{S}, d},\; \{w \in \mathrm{Raw}_h^* \mid \mathrm{zero}_{h, \mathcal{S}, d}(w)\}\bigr).(11)✦

For q>0q > 0, the cell cut predicate Cut\mathrm{Cut} on 𝒞q\mathcal{C}_q holds for a cell c∈𝒞qc \in \mathcal{C}_q when (12) holds: Cut(c)⇔pos(c)=C(0) and (mark(c)=idle or blk(c)=0).\mathrm{Cut}(c) \iff \mathrm{pos}(c) = C(0) \text{ and } \bigl(\mathrm{mark}(c) = \mathrm{idle} \text{ or } \mathrm{blk}(c) = 0\bigr).(12)✦ At parameter h>0h > 0, the raw cut predicate Cuthraw\mathrm{Cut}_h^{\mathrm{raw}} on Rawh\mathrm{Raw}_h holds for a raw vector a∈Rawha \in \mathrm{Raw}_h when (13) holds: Cuthraw(a)⇔∃c∈𝒞qh such that dech(a)=c and Cut(c).\mathrm{Cut}_h^{\mathrm{raw}}(a) \iff \exists\, c \in \mathcal{C}_{q_h} \text{ such that } \mathrm{dec}_h(a) = c \text{ and } \mathrm{Cut}(c).(13)✦

For q>0q > 0, d∈ℕd \in \mathbb{N}, a bit vector ξ∈𝔽2[0,d)\xi \in \mathbb{F}_2^{[0, d)}, and a position p∈Posqp \in \mathrm{Pos}_q, the canonical cell canq,d(ξ,p)∈𝒞q\mathrm{can}_{q, d}(\xi, p) \in \mathcal{C}_q has skeleton (p,idle,meta0)(p, \mathrm{idle}, \mathrm{meta}_0), checker idle\mathrm{idle}, certificate 00, head head0\mathrm{head}_0, data(true)=0\mathrm{data}(\mathrm{true}) = 0, and data(false)=ξ(r)\mathrm{data}(\mathrm{false}) = \xi(r) when p=C(r)p = C(r) with r<dr < d and 00 otherwise; concatenating canq,d(ξ,C(p))\mathrm{can}_{q, d}(\xi, C(p)) for p=0,…,q−1p = 0, \dots, q - 1, then canq,d(ξ,P(x))\mathrm{can}_{q, d}(\xi, P(x)) for x=0,…,q−1x = 0, \dots, q - 1, and finally canq,d(ξ,S)\mathrm{can}_{q, d}(\xi, S) gives the canonical block Blockq,d(ξ)∈𝒞q*\mathrm{Block}_{q, d}(\xi) \in \mathcal{C}_q^* of length 2q+12q + 1, and concatenating Blockq,d(ξi)\mathrm{Block}_{q, d}(\xi_i) over a word (ξ1,…,ξm)(\xi_1, \dots, \xi_m) with ξi∈𝔽2[0,d)\xi_i \in \mathbb{F}_2^{[0, d)} gives the cell-word encoding EWq,d(ξ1,…,ξm)∈𝒞q*\mathrm{EW}_{q, d}(\xi_1, \dots, \xi_m) \in \mathcal{C}_q^*. For h,D∈ℕh, D \in \mathbb{N}, writing ench*\mathrm{enc}_h^* and scalars10000Dh*\mathrm{scalars}_{10000Dh}^* for letterwise applications to words, the hierarchy embedding ιh,D:RawDh*→Rawh*\iota_{h, D} : \mathrm{Raw}_{Dh}^* \to \mathrm{Raw}_h^* is defined by (14): ιh,D(w)=ench*(EWqh,10000Dh(scalars10000Dh*(w))).\iota_{h, D}(w) = \mathrm{enc}_h^*\bigl(\mathrm{EW}_{q_h, 10000Dh}\bigl( \mathrm{scalars}_{10000Dh}^*(w)\bigr)\bigr).(14)✦

In the paper, the result reads: presentations of associative algebras by words have elementary replacements v=v′v = v' between nonempty words of equal length and zero declarations v=0v = 0 with vv nonempty; at parameter h≥1h \ge 1 with qh=2hq_h = 2^h, letters in Σh\Sigma_h (written Rawh\mathrm{Raw}_h) carry structural types C(p)C(p), P(a)P(a), SS, transaction and palette-checker tracks, and data bits; and a clean block has both tracks idle and each palette color once, while a canonical block has colors in increasing order, giving Eh(a)E_h(a) (written ench*(Blockqh,d(a))\mathrm{enc}_h^*(\mathrm{Block}_{q_h, d}(a)) for data size dd) of length Lh=2qh+1L_h = 2q_h + 1.

What Is Checked

The definitions are stated over an arbitrary alphabet Σ\Sigma, a semiring or ring KK with monoid algebra K[Σ*]K[\Sigma^*], natural numbers qq, hh, and DD (requiring q>0q > 0 for cell formatting, transitions, and cuts, and h>0h > 0 for decoding, the raw presentation, and raw cuts), schedules 𝒮\mathcal{S} on qh=2hq_h = 2^h with data bounds d∈ℕd \in \mathbb{N}, syntactic skeletons of metadata bound 1010 paired with palette checkers, 𝔽2\mathbb{F}_2-valued data and certificate bits, and reading-head states, together with raw bit vectors of width 10000h10000h and 10000Dh10000Dh.