OctoInformBeta

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

Lemma 2.4: Local replacements preserve word syntax in context and under reachability, while coherence and rigid block layout govern region owners and heads

Syntax invariance and region head ownership for finite cell words.

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

In the local-rule machinery underlying the group construction, configurations are represented as finite words of cells organized into blocks, where active reading heads and palette color checkers carry out bounded local computations. Elementary rewriting rules modify only one or two adjacent cells at a time, while arbitrary surrounding subwords flank the modified region.

First, do admissible single-cell and two-cell replacements preserve global word syntax in arbitrary surrounding contexts and across multi-step derivations? Second, in a sequence of cells with compatible adjacent skeletons, does every non-idle cell belong to a region with a unique active head, and under a rigid block layout does that region encompass every core cell of its blocks?

Positions, Skeletons, and Palette Checkers

Let q∈ℕq \in \mathbb{N} be a bound parameter. A block cell position in 𝒫q\mathcal{P}_q is either a core position core(p)\mathrm{core}(p) with p∈{0,…,q−1}p \in \{0, \dots, q-1\}, a palette position palette(a)\mathrm{palette}(a) with color index a∈{0,…,q−1}a \in \{0, \dots, q-1\}, or the stop position stop\mathrm{stop}.✦ A cell shape in 𝒮q\mathcal{S}_q is either core(p)\mathrm{core}(p) with p∈{0,…,q−1}p \in \{0, \dots, q-1\}, palette\mathrm{palette}, or stop\mathrm{stop}.✦ A cell marker is one of five tags: idle\mathrm{idle}, left\mathrm{left} (left wing), boundary\mathrm{boundary}, full\mathrm{full} (full active head), or right\mathrm{right} (right wing).✦

For an arity bound k∈ℕk \in \mathbb{N}, a block metadata record in ℳk\mathcal{M}_k is a triple (a,z,b)(a, z, b) consisting of an arity a∈{0,…,k−1}a \in \{0, \dots, k-1\}, a Boolean zero-task flag z∈{false,true}z \in \{\mathrm{false}, \mathrm{true}\}, and a block index b∈{0,…,a}b \in \{0, \dots, a\}.✦ Taking k=10k = 10 gives the cell arity metadata set ℳ=ℳ10\mathcal{M} = \mathcal{M}_{10}✦, with default metadata m0=(0,false,0)∈ℳm_0 = (0, \mathrm{false}, 0) \in \mathcal{M}.✦

A cell syntactic skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} is a triple (pos(s),mk(s),meta(s))(\mathrm{pos}(s), \mathrm{mk}(s), \mathrm{meta}(s)) consisting of a position pos(s)∈𝒫q\mathrm{pos}(s) \in \mathcal{P}_q, a marker mk(s)\mathrm{mk}(s), and metadata meta(s)=(a(s),z(s),b(s))∈ℳk\mathrm{meta}(s) = (a(s), z(s), b(s)) \in \mathcal{M}_k.✦ Given a marker mm, the marked skeleton mark(s,m)\mathrm{mark}(s, m) replaces mk(s)\mathrm{mk}(s) by mm while preserving pos(s)\mathrm{pos}(s) and meta(s)\mathrm{meta}(s).✦ A skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} carries an active head marker if mk(s)∈{boundary,full}\mathrm{mk}(s) \in \{\mathrm{boundary}, \mathrm{full}\}.✦ An initial skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} is a skeleton with b(s)=0b(s) = 0 and pos(s)=core(0)\mathrm{pos}(s) = \mathrm{core}(0), and a terminal skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} is a skeleton with b(s)=a(s)b(s) = a(s) and pos(s)=stop\mathrm{pos}(s) = \mathrm{stop}. An admissible skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} is a skeleton such that mk(s)≠right\mathrm{mk}(s) \ne \mathrm{right} whenever ss is initial and mk(s)≠left\mathrm{mk}(s) \ne \mathrm{left} whenever ss is terminal.✦

A left-external skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} is a skeleton such that mk(s)=idle\mathrm{mk}(s) = \mathrm{idle}, or mk(s)≠right\mathrm{mk}(s) \ne \mathrm{right} and ss is initial.✦ A right-external skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} is a skeleton such that mk(s)∈{idle,boundary}\mathrm{mk}(s) \in \{\mathrm{idle}, \mathrm{boundary}\}, or mk(s)≠left\mathrm{mk}(s) \ne \mathrm{left} and ss is terminal.

