OctoInformBeta

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

Lemma 2.3: Abstract palette invariants under an auxiliary-head predicate and checker rollback with idle-palette sorting in finite-table words

Color completeness and normalization in surviving 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

Consider finite words of cells under symmetric one-cell and two-cell local replacement rules relative to forbidden one-cell and two-cell zero patterns. In a finite-table verification block, the segment between the final core position and the stop position consists of palette cells carrying a color and a checker state alongside transaction-head and memory fields governed by a verification clause schedule. The question is how avoiding all reachable zero factors constrains coloring and checker rollback on such a palette segment, first in an abstract model where auxiliary moves are governed by a head predicate and then in concrete finite-table cell words.

Abstract Palette Words

Let CC be a set of colors and AA a set of auxiliary states. The set 𝒦(C)\mathcal{K}(C) of palette checker states over CC consists of idle\mathrm{idle}, passed(x)\mathrm{passed}(x) for x∈Cx \in C, and head(x)\mathrm{head}(x) for x∈Cx \in C.✦ A palette cell aa over (C,A)(C, A) is a triple (col(a),chk(a),aux(a))∈C×𝒦(C)×A(\mathrm{col}(a), \mathrm{chk}(a), \mathrm{aux}(a)) \in C \times \mathcal{K}(C) \times A comprising a color col(a)\mathrm{col}(a), a checker state chk(a)\mathrm{chk}(a), and an auxiliary state aux(a)\mathrm{aux}(a). A palette word ww over (C,A)(C, A) is a finite sequence (a1,…,am)(a_1, \dots, a_m) (m≥0m \ge 0) of palette cells over (C,A)(C, A), with length |w|=m|w| = m and color list cols(w)=(col(a1),…,col(am))\mathrm{cols}(w) = (\mathrm{col}(a_1), \dots, \mathrm{col}(a_m)); write juxtaposition uvu v for word concatenation, identifying each cell aa with the one-cell word (a)(a).

Given a palette cell aa over (C,A)(C, A) and k∈𝒦(C)k \in \mathcal{K}(C), the checker update a[chk←k]a[\mathrm{chk} \leftarrow k] is the palette cell (col(a),k,aux(a))(\mathrm{col}(a), k, \mathrm{aux}(a)). For a palette word w=(a1,…,am)w = (a_1, \dots, a_m) over (C,A)(C, A), the idle-checker word idlepal(w)\mathrm{idle}_{\mathrm{pal}}(w) of ww is the palette word (a1[chk←idle],…,am[chk←idle])(a_1[\mathrm{chk} \leftarrow \mathrm{idle}], \dots, a_m[\mathrm{chk} \leftarrow \mathrm{idle}]) over (C,A)(C, A).

Two palette checker states (k1,k2)∈𝒦(C)2(k_1, k_2) \in \mathcal{K}(C)^2 form a compatible checker pair if both equal idle\mathrm{idle}, both equal passed(x)\mathrm{passed}(x) for some x∈Cx \in C, (k1,k2)=(passed(x),head(x))(k_1, k_2) = (\mathrm{passed}(x), \mathrm{head}(x)) for some x∈Cx \in C, or (k1,k2)=(head(x),idle)(k_1, k_2) = (\mathrm{head}(x), \mathrm{idle}) for some x∈Cx \in C.✦ A palette checker state k∈𝒦(C)k \in \mathcal{K}(C) satisfies the terminal checker condition if k=idlek = \mathrm{idle} or k=head(x)k = \mathrm{head}(x) for some x∈Cx \in C.✦ A palette word w=(a1,…,am)w = (a_1, \dots, a_m) over (C,A)(C, A) satisfies the palette syntax condition if every adjacent pair (chk(ai),chk(ai+1))(\mathrm{chk}(a_i), \mathrm{chk}(a_{i+1})) (1≤i<m1 \le i < m) is a compatible checker pair and, when m≥1m \ge 1, chk(am)\mathrm{chk}(a_m) satisfies the terminal checker condition.✦

The set 𝒵pal(C,A)\mathcal{Z}_{\mathrm{pal}}(C, A) of palette zeros over (C,A)(C, A) is the set of all palette words ww over (C,A)(C, A) for which at least one of three conditions holds: some cell aa in ww satisfies chk(a)=passed(x)\mathrm{chk}(a) = \mathrm{passed}(x) with col(a)=x\mathrm{col}(a) = x; two adjacent cells a,ba, b in ww satisfy col(a)=col(b)\mathrm{col}(a) = \mathrm{col}(b); or ww is nonempty and its last cell aa satisfies chk(a)=head(x)\mathrm{chk}(a) = \mathrm{head}(x) with col(a)≠x\mathrm{col}(a) \neq x.✦

Fix a predicate HH on AA. A directed palette rewrite v→Hwv \to_H w between palette words v,wv, w over (C,A)(C, A) holds when vv and ww are related by one of the four rules in (1), for any x∈Cx \in C, palette cells a,b,ai,bia, b, a_i, b_i over (C,A)(C, A), palette words p,sp, s over (C,A)(C, A), and m≥0m \ge 0: a[chk←idle]s→Ha[chk←head(x)]s,pa[chk←head(x)]b[chk←idle]s→Hpa[chk←passed(x)]b[chk←head(x)]s(col(a)≠x),pabs→Hpbas(chk(a)=chk(b),∀y∈C,chk(a)≠head(y),aux(a)=aux(b),¬H(aux(a))),(a1,…,am)→H(b1,…,bm)(col(ai)=col(bi),chk(ai)=chk(bi) for 1≤i≤m).\begin{aligned} a[\mathrm{chk} \leftarrow \mathrm{idle}] s &\to_H a[\mathrm{chk} \leftarrow \mathrm{head}(x)] s, \\ p\, a[\mathrm{chk} \leftarrow \mathrm{head}(x)]\, b[\mathrm{chk} \leftarrow \mathrm{idle}]\, s &\to_H p\, a[\mathrm{chk} \leftarrow \mathrm{passed}(x)]\, b[\mathrm{chk} \leftarrow \mathrm{head}(x)]\, s \quad (\mathrm{col}(a) \neq x), \\ p a b s &\to_H p b a s \quad (\mathrm{chk}(a) = \mathrm{chk}(b),\; \forall y \in C,\; \mathrm{chk}(a) \neq \mathrm{head}(y),\; \mathrm{aux}(a) = \mathrm{aux}(b),\; \neg H(\mathrm{aux}(a))), \\ (a_1, \dots, a_m) &\to_H (b_1, \dots, b_m) \quad (\mathrm{col}(a_i) = \mathrm{col}(b_i),\; \mathrm{chk}(a_i) = \mathrm{chk}(b_i)\text{ for }1 \le i \le m). \end{aligned}(1)✦ A symmetric palette step v↔Hwv \leftrightarrow_H w between palette words over (C,A)(C, A) holds if v→Hwv \to_H w or w→Hvw \to_H v✦, and the palette reachability relation ⇝H\rightsquigarrow_H on palette words over (C,A)(C, A) is the reflexive-transitive closure of ↔H\leftrightarrow_H.✦ A palette word ww over (C,A)(C, A) survives under HH if no palette word vv with w⇝Hvw \rightsquigarrow_H v belongs to 𝒵pal(C,A)\mathcal{Z}_{\mathrm{pal}}(C, A).✦