Two skeletons s1,s2∈Skelq,ks_1, s_2 \in \mathrm{Skel}_{q, k} are structurally adjacent if their positions satisfy one of five rules: pos(s1)=core(p)\mathrm{pos}(s_1) = \mathrm{core}(p) and pos(s2)=core(r)\mathrm{pos}(s_2) = \mathrm{core}(r) with p+1=rp + 1 = r; pos(s1)=core(p)\mathrm{pos}(s_1) = \mathrm{core}(p) and pos(s2)=palette(a)\mathrm{pos}(s_2) = \mathrm{palette}(a) with p+1=qp + 1 = q; both pos(s1)\mathrm{pos}(s_1) and pos(s2)\mathrm{pos}(s_2) are palette positions; pos(s1)\mathrm{pos}(s_1) is a palette position and pos(s2)=stop\mathrm{pos}(s_2) = \mathrm{stop}; or pos(s1)=stop\mathrm{pos}(s_1) = \mathrm{stop} and pos(s2)=core(r)\mathrm{pos}(s_2) = \mathrm{core}(r) with r=0r = 0.✦ A skeleton s∈Skelq,ks \in \mathrm{Skel}_{q, k} accepts a marker mm on the left if m∈{full,right}m \in \{\mathrm{full}, \mathrm{right}\} when mk(s)=right\mathrm{mk}(s) = \mathrm{right}, and m=leftm = \mathrm{left} otherwise; ss accepts mm on the right if m∈{left,boundary,full}m \in \{\mathrm{left}, \mathrm{boundary}, \mathrm{full}\} when mk(s)=left\mathrm{mk}(s) = \mathrm{left}, and m=rightm = \mathrm{right} otherwise.✦ A pair of skeletons (s1,s2)∈Skelq,k×Skelq,k(s_1, s_2) \in \mathrm{Skel}_{q, k} \times \mathrm{Skel}_{q, k} satisfies internal skeleton consistency if a(s1)=a(s2)a(s_1) = a(s_2), z(s1)=z(s2)z(s_1) = z(s_2), b(s1)+1=b(s2)b(s_1) + 1 = b(s_2) when pos(s1)=stop\mathrm{pos}(s_1) = \mathrm{stop} and b(s1)=b(s2)b(s_1) = b(s_2) otherwise, s2s_2 is not initial, and s1s_1 is not terminal.✦

A compatible adjacent skeleton pair (s1,s2)∈Skelq,k×Skelq,k(s_1, s_2) \in \mathrm{Skel}_{q, k} \times \mathrm{Skel}_{q, k} is a pair of structurally adjacent skeletons such that either s1s_1 is right-external and s2s_2 is left-external, or neither is external, s1s_1 accepts mk(s2)\mathrm{mk}(s_2) on the right, s2s_2 accepts mk(s1)\mathrm{mk}(s_1) on the left, and (s1,s2)(s_1, s_2) satisfies internal skeleton consistency.✦ Extending Skelq,k\mathrm{Skel}_{q, k} with a blank boundary symbol ⊥\bot, the skeleton link relation holds on (⊥,⊥)(\bot, \bot), on (⊥,s)(\bot, s) when ss is left-external, on (s,⊥)(s, \bot) when ss is right-external, and on (s1,s2)(s_1, s_2) when (s1,s2)(s_1, s_2) is a compatible adjacent skeleton pair.✦ A finite sequence (s1,…,sm)(s_1, \dots, s_m) of skeletons in Skelq,k\mathrm{Skel}_{q, k} is closed if every sts_t is admissible and every adjacent pair in (⊥,s1,…,sm,⊥)(\bot, s_1, \dots, s_m, \bot) satisfies the link relation.✦

For a color set CC, a palette checker state in Check(C)\mathrm{Check}(C) is idle\mathrm{idle}, passed(x)\mathrm{passed}(x) with a sought color x∈Cx \in C, or an active checker head head(x)\mathrm{head}(x) seeking x∈Cx \in C.✦ Two adjacent checker states in Check(C)\mathrm{Check}(C) form a compatible checker pair if both are idle\mathrm{idle}, both are passed(x)\mathrm{passed}(x) for the same x∈Cx \in C, the left is passed(x)\mathrm{passed}(x) and the right is head(x)\mathrm{head}(x) for the same x∈Cx \in C, or the left is head(x)\mathrm{head}(x) and the right is idle\mathrm{idle}.✦ A checker state χ∈Check(C)\chi \in \mathrm{Check}(C) satisfies the terminal checker condition if it is idle\mathrm{idle} or head(x)\mathrm{head}(x) for some x∈Cx \in C, and fails if it is passed(x)\mathrm{passed}(x).✦

Cells, Tasks, and Word Syntax

A three-bit register state r∈𝔽23r \in \mathbb{F}_2^3 is a map on {0,1,2}\{0, 1, 2\}.✦ A head computation phase is one of nine stages: acquisition\text{acquisition}, read-left\text{read-left}, read-right\text{read-right}, before-gate\text{before-gate}, after-gate\text{after-gate}, undo-left\text{undo-left}, undo-right\text{undo-right}, finish\text{finish}, or success\text{success}.✦ An endpoint phase is a phase that is acquisition\text{acquisition}, before-gate\text{before-gate}, after-gate\text{after-gate}, finish\text{finish}, or success\text{success}.✦ A reading head state h∈ℋqh \in \mathcal{H}_q is a quadruple (s,j,p,r)(s, j, p, r) consisting of a side s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, a clause index j∈{0,…,q−1}j \in \{0, \dots, q-1\}, a head computation phase pp, and a register state r∈𝔽23r \in \mathbb{F}_2^3; the default head state is h0=(false,0,acquisition,0)h_0 = (\mathrm{false}, 0, \text{acquisition}, 0).✦

For a bound qq, a finite table cell c∈𝒞qc \in \mathcal{C}_q consists of a skeleton skel(c)∈Skelq,10\mathrm{skel}(c) \in \mathrm{Skel}_{q, 10}, a checker state chk(c)∈Check({0,…,q−1})\mathrm{chk}(c) \in \mathrm{Check}(\{0, \dots, q-1\}), a pair of data bits datac:{false,true}→𝔽2\mathrm{data}_c : \{\mathrm{false}, \mathrm{true}\} \to \mathbb{F}_2, a certificate bit cert(c)∈𝔽2\mathrm{cert}(c) \in \mathbb{F}_2, and a reading head state hd(c)∈ℋq\mathrm{hd}(c) \in \mathcal{H}_q.✦ For a cell c∈𝒞qc \in \mathcal{C}_q, its position pos(c)\mathrm{pos}(c), marker mk(c)\mathrm{mk}(c), and metadata meta(c)=(a(c),z(c),b(c))\mathrm{meta}(c) = (a(c), z(c), b(c)) are those of skel(c)\mathrm{skel}(c), and its cell shape shape(c)∈𝒮q\mathrm{shape}(c) \in \mathcal{S}_q maps core(p)\mathrm{core}(p) to core(p)\mathrm{core}(p), any palette(a)\mathrm{palette}(a) to palette\mathrm{palette}, and stop\mathrm{stop} to stop\mathrm{stop}.✦ A cell c∈𝒞qc \in \mathcal{C}_q is in the core if pos(c)=core(p)\mathrm{pos}(c) = \mathrm{core}(p) for some p<qp < q✦, and cc is in the palette if pos(c)=palette(a)\mathrm{pos}(c) = \mathrm{palette}(a) for some a<qa < q.✦ A head-free cell c∈𝒞qc \in \mathcal{C}_q is a cell whose skeleton does not carry an active head marker and whose checker satisfies chk(c)≠head(x)\mathrm{chk}(c) \ne \mathrm{head}(x) for every x<qx < q.✦

A cell memory address a∈𝒜qa \in \mathcal{A}_q is either a data address addrdata(s,b,p)\mathrm{addr}_{\mathrm{data}}(s, b, p) specified by a side s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, a block index b∈{0,…,9}b \in \{0, \dots, 9\}, and a position p<qp < q, or a certificate address addrcert(p)\mathrm{addr}_{\mathrm{cert}}(p) specified by p<qp < q.✦ Reading a cell c∈𝒞qc \in \mathcal{C}_q at an address a∈𝒜qa \in \mathcal{A}_q yields a bit read(a,c)∈𝔽2\mathrm{read}(a, c) \in \mathbb{F}_2: when pos(c)=core(r)\mathrm{pos}(c) = \mathrm{core}(r) with r=pr = p, it returns datac(s)\mathrm{data}_c(s) if a=addrdata(s,b,p)a = \mathrm{addr}_{\mathrm{data}}(s, b, p) and b(c)=bb(c) = b, and returns cert(c)\mathrm{cert}(c) if a=addrcert(p)a = \mathrm{addr}_{\mathrm{cert}}(p) and b(c)=0b(c) = 0; otherwise it returns 00.✦

A verification task specification t∈𝒯t \in \mathcal{T} is a pair (a,z)(a, z) consisting of an arity a∈{0,…,9}a \in \{0, \dots, 9\} and a zero-task flag z∈{false,true}z \in \{\mathrm{false}, \mathrm{true}\}.✦ The task projection sends metadata m=(a,z,b)∈ℳm = (a, z, b) \in \mathcal{M} to τ(m)=(a,z)∈𝒯\tau(m) = (a, z) \in \mathcal{T}, and for a cell cc we write τ(c)=τ(meta(c))\tau(c) = \tau(\mathrm{meta}(c)).✦ A verification clause CC of bound qq consists of three addresses αC(0),αC(1),αC(2)∈𝒜q\alpha_C(0), \alpha_C(1), \alpha_C(2) \in \mathcal{A}_q and a Boolean truth function θC:𝔽23→{false,true}\theta_C : \mathbb{F}_2^3 \to \{\mathrm{false}, \mathrm{true}\}.✦ Given a clause CC and a cell c∈𝒞qc \in \mathcal{C}_q, the clause register delta δC(c)∈𝔽23\delta_C(c) \in \mathbb{F}_2^3 has entries δC(c)(i)=read(αC(i),c)\delta_C(c)(i) = \mathrm{read}(\alpha_C(i), c) for i∈{0,1,2}i \in \{0, 1, 2\}.✦ A verification clause schedule SS of bound qq assigns to each task t∈𝒯t \in \mathcal{T} a positive clause count cntS(t)∈{1,…,q}\mathrm{cnt}_S(t) \in \{1, \dots, q\} and to each (t,j)(t, j) with j<qj < q a verification clause clS(t,j)\mathrm{cl}_S(t, j).✦