Block Syntactic Skeletons

The set ℳ\mathcal{M} of cell markers is the set {idle,left,boundary,full,right}\{\mathrm{idle}, \mathrm{left}, \mathrm{boundary}, \mathrm{full}, \mathrm{right}\}. For each integer arity bound k∈ℕk \in \mathbb{N}, a block metadata record mm of bound kk is a triple (ar(m),ζ(m),blk(m))(\mathrm{ar}(m), \zeta(m), \mathrm{blk}(m)) consisting of an arity ar(m)∈{0,…,k−1}\mathrm{ar}(m) \in \{0, \dots, k-1\}, a Boolean zero-task flag ζ(m)∈{false,true}\zeta(m) \in \{\mathrm{false}, \mathrm{true}\}, and a block index blk(m)∈{0,…,ar(m)}\mathrm{blk}(m) \in \{0, \dots, \mathrm{ar}(m)\}, and Metak\mathrm{Meta}_k is the set of these records.

For an integer position bound q∈ℕq \in \mathbb{N}, the set Posq\mathrm{Pos}_q of block cell positions consists of core positions core(p)\mathrm{core}(p) for 0≤p<q0 \le p < q, palette positions pal(x)\mathrm{pal}(x) for 0≤x<q0 \le x < q, and the position stop\mathrm{stop}.✦ A cell syntactic skeleton ss of bounds (q,k)(q, k) is a triple (pos(s),mark(s),meta(s))∈Posq×ℳ×Metak(\mathrm{pos}(s), \mathrm{mark}(s), \mathrm{meta}(s)) \in \mathrm{Pos}_q \times \mathcal{M} \times \mathrm{Meta}_k. For a cell syntactic skeleton ss of bounds (q,k)(q, k) and a marker m∈ℳm \in \mathcal{M}, the re-marked skeleton s[mark←m]s[\mathrm{mark} \leftarrow m] is the cell syntactic skeleton (pos(s),m,meta(s))(\mathrm{pos}(s), m, \mathrm{meta}(s)) of bounds (q,k)(q, k).

A syntactic skeleton ss of bounds (q,k)(q, k) is initial if blk(meta(s))=0\mathrm{blk}(\mathrm{meta}(s)) = 0 and pos(s)=core(0)\mathrm{pos}(s) = \mathrm{core}(0)✦, and terminal if blk(meta(s))=ar(meta(s))\mathrm{blk}(\mathrm{meta}(s)) = \mathrm{ar}(\mathrm{meta}(s)) and pos(s)=stop\mathrm{pos}(s) = \mathrm{stop}.✦ A syntactic skeleton ss of bounds (q,k)(q, k) is admissible if 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✦, and ss carries an active head marker if mark(s)∈{boundary,full}\mathrm{mark}(s) \in \{\mathrm{boundary}, \mathrm{full}\}.✦

Two syntactic skeletons s1,s2s_1, s_2 of bounds (q,k)(q, k) satisfy structural position adjacency if (pos(s1),pos(s2))(\mathrm{pos}(s_1), \mathrm{pos}(s_2)) has one of the five forms (core(p),core(r))(\mathrm{core}(p), \mathrm{core}(r)) with p+1=rp + 1 = r, (core(p),pal(x))(\mathrm{core}(p), \mathrm{pal}(x)) with p+1=qp + 1 = q, (pal(x),pal(y))(\mathrm{pal}(x), \mathrm{pal}(y)), (pal(x),stop)(\mathrm{pal}(x), \mathrm{stop}), or (stop,core(0))(\mathrm{stop}, \mathrm{core}(0)). A pair (s1,s2)(s_1, s_2) of syntactic skeletons of bounds (q,k)(q, k) satisfies internal consistency if ar(meta(s1))=ar(meta(s2))\mathrm{ar}(\mathrm{meta}(s_1)) = \mathrm{ar}(\mathrm{meta}(s_2)), ζ(meta(s1))=ζ(meta(s2))\zeta(\mathrm{meta}(s_1)) = \zeta(\mathrm{meta}(s_2)), the block indices satisfy blk(meta(s2))=blk(meta(s1))+1\mathrm{blk}(\mathrm{meta}(s_2)) = \mathrm{blk}(\mathrm{meta}(s_1)) + 1 when pos(s1)=stop\mathrm{pos}(s_1) = \mathrm{stop} and blk(meta(s2))=blk(meta(s1))\mathrm{blk}(\mathrm{meta}(s_2)) = \mathrm{blk}(\mathrm{meta}(s_1)) otherwise, s2s_2 is not initial, and s1s_1 is not terminal.

A syntactic skeleton ss of bounds (q,k)(q, k) accepts a marker m∈ℳm \in \mathcal{M} on the left if m∈{full,right}m \in \{\mathrm{full}, \mathrm{right}\} when mark(s)=right\mathrm{mark}(s) = \mathrm{right} and m=leftm = \mathrm{left} otherwise✦, and accepts mm on the right if m∈{left,boundary,full}m \in \{\mathrm{left}, \mathrm{boundary}, \mathrm{full}\} when mark(s)=left\mathrm{mark}(s) = \mathrm{left} and m=rightm = \mathrm{right} otherwise.✦ A syntactic skeleton ss of bounds (q,k)(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.✦

The set 𝒫skel(q,k)\mathcal{P}_{\mathrm{skel}}(q, k) of compatible adjacent skeleton pairs of bounds (q,k)(q, k) is the set of all pairs (s1,s2)(s_1, s_2) of syntactic skeletons of bounds (q,k)(q, k) that satisfy structural position adjacency and either have s1s_1 right-external and s2s_2 left-external, or have neither s1s_1 right-external nor s2s_2 left-external while s1s_1 accepts mark(s2)\mathrm{mark}(s_2) on the right, s2s_2 accepts mark(s1)\mathrm{mark}(s_1) on the left, and (s1,s2)(s_1, s_2) satisfies internal consistency.✦

Cells and Survival in Finite Tables

Fix a positive integer bound q≥1q \ge 1. A cell memory address of bound qq is either a data address data(s,b,p)\mathrm{data}(s, b, p) specified by a Boolean side s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, a block index b∈{0,…,9}b \in \{0, \dots, 9\}, and a position index p∈{0,…,q−1}p \in \{0, \dots, q-1\}, or a certificate address cert(p)\mathrm{cert}(p) with p∈{0,…,q−1}p \in \{0, \dots, q-1\}; write Addrq\mathrm{Addr}_q for the set of these addresses.✦ The additive group Reg\mathrm{Reg} of three-bit register states is the group of functions r:{0,1,2}→𝔽2r : \{0, 1, 2\} \to \mathbb{F}_2 over 𝔽2\mathbb{F}_2.✦ A verification clause CC of bound qq is a pair (addrC,truthC)(\mathrm{addr}_C, \mathrm{truth}_C) consisting of an address triple addrC:{0,1,2}→Addrq\mathrm{addr}_C : \{0, 1, 2\} \to \mathrm{Addr}_q and a Boolean truth function truthC:Reg→{false,true}\mathrm{truth}_C : \mathrm{Reg} \to \{\mathrm{false}, \mathrm{true}\}.✦

A verification task tt is a pair (ar(t),ζ(t))(\mathrm{ar}(t), \zeta(t)) consisting of an arity ar(t)∈{0,…,9}\mathrm{ar}(t) \in \{0, \dots, 9\} and a Boolean zero-task flag ζ(t)∈{false,true}\zeta(t) \in \{\mathrm{false}, \mathrm{true}\}.✦ A verification clause schedule 𝒮\mathcal{S} of bound qq assigns to each verification task tt a clause count cnt𝒮(t)\mathrm{cnt}_{\mathcal{S}}(t) satisfying 1≤cnt𝒮(t)≤q1 \le \mathrm{cnt}_{\mathcal{S}}(t) \le q and a family of verification clauses C𝒮(t,j)C_{\mathcal{S}}(t, j) of bound qq indexed by j∈{0,…,q−1}j \in \{0, \dots, q-1\}.✦

The set of head computation phases consists of nine sequential 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}.✦ A reading head state hh of bound qq is a quadruple (side(h),cl(h),ph(h),reg(h))(\mathrm{side}(h), \mathrm{cl}(h), \mathrm{ph}(h), \mathrm{reg}(h)) consisting of a Boolean side side(h)\mathrm{side}(h), a clause index cl(h)∈{0,…,q−1}\mathrm{cl}(h) \in \{0, \dots, q-1\}, a head computation phase ph(h)\mathrm{ph}(h), and a three-bit register state reg(h)∈Reg\mathrm{reg}(h) \in \mathrm{Reg}; the default reading head state h0h_0 of bound qq is the reading head state (false,0,acquisition,0)(\mathrm{false}, 0, \mathrm{acquisition}, 0) of bound qq.✦

A cell arity metadata record mm is an element of Meta10\mathrm{Meta}_{10}✦, and the associated task task(m)\mathrm{task}(m) of mm is the verification task (ar(m),ζ(m))(\mathrm{ar}(m), \zeta(m)).✦ The default cell metadata record m0m_0 is the element (0,false,0)∈Meta10(0, \mathrm{false}, 0) \in \mathrm{Meta}_{10}.✦