Given a schedule SS of bound qq and a data size d∈ℕd \in \mathbb{N}, a cell c∈𝒞qc \in \mathcal{C}_q satisfies the cell formatting condition for SS and dd when its head h=(sh,jh,ph,rh)=hd(c)h = (s_h, j_h, p_h, r_h) = \mathrm{hd}(c) satisfies (1): skel(c) is admissible,c not in palette⟹chk(c)=idle,pos(c)=core(p) with p≥d⟹datac=0,c not in core⟹datac=0 and cert(c)=0,mk(c)=idle⟹meta(c)=m0,h=h0,datac(true)=0,cert(c)=0,mk(c)∈{left,right}⟹h=h0,mk(c)=boundary⟹(jh,ph,rh)=(0,acquisition,0),skel(c) carries an active head and z(c)=true⟹sh=false,mk(c)=full⟹(ph=success⟹jh=0,ph≠success⟹jh<cntS(τ(c)),ph is an endpoint phase⟹skel(c) is terminal).\begin{aligned} &\mathrm{skel}(c) \text{ is admissible}, \quad c \text{ not in palette} \implies \mathrm{chk}(c) = \mathrm{idle}, \\ &\mathrm{pos}(c) = \mathrm{core}(p) \text{ with } p \ge d \implies \mathrm{data}_c = 0, \\ &c \text{ not in core} \implies \mathrm{data}_c = 0 \text{ and } \mathrm{cert}(c) = 0, \\ &\mathrm{mk}(c) = \mathrm{idle} \implies \mathrm{meta}(c) = m_0,\ h = h_0,\ \mathrm{data}_c(\mathrm{true}) = 0,\ \mathrm{cert}(c) = 0, \\ &\mathrm{mk}(c) \in \{\mathrm{left}, \mathrm{right}\} \implies h = h_0, \\ &\mathrm{mk}(c) = \mathrm{boundary} \implies (j_h, p_h, r_h) = (0, \text{acquisition}, 0), \\ &\mathrm{skel}(c) \text{ carries an active head and } z(c) = \mathrm{true} \implies s_h = \mathrm{false}, \\ &\mathrm{mk}(c) = \mathrm{full} \implies \bigl(p_h = \text{success} \implies j_h = 0,\ p_h \ne \text{success} \implies j_h < \mathrm{cnt}_S(\tau(c)), \\ &\qquad\qquad\qquad\quad p_h \text{ is an endpoint phase} \implies \mathrm{skel}(c) \text{ is terminal}\bigr). \end{aligned}(1)✦ Two adjacent cells a,b∈𝒞qa, b \in \mathcal{C}_q satisfy checker compatibility if whenever both are in the palette (chk(a),chk(b))(\mathrm{chk}(a), \mathrm{chk}(b)) is a compatible checker pair, and whenever aa is in the palette and pos(b)=stop\mathrm{pos}(b) = \mathrm{stop}, chk(a)\mathrm{chk}(a) satisfies the terminal checker condition.✦ Given a schedule SS of bound qq and a data size d∈ℕd \in \mathbb{N}, a finite cell word w=(c1,…,cm)w = (c_1, \dots, c_m) of cells in 𝒞q\mathcal{C}_q satisfies the cell word syntax condition SynS,d(w)\mathrm{Syn}_{S, d}(w) when (2) holds: (skel(c1),…,skel(cm)) is closed,(ct,ct+1) is checker-compatible for 1≤t<m,and every ct satisfies cell formatting for S and d.\begin{gathered} (\mathrm{skel}(c_1), \dots, \mathrm{skel}(c_m)) \text{ is closed}, \qquad (c_t, c_{t+1}) \text{ is checker-compatible for } 1 \le t < m, \\ \text{and every } c_t \text{ satisfies cell formatting for } S \text{ and } d. \end{gathered}(2)✦

Local Replacements and Reachability

Given a cell c∈𝒞qc \in \mathcal{C}_q and a side s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, the idle cell idle(c,s)\mathrm{idle}(c, s) keeps pos(c)\mathrm{pos}(c) and chk(c)\mathrm{chk}(c), resets the marker to idle\mathrm{idle}, metadata to m0m_0, head to h0h_0, and certificate to 00, and sets its data function to true↦0\mathrm{true} \mapsto 0 and false↦datac(s)\mathrm{false} \mapsto \mathrm{data}_c(s).✦ Given a cell c∈𝒞qc \in \mathcal{C}_q and a side s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, the boundary cell bd(c,s)\mathrm{bd}(c, s) sets the skeleton of cc to mark(skel(c),boundary)\mathrm{mark}(\mathrm{skel}(c), \mathrm{boundary}) and the head to (s,0,acquisition,0)(s, 0, \text{acquisition}, 0).✦ Given a cell c∈𝒞qc \in \mathcal{C}_q and a marker mm, the wing cell wing(c,m)\mathrm{wing}(c, m) sets the skeleton of cc to mark(skel(c),m)\mathrm{mark}(\mathrm{skel}(c), m) and the head to h0h_0; for a side s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, clause index j<qj < q, phase pp, and register state r∈𝔽23r \in \mathbb{F}_2^3, the full cell full(c,s,j,p,r)\mathrm{full}(c, s, j, p, r) sets the skeleton to mark(skel(c),full)\mathrm{mark}(\mathrm{skel}(c), \mathrm{full}) and the head to (s,j,p,r)(s, j, p, r). Given a cell c∈𝒞qc \in \mathcal{C}_q, checker state χ∈Check({0,…,q−1})\chi \in \mathrm{Check}(\{0, \dots, q-1\}), and color a<qa < q, the checker update chk(c←χ)\mathrm{chk}(c \leftarrow \chi) replaces chk(c)\mathrm{chk}(c) by χ\chi✦, and the color update col(c←a)\mathrm{col}(c \leftarrow a) replaces the position in skel(c)\mathrm{skel}(c) by palette(a)\mathrm{palette}(a).✦

For a schedule SS of bound qq, the unary cell transition u→S1vu \to_S^1 v on 𝒞q\mathcal{C}_q holds across the twelve rules in (3), where c∈𝒞qc \in \mathcal{C}_q, s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, j,j′<qj, j' < q, and r∈𝔽23r \in \mathbb{F}_2^3: idle(c,s)→bd(c,s)if skel(c) is initial,bd(c,s)→full(c,s,0,acquisition,0)if skel(c) is terminal,full(c,s,j,acquisition,r)→full(c,s,j,read-left,r)if skel(c) is terminal,full(c,s,j,read-left,r)→full(c,s,j,read-right,r)if skel(c) is initial,full(c,s,j,read-right,r)→full(c,s,j,before-gate,r)if skel(c) is terminal,full(c,s,j,before-gate,r)→full(c,s,j,after-gate,r)if skel(c) is terminaland θclS(τ(c),j)(r)=true,full(c,s,j,after-gate,r)→full(c,s,j,undo-left,r)if skel(c) is terminal,full(c,s,j,undo-left,r)→full(c,s,j,undo-right,r)if skel(c) is initial,full(c,s,j,undo-right,r)→full(c,s,j,finish,r)if skel(c) is terminal,full(c,s,j,finish,0)→full(c,s,j′,acquisition,0)if j+1=j′ and skel(c) is terminal,full(c,s,j,finish,0)→full(c,s,0,success,0)if j+1=cntS(τ(c))and skel(c) is terminal,full(c,s,0,success,0)→full(c,¬s,0,success,0)if skel(c) is terminal and z(c)=false.\begin{aligned} \mathrm{idle}(c, s) &\to \mathrm{bd}(c, s) && \text{if } \mathrm{skel}(c) \text{ is initial}, \\ \mathrm{bd}(c, s) &\to \mathrm{full}(c, s, 0, \text{acquisition}, 0) && \text{if } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, s, j, \text{acquisition}, r) &\to \mathrm{full}(c, s, j, \text{read-left}, r) && \text{if } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, s, j, \text{read-left}, r) &\to \mathrm{full}(c, s, j, \text{read-right}, r) && \text{if } \mathrm{skel}(c) \text{ is initial}, \\ \mathrm{full}(c, s, j, \text{read-right}, r) &\to \mathrm{full}(c, s, j, \text{before-gate}, r) && \text{if } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, s, j, \text{before-gate}, r) &\to \mathrm{full}(c, s, j, \text{after-gate}, r) && \text{if } \mathrm{skel}(c) \text{ is terminal} \\ &&&\quad \text{and } \theta_{\mathrm{cl}_S(\tau(c), j)}(r) = \mathrm{true}, \\ \mathrm{full}(c, s, j, \text{after-gate}, r) &\to \mathrm{full}(c, s, j, \text{undo-left}, r) && \text{if } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, s, j, \text{undo-left}, r) &\to \mathrm{full}(c, s, j, \text{undo-right}, r) && \text{if } \mathrm{skel}(c) \text{ is initial}, \\ \mathrm{full}(c, s, j, \text{undo-right}, r) &\to \mathrm{full}(c, s, j, \text{finish}, r) && \text{if } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, s, j, \text{finish}, 0) &\to \mathrm{full}(c, s, j', \text{acquisition}, 0) && \text{if } j + 1 = j' \text{ and } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, s, j, \text{finish}, 0) &\to \mathrm{full}(c, s, 0, \text{success}, 0) && \text{if } j + 1 = \mathrm{cnt}_S(\tau(c)) \\ &&&\quad \text{and } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, s, 0, \text{success}, 0) &\to \mathrm{full}(c, \neg s, 0, \text{success}, 0) && \text{if } \mathrm{skel}(c) \text{ is terminal and } z(c) = \mathrm{false}. \end{aligned}(3)✦