A finite-table cell cc of bound qq is a tuple (skel(c),chk(c),data(c),cert(c),head(c))(\mathrm{skel}(c), \mathrm{chk}(c), \mathrm{data}(c), \mathrm{cert}(c), \mathrm{head}(c)) consisting of a syntactic skeleton skel(c)\mathrm{skel}(c) of bounds (q,10)(q, 10), a palette checker state chk(c)∈𝒦({0,…,q−1})\mathrm{chk}(c) \in \mathcal{K}(\{0, \dots, q-1\}), a data function data(c):{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 head(c)\mathrm{head}(c) of bound qq. Write pos(c)\mathrm{pos}(c), mark(c)\mathrm{mark}(c), and meta(c)\mathrm{meta}(c) for the position, marker, and metadata of skel(c)\mathrm{skel}(c); a finite-table cell cc of bound qq is a core cell if pos(c)=core(p)\mathrm{pos}(c) = \mathrm{core}(p) for some p∈{0,…,q−1}p \in \{0, \dots, q-1\} and a palette cell if pos(c)=pal(x)\mathrm{pos}(c) = \mathrm{pal}(x) for some x∈{0,…,q−1}x \in \{0, \dots, q-1\}.

For a finite-table cell cc of bound qq, its color col(c)∈{0,…,q−1}\mathrm{col}(c) \in \{0, \dots, q-1\} equals xx when pos(c)=pal(x)\mathrm{pos}(c) = \mathrm{pal}(x) and 00 otherwise; for a finite sequence (or cell word) w=(c1,…,cm)w = (c_1, \dots, c_m) of finite-table cells of bound qq, write |w|=m|w| = m and cols(w)=(col(c1),…,col(cm))\mathrm{cols}(w) = (\mathrm{col}(c_1), \dots, \mathrm{col}(c_m)).✦ For a finite-table cell cc of bound qq and x∈{0,…,q−1}x \in \{0, \dots, q-1\}, the recolored cell c[col←x]c[\mathrm{col} \leftarrow x] is the finite-table cell of bound qq obtained by replacing pos(skel(c))\mathrm{pos}(\mathrm{skel}(c)) with pal(x)\mathrm{pal}(x) while preserving all other fields of cc✦, and the color erasure erase(c)\mathrm{erase}(c) of cc is the finite-table cell c[col←0]c[\mathrm{col} \leftarrow 0] of bound qq.✦ For a finite-table cell cc of bound qq and k∈𝒦({0,…,q−1})k \in \mathcal{K}(\{0, \dots, q-1\}), the checker update c[chk←k]c[\mathrm{chk} \leftarrow k] is the finite-table cell of bound qq obtained by replacing chk(c)\mathrm{chk}(c) with kk while preserving all other fields of cc.✦ A finite-table cell cc of bound qq is head-free if skel(c)\mathrm{skel}(c) does not carry an active head marker and chk(c)≠head(x)\mathrm{chk}(c) \neq \mathrm{head}(x) for every x∈{0,…,q−1}x \in \{0, \dots, q-1\}.

Four operations modify the marker and transaction fields of a finite-table cell cc of bound qq: for s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, the boundary cell bnd(c,s)\mathrm{bnd}(c, s) replaces skel(c)\mathrm{skel}(c) with skel(c)[mark←boundary]\mathrm{skel}(c)[\mathrm{mark} \leftarrow \mathrm{boundary}] and sets the head to (s,0,acquisition,0)(s, 0, \mathrm{acquisition}, 0)✦; for m∈ℳm \in \mathcal{M}, the wing cell wing(c,m)\mathrm{wing}(c, m) replaces skel(c)\mathrm{skel}(c) with skel(c)[mark←m]\mathrm{skel}(c)[\mathrm{mark} \leftarrow m] and sets the head to h0h_0✦; for s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, j∈{0,…,q−1}j \in \{0, \dots, q-1\}, phase ϕ\phi, and r∈Regr \in \mathrm{Reg}, the full cell full(c,s,j,ϕ,r)\mathrm{full}(c, s, j, \phi, r) replaces skel(c)\mathrm{skel}(c) with skel(c)[mark←full]\mathrm{skel}(c)[\mathrm{mark} \leftarrow \mathrm{full}] and sets the head to (s,j,ϕ,r)(s, j, \phi, r)✦; and for s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, the idle cell idlecell(c,s)\mathrm{idle}_{\mathrm{cell}}(c, s) replaces skel(c)\mathrm{skel}(c) with (pos(c),idle,m0)(\mathrm{pos}(c), \mathrm{idle}, m_0), sets the head to h0h_0 and the certificate bit to 00, keeps chk(c)\mathrm{chk}(c) unchanged, and replaces data(c)\mathrm{data}(c) with the function mapping true\mathrm{true} to 00 and false\mathrm{false} to data(c)(s)\mathrm{data}(c)(s).✦

The bit read read(a,c)∈𝔽2\mathrm{read}(a, c) \in \mathbb{F}_2 from a finite-table cell cc of bound qq at an address a∈Addrqa \in \mathrm{Addr}_q is given by (2): read(a,c)={data(c)(s)if a=data(s,b,p),pos(c)=core(p),blk(meta(c))=b,cert(c)if a=cert(p),pos(c)=core(p),blk(meta(c))=0,0otherwise.\mathrm{read}(a, c) = \begin{cases} \mathrm{data}(c)(s) & \text{if } a = \mathrm{data}(s, b, p),\; \mathrm{pos}(c) = \mathrm{core}(p),\; \mathrm{blk}(\mathrm{meta}(c)) = b, \\ \mathrm{cert}(c) & \text{if } a = \mathrm{cert}(p),\; \mathrm{pos}(c) = \mathrm{core}(p),\; \mathrm{blk}(\mathrm{meta}(c)) = 0, \\ 0 & \text{otherwise.} \end{cases}(2)✦ For a verification clause CC of bound qq and a finite-table cell cc of bound qq, the clause register delta Δ(C,c)∈Reg\Delta(C, c) \in \mathrm{Reg} is defined at each i∈{0,1,2}i \in \{0, 1, 2\} by Δ(C,c)(i)=read(addrC(i),c)\Delta(C, c)(i) = \mathrm{read}(\mathrm{addr}_C(i), c).✦

A head computation phase ϕ\phi is an endpoint phase if ϕ∈{acquisition,before-gate,after-gate,finish,success}\phi \in \{\mathrm{acquisition}, \mathrm{before\text{-}gate}, \mathrm{after\text{-}gate}, \mathrm{finish}, \mathrm{success}\}. Given a verification clause schedule 𝒮\mathcal{S} of bound qq and a data size d∈ℕd \in \mathbb{N}, a finite-table cell cc of bound qq satisfies the cell formatting condition for (𝒮,d)(\mathcal{S}, d) if the following conditions hold: skel(c)\mathrm{skel}(c) is admissible; if cc is not a palette cell then chk(c)=idle\mathrm{chk}(c) = \mathrm{idle}; if pos(c)=core(p)\mathrm{pos}(c) = \mathrm{core}(p) with p≥dp \ge d then data(c)(false)=data(c)(true)=0\mathrm{data}(c)(\mathrm{false}) = \mathrm{data}(c)(\mathrm{true}) = 0; if cc is not a core cell then data(c)(false)=data(c)(true)=0\mathrm{data}(c)(\mathrm{false}) = \mathrm{data}(c)(\mathrm{true}) = 0 and cert(c)=0\mathrm{cert}(c) = 0; if mark(c)=idle\mathrm{mark}(c) = \mathrm{idle} then meta(c)=m0\mathrm{meta}(c) = m_0, head(c)=h0\mathrm{head}(c) = h_0, data(c)(true)=0\mathrm{data}(c)(\mathrm{true}) = 0, and cert(c)=0\mathrm{cert}(c) = 0; if mark(c)∈{left,right}\mathrm{mark}(c) \in \{\mathrm{left}, \mathrm{right}\} then head(c)=h0\mathrm{head}(c) = h_0; if mark(c)=boundary\mathrm{mark}(c) = \mathrm{boundary} then cl(head(c))=0\mathrm{cl}(\mathrm{head}(c)) = 0, ph(head(c))=acquisition\mathrm{ph}(\mathrm{head}(c)) = \mathrm{acquisition}, and reg(head(c))=0\mathrm{reg}(\mathrm{head}(c)) = 0; if skel(c)\mathrm{skel}(c) carries an active head marker and ζ(meta(c))=true\zeta(\mathrm{meta}(c)) = \mathrm{true} then side(head(c))=false\mathrm{side}(\mathrm{head}(c)) = \mathrm{false}; and if mark(c)=full\mathrm{mark}(c) = \mathrm{full} then ph(head(c))=success\mathrm{ph}(\mathrm{head}(c)) = \mathrm{success} implies cl(head(c))=0\mathrm{cl}(\mathrm{head}(c)) = 0, ph(head(c))≠success\mathrm{ph}(\mathrm{head}(c)) \neq \mathrm{success} implies cl(head(c))<cnt𝒮(task(meta(c)))\mathrm{cl}(\mathrm{head}(c)) < \mathrm{cnt}_{\mathcal{S}}(\mathrm{task}(\mathrm{meta}(c))), and ph(head(c))\mathrm{ph}(\mathrm{head}(c)) being an endpoint phase implies skel(c)\mathrm{skel}(c) is terminal.

Two finite-table cells a,ba, b of bound qq satisfy checker compatibility if whenever both are palette cells the pair (chk(a),chk(b))(\mathrm{chk}(a), \mathrm{chk}(b)) is a compatible checker pair in 𝒦({0,…,q−1})\mathcal{K}(\{0, \dots, q-1\}), and whenever aa is a palette cell and pos(b)=stop\mathrm{pos}(b) = \mathrm{stop} the checker state chk(a)\mathrm{chk}(a) satisfies the terminal checker condition.✦ A pair (a,b)(a, b) of finite-table cells of bound qq forms a compatible adjacent cell pair if (skel(a),skel(b))∈𝒫skel(q,10)(\mathrm{skel}(a), \mathrm{skel}(b)) \in \mathcal{P}_{\mathrm{skel}}(q, 10) and a,ba, b satisfy checker compatibility.

Given a verification clause schedule 𝒮\mathcal{S} of bound qq, the unary cell transition c1→un,𝒮c2c_1 \to_{\mathrm{un}, \mathcal{S}} c_2 between finite-table cells of bound qq holds in the twelve cases of (3), for any cell cc, side s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\} with opposite side ¬s\neg s, clause indices j,j′∈{0,…,q−1}j, j' \in \{0, \dots, q-1\}, and register r∈Regr \in \mathrm{Reg}: idlecell(c,s)→un,𝒮bnd(c,s)if skel(c) is initial,bnd(c,s)→un,𝒮full(c,s,0,acquisition,0)if skel(c) is terminal,full(c,s,j,acquisition,r)→un,𝒮full(c,s,j,read-left,r)if skel(c) is terminal,full(c,s,j,read-left,r)→un,𝒮full(c,s,j,read-right,r)if skel(c) is initial,full(c,s,j,read-right,r)→un,𝒮full(c,s,j,before-gate,r)if skel(c) is terminal,full(c,s,j,before-gate,r)→un,𝒮full(c,s,j,after-gate,r)if skel(c) is terminal and truthC𝒮(task(meta(c)),j)(r)=true,full(c,s,j,after-gate,r)→un,𝒮full(c,s,j,undo-left,r)if skel(c) is terminal,full(c,s,j,undo-left,r)→un,𝒮full(c,s,j,undo-right,r)if skel(c) is initial,full(c,s,j,undo-right,r)→un,𝒮full(c,s,j,finish,r)if skel(c) is terminal,full(c,s,j,finish,0)→un,𝒮full(c,s,j′,acquisition,0)if skel(c) is terminal and j+1=j′,full(c,s,j,finish,0)→un,𝒮full(c,s,0,success,0)if skel(c) is terminal and j+1=cnt𝒮(task(meta(c))),full(c,s,0,success,0)→un,𝒮full(c,¬s,0,success,0)if skel(c) is terminal and ζ(meta(c))=false.\begin{aligned} \mathrm{idle}_{\mathrm{cell}}(c, s) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{bnd}(c, s) && \text{if }\mathrm{skel}(c)\text{ is initial}, \\ \mathrm{bnd}(c, s) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{full}(c, s, 0, \mathrm{acquisition}, 0) && \text{if }\mathrm{skel}(c)\text{ is terminal}, \\ \mathrm{full}(c, s, j, \mathrm{acquisition}, r) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{full}(c, s, j, \mathrm{read\text{-}left}, r) && \text{if }\mathrm{skel}(c)\text{ is terminal}, \\ \mathrm{full}(c, s, j, \mathrm{read\text{-}left}, r) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{full}(c, s, j, \mathrm{read\text{-}right}, r) && \text{if }\mathrm{skel}(c)\text{ is initial}, \\ \mathrm{full}(c, s, j, \mathrm{read\text{-}right}, r) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{full}(c, s, j, \mathrm{before\text{-}gate}, r) && \text{if }\mathrm{skel}(c)\text{ is terminal}, \\ \mathrm{full}(c, s, j, \mathrm{before\text{-}gate}, r) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{full}(c, s, j, \mathrm{after\text{-}gate}, r) && \text{if }\mathrm{skel}(c)\text{ is terminal and }\mathrm{truth}_{C_{\mathcal{S}}(\mathrm{task}(\mathrm{meta}(c)), j)}(r) = \mathrm{true}, \\ \mathrm{full}(c, s, j, \mathrm{after\text{-}gate}, r) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{full}(c, s, j, \mathrm{undo\text{-}left}, r) && \text{if }\mathrm{skel}(c)\text{ is terminal}, \\ \mathrm{full}(c, s, j, \mathrm{undo\text{-}left}, r) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{full}(c, s, j, \mathrm{undo\text{-}right}, r) && \text{if }\mathrm{skel}(c)\text{ is initial}, \\ \mathrm{full}(c, s, j, \mathrm{undo\text{-}right}, r) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{full}(c, s, j, \mathrm{finish}, r) && \text{if }\mathrm{skel}(c)\text{ is terminal}, \\ \mathrm{full}(c, s, j, \mathrm{finish}, 0) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{full}(c, s, j', \mathrm{acquisition}, 0) && \text{if }\mathrm{skel}(c)\text{ is terminal and }j + 1 = j', \\ \mathrm{full}(c, s, j, \mathrm{finish}, 0) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{full}(c, s, 0, \mathrm{success}, 0) && \text{if }\mathrm{skel}(c)\text{ is terminal and }j + 1 = \mathrm{cnt}_{\mathcal{S}}(\mathrm{task}(\mathrm{meta}(c))), \\ \mathrm{full}(c, s, 0, \mathrm{success}, 0) &\to_{\mathrm{un}, \mathcal{S}} \mathrm{full}(c, \neg s, 0, \mathrm{success}, 0) && \text{if }\mathrm{skel}(c)\text{ is terminal and }\zeta(\mathrm{meta}(c)) = \mathrm{false}. \end{aligned}(3)✦