For cells a,b∈𝒞qa, b \in \mathcal{C}_q, write Pacq(a,b)P_{\mathrm{acq}}(a, b) when (mark(skel(a),left),mark(skel(b),boundary))(\mathrm{mark}(\mathrm{skel}(a), \mathrm{left}), \mathrm{mark}(\mathrm{skel}(b), \mathrm{boundary})) is a compatible adjacent skeleton pair, and Pstep(a,b)P_{\mathrm{step}}(a, b) when (mark(skel(a),full),mark(skel(b),right))(\mathrm{mark}(\mathrm{skel}(a), \mathrm{full}), \mathrm{mark}(\mathrm{skel}(b), \mathrm{right})) is a compatible adjacent skeleton pair. For j<qj < q, write δa,j=δclS(τ(a),j)(a)\delta_{a, j} = \delta_{\mathrm{cl}_S(\tau(a), j)}(a). The binary cell transition (u,v)→S2(u′,v′)(u, v) \to_S^2 (u', v') holds across the eight adjacent-cell rules in (4), where a,b∈𝒞qa, b \in \mathcal{C}_q, s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, j,p,w,x,y<qj, p, w, x, y < q, and r∈𝔽23r \in \mathbb{F}_2^3: (bd(a,s),idle(b,s))→(wing(a,left),bd(b,s))if Pacq(a,b),(wing(a,left),full(b,s,j,read-left,r))→(full(a,s,j,read-left,r+δa,j),wing(b,right))if Pstep(a,b),(full(a,s,j,read-right,r),wing(b,right))→(wing(a,left),full(b,s,j,read-right,r))if Pstep(a,b),(wing(a,left),full(b,s,j,undo-left,r))→(full(a,s,j,undo-left,r),wing(b,right))if Pstep(a,b),(full(a,s,j,undo-right,r),wing(b,right))→(wing(a,left),full(b,s,j,undo-right,r+δa,j))if Pstep(a,b),(a,chk(b←idle))→(a,chk(b←head(x)))if pos(a)=core(p),p+1=q,and b is in palette,(chk(a←head(x)),chk(b←idle))→(chk(a←passed(x)),chk(b←head(x)))if pos(a)=palette(w),w≠x,and b is in palette,(a,b)→(b,a)if pos(a)=palette(x),pos(b)=palette(y),col(a←y)=b,and a,b are head-free.\begin{aligned} (\mathrm{bd}(a, s), \mathrm{idle}(b, s)) &\to (\mathrm{wing}(a, \mathrm{left}), \mathrm{bd}(b, s)) && \text{if } P_{\mathrm{acq}}(a, b), \\ (\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, s, j, \text{read-left}, r)) &\to (\mathrm{full}(a, s, j, \text{read-left}, r + \delta_{a, j}), \mathrm{wing}(b, \mathrm{right})) && \text{if } P_{\mathrm{step}}(a, b), \\ (\mathrm{full}(a, s, j, \text{read-right}, r), \mathrm{wing}(b, \mathrm{right})) &\to (\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, s, j, \text{read-right}, r)) && \text{if } P_{\mathrm{step}}(a, b), \\ (\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, s, j, \text{undo-left}, r)) &\to (\mathrm{full}(a, s, j, \text{undo-left}, r), \mathrm{wing}(b, \mathrm{right})) && \text{if } P_{\mathrm{step}}(a, b), \\ (\mathrm{full}(a, s, j, \text{undo-right}, r), \mathrm{wing}(b, \mathrm{right})) &\to (\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, s, j, \text{undo-right}, r + \delta_{a, j})) && \text{if } P_{\mathrm{step}}(a, b), \\ (a, \mathrm{chk}(b \leftarrow \mathrm{idle})) &\to (a, \mathrm{chk}(b \leftarrow \mathrm{head}(x))) && \text{if } \mathrm{pos}(a) = \mathrm{core}(p),\ p + 1 = q, \\ &&&\quad \text{and } b \text{ is in palette}, \\ (\mathrm{chk}(a \leftarrow \mathrm{head}(x)), \mathrm{chk}(b \leftarrow \mathrm{idle})) &\to (\mathrm{chk}(a \leftarrow \mathrm{passed}(x)), \mathrm{chk}(b \leftarrow \mathrm{head}(x))) && \text{if } \mathrm{pos}(a) = \mathrm{palette}(w),\ w \ne x, \\ &&&\quad \text{and } b \text{ is in palette}, \\ (a, b) &\to (b, a) && \text{if } \mathrm{pos}(a) = \mathrm{palette}(x),\ \mathrm{pos}(b) = \mathrm{palette}(y), \\ &&&\quad \mathrm{col}(a \leftarrow y) = b,\ \text{and } a, b \text{ are head-free}. \end{aligned}(4)✦