For a verification clause schedule 𝒮\mathcal{S} of bound qq, let Pfr(a,b)P_{\mathrm{fr}}(a, b) denote (skel(a)[mark←full],skel(b)[mark←right])∈𝒫skel(q,10)(\mathrm{skel}(a)[\mathrm{mark} \leftarrow \mathrm{full}],\, \mathrm{skel}(b)[\mathrm{mark} \leftarrow \mathrm{right}]) \in \mathcal{P}_{\mathrm{skel}}(q, 10) and write δ(a,j)=Δ(C𝒮(task(meta(a)),j),a)\delta(a, j) = \Delta(C_{\mathcal{S}}(\mathrm{task}(\mathrm{meta}(a)), j), a). The binary cell transition (a1,b1)→bin,𝒮(a2,b2)(a_1, b_1) \to_{\mathrm{bin}, \mathcal{S}} (a_2, b_2) on pairs of finite-table cells of bound qq holds in the eight cases of (4), for any cells a,ba, b, s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, j,p,v,x,y∈{0,…,q−1}j, p, v, x, y \in \{0, \dots, q-1\}, and r∈Regr \in \mathrm{Reg}: (bnd(a,s),idlecell(b,s))→bin,𝒮(wing(a,left),bnd(b,s))if (skel(a)[mark←left],skel(b)[mark←boundary])∈𝒫skel(q,10),(wing(a,left),full(b,s,j,read-left,r))→bin,𝒮(full(a,s,j,read-left,r+δ(a,j)),wing(b,right))if Pfr(a,b),(full(a,s,j,read-right,r),wing(b,right))→bin,𝒮(wing(a,left),full(b,s,j,read-right,r))if Pfr(a,b),(wing(a,left),full(b,s,j,undo-left,r))→bin,𝒮(full(a,s,j,undo-left,r),wing(b,right))if Pfr(a,b),(full(a,s,j,undo-right,r),wing(b,right))→bin,𝒮(wing(a,left),full(b,s,j,undo-right,r+δ(a,j)))if Pfr(a,b),(a,b[chk←idle])→bin,𝒮(a,b[chk←head(x)])if pos(a)=core(p),p+1=q,b is a palette cell,(a[chk←head(x)],b[chk←idle])→bin,𝒮(a[chk←passed(x)],b[chk←head(x)])if pos(a)=pal(v),b is a palette cell,v≠x,(a,b)→bin,𝒮(b,a)if pos(a)=pal(x),pos(b)=pal(y),a[col←y]=b,a,b head-free.\begin{aligned} \bigl(\mathrm{bnd}(a, s),\, \mathrm{idle}_{\mathrm{cell}}(b, s)\bigr) &\to_{\mathrm{bin}, \mathcal{S}} \bigl(\mathrm{wing}(a, \mathrm{left}),\, \mathrm{bnd}(b, s)\bigr) &&\text{if }(\mathrm{skel}(a)[\mathrm{mark} \leftarrow \mathrm{left}],\, \mathrm{skel}(b)[\mathrm{mark} \leftarrow \mathrm{boundary}]) \in \mathcal{P}_{\mathrm{skel}}(q, 10), \\ \bigl(\mathrm{wing}(a, \mathrm{left}),\, \mathrm{full}(b, s, j, \mathrm{read\text{-}left}, r)\bigr) &\to_{\mathrm{bin}, \mathcal{S}} \bigl(\mathrm{full}(a, s, j, \mathrm{read\text{-}left}, r + \delta(a, j)),\, \mathrm{wing}(b, \mathrm{right})\bigr) &&\text{if }P_{\mathrm{fr}}(a, b), \\ \bigl(\mathrm{full}(a, s, j, \mathrm{read\text{-}right}, r),\, \mathrm{wing}(b, \mathrm{right})\bigr) &\to_{\mathrm{bin}, \mathcal{S}} \bigl(\mathrm{wing}(a, \mathrm{left}),\, \mathrm{full}(b, s, j, \mathrm{read\text{-}right}, r)\bigr) &&\text{if }P_{\mathrm{fr}}(a, b), \\ \bigl(\mathrm{wing}(a, \mathrm{left}),\, \mathrm{full}(b, s, j, \mathrm{undo\text{-}left}, r)\bigr) &\to_{\mathrm{bin}, \mathcal{S}} \bigl(\mathrm{full}(a, s, j, \mathrm{undo\text{-}left}, r),\, \mathrm{wing}(b, \mathrm{right})\bigr) &&\text{if }P_{\mathrm{fr}}(a, b), \\ \bigl(\mathrm{full}(a, s, j, \mathrm{undo\text{-}right}, r),\, \mathrm{wing}(b, \mathrm{right})\bigr) &\to_{\mathrm{bin}, \mathcal{S}} \bigl(\mathrm{wing}(a, \mathrm{left}),\, \mathrm{full}(b, s, j, \mathrm{undo\text{-}right}, r + \delta(a, j))\bigr) &&\text{if }P_{\mathrm{fr}}(a, b), \\ \bigl(a,\, b[\mathrm{chk} \leftarrow \mathrm{idle}]\bigr) &\to_{\mathrm{bin}, \mathcal{S}} \bigl(a,\, b[\mathrm{chk} \leftarrow \mathrm{head}(x)]\bigr) &&\text{if }\mathrm{pos}(a) = \mathrm{core}(p),\; p + 1 = q,\; b\text{ is a palette cell}, \\ \bigl(a[\mathrm{chk} \leftarrow \mathrm{head}(x)],\, b[\mathrm{chk} \leftarrow \mathrm{idle}]\bigr) &\to_{\mathrm{bin}, \mathcal{S}} \bigl(a[\mathrm{chk} \leftarrow \mathrm{passed}(x)],\, b[\mathrm{chk} \leftarrow \mathrm{head}(x)]\bigr) &&\text{if }\mathrm{pos}(a) = \mathrm{pal}(v),\; b\text{ is a palette cell},\; v \neq x, \\ (a, b) &\to_{\mathrm{bin}, \mathcal{S}} (b, a) &&\text{if }\mathrm{pos}(a) = \mathrm{pal}(x),\; \mathrm{pos}(b) = \mathrm{pal}(y),\; a[\mathrm{col} \leftarrow y] = b,\; a, b\text{ head-free}. \end{aligned}(4)