Given a schedule SS of bound qq and a data size d∈ℕd \in \mathbb{N}, two cell words v,wv, w satisfy the replacement relation ReplS,d(v,w)\mathrm{Repl}_{S, d}(v, w) if every cell appearing in vv or ww satisfies cell formatting for SS and dd, and either v=(a)v = (a) and w=(b)w = (b) with a→S1ba \to_S^1 b or b→S1ab \to_S^1 a, or v=(a,b)v = (a, b) and w=(a′,b′)w = (a', b') with (a,b)→S2(a′,b′)(a, b) \to_S^2 (a', b') or (a′,b′)→S2(a,b)(a', b') \to_S^2 (a, b).✦ A cell word rewriting step v→S,dwv \to_{S, d} w holds if there exist cell words p,s,a,bp, s, a, b such that v=pasv = p a s, w=pbsw = p b s, and ReplS,d(a,b)\mathrm{Repl}_{S, d}(a, b).✦ Cell word reachability v→S,d*wv \to_{S, d}^* w is the reflexive-transitive closure of →S,d\to_{S, d}.✦

Regions, Ownership, and Rigid Block Layouts

A finite sequence f:{0,…,N−1}→𝒞qf : \{0, \dots, N-1\} \to \mathcal{C}_q of length N∈ℕN \in \mathbb{N} is coherent if skel(f(i))\mathrm{skel}(f(i)) and skel(f(j))\mathrm{skel}(f(j)) form a compatible adjacent skeleton pair for all i,j∈{0,…,N−1}i, j \in \{0, \dots, N-1\} with i+1=ji + 1 = j.✦ The exterior boundary condition holds for a sequence f:{0,…,N−1}→𝒞qf : \{0, \dots, N-1\} \to \mathcal{C}_q of length NN if skel(f(i))\mathrm{skel}(f(i)) is left-external whenever i=0i = 0 and right-external whenever i+1=Ni + 1 = N.✦

Given a cut predicate κ\kappa on {0,…,N−1}\{0, \dots, N-1\}, two indices i,j∈{0,…,N−1}i, j \in \{0, \dots, N-1\} are connected without cuts if ¬κ(k)\neg \kappa(k) for every kk satisfying min⁡(i,j)≤k<max⁡(i,j)\min(i, j) \le k < \max(i, j).✦ For f:{0,…,N−1}→𝒞qf : \{0, \dots, N-1\} \to \mathcal{C}_q, the cell cut predicate κf(i)\kappa_f(i) holds when skel(f(i))\mathrm{skel}(f(i)) is right-external.✦ Two indices i,j∈{0,…,N−1}i, j \in \{0, \dots, N-1\} lie in the same region of a sequence f:{0,…,N−1}→𝒞qf : \{0, \dots, N-1\} \to \mathcal{C}_q, written i∼fji \sim_f j, if ii and jj are connected without cuts with respect to κf\kappa_f.✦ An index h∈{0,…,N−1}h \in \{0, \dots, N-1\} owns an index i∈{0,…,N−1}i \in \{0, \dots, N-1\} in ff, written ownf(i,h)\mathrm{own}_f(i, h), if i∼fhi \sim_f h and skel(f(h))\mathrm{skel}(f(h)) carries an active head marker.✦ For each i∈{0,…,N−1}i \in \{0, \dots, N-1\}, the region component Cf(i)C_f(i) is the set {j∈{0,…,N−1}:i∼fj}\{j \in \{0, \dots, N-1\} : i \sim_f j\}✦, and its left endpoint is ℓf(i)=min⁡Cf(i)\ell_f(i) = \min C_f(i).✦

For a bound q∈ℕq \in \mathbb{N}, the rigid block width is Wq=2q+1W_q = 2q + 1.✦ Each coordinate k∈{0,…,Wq−1}k \in \{0, \dots, W_q - 1\} has block coordinate position posq(k)∈𝒫q\mathrm{pos}_q(k) \in \mathcal{P}_q given by core(k)\mathrm{core}(k) for k<qk < q, palette(k−q)\mathrm{palette}(k - q) for q≤k<2qq \le k < 2q, and stop\mathrm{stop} for k=2qk = 2q, and block coordinate shape shapeq(k)∈𝒮q\mathrm{shape}_q(k) \in \mathcal{S}_q given by core(k)\mathrm{core}(k) for k<qk < q, palette\mathrm{palette} for q≤k<2qq \le k < 2q, and stop\mathrm{stop} for k=2qk = 2q. For n∈ℕn \in \mathbb{N} blocks of width WqW_q, an index i∈{0,…,nWq−1}i \in \{0, \dots, n W_q - 1\} has block index block(i)=⌊i/Wq⌋\mathrm{block}(i) = \lfloor i / W_q \rfloor in {0,…,n−1}\{0, \dots, n-1\} and block coordinate coord(i)=imod⁡Wq\mathrm{coord}(i) = i \bmod W_q in {0,…,Wq−1}\{0, \dots, W_q - 1\}. Conversely, a block b∈{0,…,n−1}b \in \{0, \dots, n-1\} and offset k∈{0,…,Wq−1}k \in \{0, \dots, W_q - 1\} yield the cell index cell(b,k)=bWq+k\mathrm{cell}(b, k) = b W_q + k✦, and for p<qp < q the core index is coreq(b,p)=cell(b,p)\mathrm{core}_q(b, p) = \mathrm{cell}(b, p).✦