Two cell words v,wv, w of bound qq satisfy the cell-list replacement relation for (𝒮,d)(\mathcal{S}, d) if every cell appearing in vv or ww satisfies the cell formatting condition for (𝒮,d)(\mathcal{S}, d) and either v=(c1)v = (c_1) and w=(c2)w = (c_2) with c1→un,𝒮c2c_1 \to_{\mathrm{un}, \mathcal{S}} c_2 or c2→un,𝒮c1c_2 \to_{\mathrm{un}, \mathcal{S}} c_1, or v=(a1,b1)v = (a_1, b_1) and w=(a2,b2)w = (a_2, b_2) with (a1,b1)→bin,𝒮(a2,b2)(a_1, b_1) \to_{\mathrm{bin}, \mathcal{S}} (a_2, b_2) or (a2,b2)→bin,𝒮(a1,b1)(a_2, b_2) \to_{\mathrm{bin}, \mathcal{S}} (a_1, b_1).✦ A cell-word rewriting step v↔𝒮,dwv \leftrightarrow_{\mathcal{S}, d} w holds between cell words v,wv, w of bound qq if v=pu1sv = p u_1 s and w=pu2sw = p u_2 s for some cell words p,sp, s of bound qq and pair (u1,u2)(u_1, u_2) satisfying the cell-list replacement relation for (𝒮,d)(\mathcal{S}, d)✦, and the cell-word reachability relation ⇝𝒮,d\rightsquigarrow_{\mathcal{S}, d} on cell words of bound qq is the reflexive-transitive closure of ↔𝒮,d\leftrightarrow_{\mathcal{S}, d}.✦