A sequence f:{0,…,nWq−1}→𝒞qf : \{0, \dots, n W_q - 1\} \to \mathcal{C}_q has a rigid block layout if shape(f(i))=shapeq(coord(i))\mathrm{shape}(f(i)) = \mathrm{shape}_q(\mathrm{coord}(i)) for all i∈{0,…,nWq−1}i \in \{0, \dots, n W_q - 1\}.✦ Given a sequence f:{0,…,nWq−1}→𝒞qf : \{0, \dots, n W_q - 1\} \to \mathcal{C}_q in rigid block layout and an index i∈{0,…,nWq−1}i \in \{0, \dots, n W_q - 1\} satisfying the local skeleton and cell hypotheses for region blocks, each offset b∈{0,…,a(f(i))}b \in \{0, \dots, a(f(i))\} defines a region block index βf(i,b)=block(ℓf(i))+b∈{0,…,n−1}\beta_f(i, b) = \mathrm{block}(\ell_f(i)) + b \in \{0, \dots, n-1\}.✦

The Claim

Theorem 1. Let SS be a verification clause schedule of bound qq and let d∈ℕd \in \mathbb{N} be a data size. For any cell words v,wv, w satisfying ReplS,d(v,w)\mathrm{Repl}_{S, d}(v, w) and any cell words p,sp, s, SynS,d(pvs)⇔SynS,d(pws).\mathrm{Syn}_{S, d}(p v s) \iff \mathrm{Syn}_{S, d}(p w s).(5)✦ For any cell words v,wv, w with v→S,d*wv \to_{S, d}^* w such that SynS,d(v)\mathrm{Syn}_{S, d}(v) holds, SynS,d(w).\mathrm{Syn}_{S, d}(w).(6)✦

Let f:{0,…,N−1}→𝒞qf : \{0, \dots, N-1\} \to \mathcal{C}_q be a coherent cell sequence satisfying the exterior boundary condition. For every index i∈{0,…,N−1}i \in \{0, \dots, N-1\} with mk(f(i))≠idle\mathrm{mk}(f(i)) \ne \mathrm{idle}, ∃h∈{0,…,N−1},ownf(i,h).\exists\, h \in \{0, \dots, N-1\},\quad \mathrm{own}_f(i, h).(7)✦ If f:{0,…,N−1}→𝒞qf : \{0, \dots, N-1\} \to \mathcal{C}_q is coherent and i,j∈{0,…,N−1}i, j \in \{0, \dots, N-1\} satisfy i∼fji \sim_f j with both skel(f(i))\mathrm{skel}(f(i)) and skel(f(j))\mathrm{skel}(f(j)) carrying active head markers, then i=j.i = j.(8)✦

Let f:{0,…,nWq−1}→𝒞qf : \{0, \dots, n W_q - 1\} \to \mathcal{C}_q be a sequence in rigid block layout such that the cell word (f(0),…,f(nWq−1))(f(0), \dots, f(n W_q - 1)) satisfies the cell word syntax condition SynS,d((f(0),…,f(nWq−1)))\mathrm{Syn}_{S, d}((f(0), \dots, f(n W_q - 1))), and let i∈{0,…,nWq−1}i \in \{0, \dots, n W_q - 1\} be an index with mk(f(i))=full\mathrm{mk}(f(i)) = \mathrm{full}. For every b∈{0,…,a(f(i))}b \in \{0, \dots, a(f(i))\} and every core position p∈{0,…,q−1}p \in \{0, \dots, q-1\}, i∼fcoreq(βf(i,b),p).i \sim_f \mathrm{core}_q(\beta_f(i, b), p).(9)✦

In the paper, the result reads: starting from a concatenation of complete clean blocks, the structural, transaction, and checker syntax (SynS,d\mathrm{Syn}_{S, d}) is preserved under all elementary replacements, distinct transactions never own cells of the same block, and the elementary moves are context safe at both untouched neighboring letters, even when two transaction regions abut. The library states these properties in terms of prefix-suffix word concatenation and reachability in (5) and (6), and cut-connected regions in rigid block layouts in (7) through (9).

What Is Checked

The syntax invariance statements (5) and (6) are stated over a verification clause schedule SS of bound qq, a data size d∈ℕd \in \mathbb{N}, and finite words of cells in 𝒞q\mathcal{C}_q related by cell word replacements and rewriting reachability. The region ownership statement (7) and head uniqueness statement (8) are stated over a coherent sequence of NN cells in 𝒞q\mathcal{C}_q, with the exterior boundary condition and a non-idle cell for (7) and with two same-region active head indices for (8). The region core statement (9) is stated over a sequence of nWqn W_q cells in rigid block layout and a cell index satisfying the local skeleton and cell hypotheses for region blocks, quantified over block offsets up to the cell’s arity and core positions below qq.