A finite-table cell cc of bound qq is a semantic zero cell for 𝒮\mathcal{S} if mark(c)=full\mathrm{mark}(c) = \mathrm{full} and its head h=head(c)h = \mathrm{head}(c) satisfies one of three failure conditions: ph(h)∈{acquisition,finish,success}\mathrm{ph}(h) \in \{\mathrm{acquisition}, \mathrm{finish}, \mathrm{success}\} and reg(h)≠0\mathrm{reg}(h) \neq 0; ph(h)=after-gate\mathrm{ph}(h) = \mathrm{after\text{-}gate} and truthC𝒮(task(meta(c)),cl(h))(reg(h))=false\mathrm{truth}_{C_{\mathcal{S}}(\mathrm{task}(\mathrm{meta}(c)), \mathrm{cl}(h))}(\mathrm{reg}(h)) = \mathrm{false}; or ph(h)=success\mathrm{ph}(h) = \mathrm{success} and ζ(meta(c))=true\zeta(\mathrm{meta}(c)) = \mathrm{true}. A finite-table cell cc of bound qq is a unary zero cell for (𝒮,d)(\mathcal{S}, d) if cc fails the cell formatting condition for (𝒮,d)(\mathcal{S}, d), cc is a semantic zero cell for 𝒮\mathcal{S}, or pos(c)=pal(x)\mathrm{pos}(c) = \mathrm{pal}(x) and chk(c)=passed(x)\mathrm{chk}(c) = \mathrm{passed}(x) for some x∈{0,…,q−1}x \in \{0, \dots, q-1\}.✦ Two finite-table cells a,ba, b of bound qq form a binary zero pair (a,b)(a, b) if (a,b)(a, b) is not a compatible adjacent cell pair, pos(a)=pos(b)=pal(x)\mathrm{pos}(a) = \mathrm{pos}(b) = \mathrm{pal}(x) for some x∈{0,…,q−1}x \in \{0, \dots, q-1\}, or pos(a)=pal(x)\mathrm{pos}(a) = \mathrm{pal}(x), chk(a)=head(y)\mathrm{chk}(a) = \mathrm{head}(y), pos(b)=stop\mathrm{pos}(b) = \mathrm{stop}, and x≠yx \neq y.✦ The set 𝒵ft(𝒮,d)\mathcal{Z}_{\mathrm{ft}}(\mathcal{S}, d) of zero cell words for (𝒮,d)(\mathcal{S}, d) is the set of one-cell words (c)(c) where cc is a unary zero cell for (𝒮,d)(\mathcal{S}, d) and two-cell words (a,b)(a, b) where (a,b)(a, b) is a binary zero pair✦; a cell word ww of bound qq survives under (𝒮,d)(\mathcal{S}, d) if whenever w⇝𝒮,dpzsw \rightsquigarrow_{\mathcal{S}, d} p z s for cell words p,z,sp, z, s of bound qq, the factor zz does not belong to 𝒵ft(𝒮,d)\mathcal{Z}_{\mathrm{ft}}(\mathcal{S}, d).✦

For a cell word w=(c1,…,cm)w = (c_1, \dots, c_m) of bound qq, the idle-checker cell word idlechk(w)\mathrm{idle}_{\mathrm{chk}}(w) of ww is the cell word (c1[chk←idle],…,cm[chk←idle])(c_1[\mathrm{chk} \leftarrow \mathrm{idle}], \dots, c_m[\mathrm{chk} \leftarrow \mathrm{idle}]) of bound qq.✦ Given d∈ℕd \in \mathbb{N}, a vector u:{0,…,d−1}→𝔽2u : \{0, \dots, d-1\} \to \mathbb{F}_2, and a position p∈Posqp \in \mathrm{Pos}_q, the canonical cell canonq(u,p)\mathrm{canon}_q(u, p) is the finite-table cell of bound qq with skeleton (p,idle,m0)(p, \mathrm{idle}, m_0), checker state idle\mathrm{idle}, certificate bit 00, head state h0h_0, data bit data(canonq(u,p))(true)=0\mathrm{data}(\mathrm{canon}_q(u, p))(\mathrm{true}) = 0, and data bit data(canonq(u,p))(false)\mathrm{data}(\mathrm{canon}_q(u, p))(\mathrm{false}) equal to u(r)u(r) when p=core(r)p = \mathrm{core}(r) with r<dr < d and 00 otherwise.✦ Given d∈ℕd \in \mathbb{N}, a vector u:{0,…,d−1}→𝔽2u : \{0, \dots, d-1\} \to \mathbb{F}_2, and a finite list E=(x1,…,xm)E = (x_1, \dots, x_m) of colors in {0,…,q−1}\{0, \dots, q-1\}, the canonical palette word canonPalq(u,E)\mathrm{canonPal}_q(u, E) of EE for uu is the cell word (canonq(u,pal(x1)),…,canonq(u,pal(xm)))\bigl(\mathrm{canon}_q(u, \mathrm{pal}(x_1)), \dots, \mathrm{canon}_q(u, \mathrm{pal}(x_m))\bigr) of bound qq.

The Claim

Theorem 1. Let CC be a color set, AA an auxiliary state set, and HH a predicate on AA. If vv is a palette word over (C,A)(C, A) satisfying the palette syntax condition whose cells all have checker state idle\mathrm{idle} and whose color list cols(v)\mathrm{cols}(v) has pairwise distinct entries containing every element of CC, then every palette word ww over (C,A)(C, A) with v⇝Hwv \rightsquigarrow_H w satisfies (5): w∉𝒵pal(C,A).w \notin \mathcal{Z}_{\mathrm{pal}}(C, A).(5)✦ For any palette word ww over (C,A)(C, A) satisfying the palette syntax condition, (6) holds: w∈𝒵pal(C,A)orw⇝Hidlepal(w).w \in \mathcal{Z}_{\mathrm{pal}}(C, A) \quad \text{or} \quad w \rightsquigarrow_H \mathrm{idle}_{\mathrm{pal}}(w).(6)✦ Every nonempty palette word ww over (C,A)(C, A) that survives under HH and has checker state idle\mathrm{idle} on every cell satisfies (7): ∀x∈C,x∈cols(w).\forall x \in C,\; x \in \mathrm{cols}(w).(7)✦ When α∈A\alpha \in A satisfies ¬H(α)\neg H(\alpha) and w=(a1,…,am)w = (a_1, \dots, a_m) is a palette word over (C,A)(C, A) surviving under HH with chk(ai)=idle\mathrm{chk}(a_i) = \mathrm{idle} and aux(ai)=α\mathrm{aux}(a_i) = \alpha for all 1≤i≤m1 \le i \le m, condition (8) holds: col(ai)≠col(aj)for all 1≤i<j≤m.\mathrm{col}(a_i) \neq \mathrm{col}(a_j) \quad \text{for all } 1 \le i < j \le m.(8)✦ Under the hypotheses of (8), if ww is also nonempty and E=(x1,…,xr)E = (x_1, \dots, x_r) is a finite list of pairwise distinct elements of CC containing every element of CC, then (9) holds: w⇝H((x1,idle,α),…,(xr,idle,α)).w \rightsquigarrow_H \bigl((x_1, \mathrm{idle}, \alpha), \dots, (x_r, \mathrm{idle}, \alpha)\bigr).(9)✦

Fix an integer bound q≥1q \ge 1, a verification clause schedule 𝒮\mathcal{S} of bound qq, and a data size d∈ℕd \in \mathbb{N}. Suppose cc and zz are finite-table cells of bound qq with pos(c)=core(t)\mathrm{pos}(c) = \mathrm{core}(t) for some t∈{0,…,q−1}t \in \{0, \dots, q-1\} satisfying t+1=qt + 1 = q and pos(z)=stop\mathrm{pos}(z) = \mathrm{stop}, and suppose ww is a word of palette cells of bound qq such that cwzc w z survives under (𝒮,d)(\mathcal{S}, d); then (10) holds: cwz⇝𝒮,dcidlechk(w)z.c w z \rightsquigarrow_{\mathcal{S}, d} c\, \mathrm{idle}_{\mathrm{chk}}(w)\, z.(10)✦ If, in addition to the hypotheses of (10), ww is nonempty, then (11) holds: ∀x∈{0,…,q−1},x∈cols(w).\forall x \in \{0, \dots, q-1\},\; x \in \mathrm{cols}(w).(11)✦ Whenever cc, zz, and ww satisfy the hypotheses of (11) and every cell of ww has marker idle\mathrm{idle} and checker state idle\mathrm{idle}, for every vector u:{0,…,d−1}→𝔽2u : \{0, \dots, d-1\} \to \mathbb{F}_2 condition (12) holds: |w|=qandw⇝𝒮,dcanonPalq(u,(0,1,…,q−1)).|w| = q \quad \text{and} \quad w \rightsquigarrow_{\mathcal{S}, d} \mathrm{canonPal}_q(u, (0, 1, \dots, q-1)).(12)✦ If w=(a1,…,am)w = (a_1, \dots, a_m) is any word of palette cells of bound qq that survives under (𝒮,d)(\mathcal{S}, d) and satisfies erase(ai)=erase(aj)\mathrm{erase}(a_i) = \mathrm{erase}(a_j) for all 1≤i,j≤m1 \le i, j \le m, then (13) holds: col(ai)≠col(aj)for all 1≤i<j≤m.\mathrm{col}(a_i) \neq \mathrm{col}(a_j) \quad \text{for all } 1 \le i < j \le m.(13)✦

In the paper, the result reads: a complete palette containing each color exactly once, initially idle on its checker track, cannot reach a palette zero under palette operations arbitrarily interleaved with transaction operations; conversely, if a palette together with its preceding core cell at core(q−1)\mathrm{core}(q-1) (the paper’s C(qh)C(q_h), with qq standing for qhq_h) and following stop cell at stop\mathrm{stop} (the paper’s SS) occurs in a nonzero word, its checker can be removed by replacements supported on those cells, and once its transaction track is also idle, the palette has each color once and can be sorted into increasing color order. Parts (5) through (9) isolate the abstract palette invariants with the auxiliary state set AA and predicate HH representing interleaved transaction moves, while parts (10) through (13) formulate the finite-table invariants for surviving cell words with idle markers representing an idle transaction track.

What Is Checked

The abstract claims (5) through (9) are stated over palette words in an arbitrary color set CC and auxiliary state set AA equipped with a head predicate HH under the palette syntax, idle-checker, zero-word, reachability, and survival conditions, while the finite-table claims (10) through (13) are stated over cell words of positive bound qq relative to a verification clause schedule 𝒮\mathcal{S} and data size dd under the cell projections, color-erasure, idle-checker, and canonical-palette maps and the cell-word reachability and survival relations built from block syntactic skeletons, cell formatting, unary and binary transitions, and zero patterns.