OctoInformBeta

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

Lemma 2.6: Tour plans roll back or hit a bad state; active syntactic components release to idle or hit zero, and surviving ones unlock

Rollback and release of active cell components.

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 finite-table cells governed by symmetric local rewriting rules of length one and two, together with local zero patterns that mark degenerate configurations. Inside such a word, an active transaction spans a cut-free connected component containing either a full reading head executing a sequence of verification clauses or a boundary cursor at the edge of an acquired prefix. Can every complete transaction region carrying one full head in a valid control state be rolled back to its acquisition state and released to an idle word or else hit a zero cell, and can every boundary-cursor region be released within its acquired interval so that surviving active components unlock completely?

Local Syntax and Palette Checkers

Fix integers q,k≥0q, k \ge 0. A cell marker mm is an element of the five-element set ℳ={idle,left,boundary,full,right}\mathcal{M} = \{\mathrm{idle}, \mathrm{left}, \mathrm{boundary}, \mathrm{full}, \mathrm{right}\}. A block metadata record of arity bound kk is a triple m=(α,z,β)∈Metakm = (\alpha, z, \beta) \in \mathrm{Meta}_k consisting of an arity integer 0≤α<k0 \le \alpha < k, a Boolean zero-task flag z∈{false,true}z \in \{\mathrm{false}, \mathrm{true}\}, and a block index 0≤β≤α0 \le \beta \le \alpha.✦ A block cell position π\pi of bound qq is an element of Pos(q)={core(p):0≤p<q}∪{palette(x):0≤x<q}∪{stop}\mathrm{Pos}(q) = \{\mathrm{core}(p) : 0 \le p < q\} \cup \{\mathrm{palette}(x) : 0 \le x < q\} \cup \{\mathrm{stop}\}. A cell syntactic skeleton cc of parameters (q,k)(q, k) is a triple (p,m,μ)∈Skel(q,k)=Pos(q)×ℳ×Metak(p, m, \mu) \in \mathrm{Skel}(q, k) = \mathrm{Pos}(q) \times \mathcal{M} \times \mathrm{Meta}_k, whose components are written pos(c),mark(c),meta(c)\mathrm{pos}(c), \mathrm{mark}(c), \mathrm{meta}(c). For a skeleton c∈Skel(q,k)c \in \mathrm{Skel}(q, k) and a cell marker m∈ℳm \in \mathcal{M}, the marker update mark(c,m)∈Skel(q,k)\mathrm{mark}(c, m) \in \mathrm{Skel}(q, k) of cc by mm is the skeleton (pos(c),m,meta(c))(\mathrm{pos}(c), m, \mathrm{meta}(c)).✦

A skeleton c∈Skel(q,k)c \in \mathrm{Skel}(q, k) is initial if β(meta(c))=0\beta(\mathrm{meta}(c)) = 0 and pos(c)=core(0)\mathrm{pos}(c) = \mathrm{core}(0), and terminal if β(meta(c))=α(meta(c))\beta(\mathrm{meta}(c)) = \alpha(\mathrm{meta}(c)) and pos(c)=stop\mathrm{pos}(c) = \mathrm{stop}. A skeleton c∈Skel(q,k)c \in \mathrm{Skel}(q, k) carries an active head marker if mark(c)∈{boundary,full}\mathrm{mark}(c) \in \{\mathrm{boundary}, \mathrm{full}\}.✦ A skeleton c∈Skel(q,k)c \in \mathrm{Skel}(q, k) is admissible if mark(c)=right\mathrm{mark}(c) = \mathrm{right} implies cc is not initial and mark(c)=left\mathrm{mark}(c) = \mathrm{left} implies cc is not terminal.✦ A skeleton c∈Skel(q,k)c \in \mathrm{Skel}(q, k) is left-external if mark(c)=idle\mathrm{mark}(c) = \mathrm{idle} or both mark(c)≠right\mathrm{mark}(c) \neq \mathrm{right} and cc is initial, and right-external if mark(c)∈{idle,boundary}\mathrm{mark}(c) \in \{\mathrm{idle}, \mathrm{boundary}\} or both mark(c)≠left\mathrm{mark}(c) \neq \mathrm{left} and cc is terminal.

Two skeletons a,b∈Skel(q,k)a, b \in \mathrm{Skel}(q, k) are structurally adjacent, written struct(a,b)\mathrm{struct}(a, b), when one of four position relations holds: pos(a)=core(p)\mathrm{pos}(a) = \mathrm{core}(p) and pos(b)=core(p+1)\mathrm{pos}(b) = \mathrm{core}(p + 1); pos(a)=core(p)\mathrm{pos}(a) = \mathrm{core}(p) with p+1=qp + 1 = q and pos(b)=palette(x)\mathrm{pos}(b) = \mathrm{palette}(x); pos(a)=palette(x)\mathrm{pos}(a) = \mathrm{palette}(x) and pos(b)\mathrm{pos}(b) is either palette(y)\mathrm{palette}(y) or stop\mathrm{stop}; or pos(a)=stop\mathrm{pos}(a) = \mathrm{stop} and pos(b)=core(0)\mathrm{pos}(b) = \mathrm{core}(0).✦ Two skeletons a,b∈Skel(q,k)a, b \in \mathrm{Skel}(q, k) satisfy internal skeleton consistency, written int(a,b)\mathrm{int}(a, b), when meta(a)\mathrm{meta}(a) and meta(b)\mathrm{meta}(b) share the same arity and zero-task flag, β(meta(b))=β(meta(a))+1\beta(\mathrm{meta}(b)) = \beta(\mathrm{meta}(a)) + 1 if pos(a)=stop\mathrm{pos}(a) = \mathrm{stop} and β(meta(b))=β(meta(a))\beta(\mathrm{meta}(b)) = \beta(\mathrm{meta}(a)) otherwise, bb is not initial, and aa is not terminal.✦

A skeleton c∈Skel(q,k)c \in \mathrm{Skel}(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(c)=right\mathrm{mark}(c) = \mathrm{right} and m=leftm = \mathrm{left} otherwise✦; likewise, c∈Skel(q,k)c \in \mathrm{Skel}(q, k) accepts mm on the right if m∈{left,boundary,full}m \in \{\mathrm{left}, \mathrm{boundary}, \mathrm{full}\} when mark(c)=left\mathrm{mark}(c) = \mathrm{left} and m=rightm = \mathrm{right} otherwise.✦ Two skeletons a,b∈Skel(q,k)a, b \in \mathrm{Skel}(q, k) form a compatible adjacent skeleton pair, written pairskel(a,b)\mathrm{pair}_{\mathrm{skel}}(a, b), if struct(a,b)\mathrm{struct}(a, b) holds and either aa is right-external and bb is left-external, or aa is not right-external, bb is not left-external, aa accepts mark(b)\mathrm{mark}(b) on the right, bb accepts mark(a)\mathrm{mark}(a) on the left, and int(a,b)\mathrm{int}(a, b) holds.✦ Adjoining a blank boundary symbol ⊥\bot to Skel(q,k)\mathrm{Skel}(q, k), the skeleton link relation on Skel(q,k)∪{⊥}\mathrm{Skel}(q, k) \cup \{\bot\} holds for (⊥,⊥)(\bot, \bot), for (⊥,b)(\bot, b) with b∈Skel(q,k)b \in \mathrm{Skel}(q, k) when bb is left-external, for (a,⊥)(a, \bot) with a∈Skel(q,k)a \in \mathrm{Skel}(q, k) when aa is right-external, and for (a,b)(a, b) with a,b∈Skel(q,k)a, b \in \mathrm{Skel}(q, k) when pairskel(a,b)\mathrm{pair}_{\mathrm{skel}}(a, b) holds.✦ A finite sequence (c0,…,cn−1)(c_0, \dots, c_{n-1}) of skeletons in Skel(q,k)\mathrm{Skel}(q, k) is closed if every cic_i is admissible and every consecutive pair in (⊥,c0,…,cn−1,⊥)(\bot, c_0, \dots, c_{n-1}, \bot) satisfies the skeleton link relation.✦

For any color set CC, a palette checker state χ\chi over CC is an element of Check(C)={idle}∪{passed(x),head(x):x∈C}\mathrm{Check}(C) = \{\mathrm{idle}\} \cup \{\mathrm{passed}(x), \mathrm{head}(x) : x \in C\}. A checker state χ∈Check(C)\chi \in \mathrm{Check}(C) satisfies the terminal palette checker condition if χ=idle\chi = \mathrm{idle} or χ=head(x)\chi = \mathrm{head}(x) for some x∈Cx \in C.✦ Two adjacent checker states (χ1,χ2)(\chi_1, \chi_2) in Check(C)\mathrm{Check}(C) form a compatible palette checker pair if (χ1,χ2)(\chi_1, \chi_2) equals (idle,idle)(\mathrm{idle}, \mathrm{idle}), (passed(x),passed(x))(\mathrm{passed}(x), \mathrm{passed}(x)), (passed(x),head(x))(\mathrm{passed}(x), \mathrm{head}(x)), or (head(x),idle)(\mathrm{head}(x), \mathrm{idle}) for some x∈Cx \in C.✦

Finite-table Cells and Local Rewriting

Fix a positive integer q≥1q \ge 1 and arity bound k=10k = 10, and set Meta=Meta10\mathrm{Meta} = \mathrm{Meta}_{10}.✦ A cell memory address in Addr(q)\mathrm{Addr}(q) is either a data address data(σ,β,p)\mathrm{data}(\sigma, \beta, p) with σ∈{false,true}\sigma \in \{\mathrm{false}, \mathrm{true}\}, β∈{0,…,9}\beta \in \{0, \dots, 9\}, and 0≤p<q0 \le p < q, or a certificate address cert(p)\mathrm{cert}(p) with 0≤p<q0 \le p < q.✦ A three-bit register state is a vector r∈𝔽23r \in \mathbb{F}_2^3.✦ A verification clause CC of bound qq consists of three addresses (u0,u1,u2)∈Addr(q)3(u_0, u_1, u_2) \in \mathrm{Addr}(q)^3 and a truth function τC:𝔽23→{false,true}\tau_C : \mathbb{F}_2^3 \to \{\mathrm{false}, \mathrm{true}\}.✦ A verification task tt is a pair (α,z)(\alpha, z) consisting of an arity α∈{0,…,9}\alpha \in \{0, \dots, 9\} and a Boolean zero-task flag zz; the task projection task(m)\mathrm{task}(m) of a metadata record m=(α,z,β)∈Metam = (\alpha, z, \beta) \in \mathrm{Meta} is the verification task (α,z)(\alpha, z). A verification clause schedule SS of bound qq assigns to each verification task tt a positive clause count 1≤mS(t)≤q1 \le m_S(t) \le q and verification clauses CS(t,j)C_S(t, j) for 0≤j<q0 \le j < q.✦

A head computation phase ϕ\phi belongs to the nine-element set Φ={acq,rl,rr,bg,ag,ul,ur,fin,succ}\Phi = \{\mathrm{acq}, \mathrm{rl}, \mathrm{rr}, \mathrm{bg}, \mathrm{ag}, \mathrm{ul}, \mathrm{ur}, \mathrm{fin}, \mathrm{succ}\}, standing respectively for acquisition, read-left, read-right, before-gate, after-gate, undo-left, undo-right, finish, and success. An endpoint phase ϕ∈Φ\phi \in \Phi is a computation phase belonging to ℰ={acq,bg,ag,fin,succ}\mathcal{E} = \{\mathrm{acq}, \mathrm{bg}, \mathrm{ag}, \mathrm{fin}, \mathrm{succ}\}. A reading head state h∈Head(q)h \in \mathrm{Head}(q) is a quadruple (σ,j,ϕ,r)∈{false,true}×{0,…,q−1}×Φ×𝔽23(\sigma, j, \phi, r) \in \{\mathrm{false}, \mathrm{true}\} \times \{0, \dots, q - 1\} \times \Phi \times \mathbb{F}_2^3, whose components are written σ(h),j(h),ϕ(h),r(h)\sigma(h), j(h), \phi(h), r(h). The default head state is head0=(false,0,acq,0)\mathrm{head}_0 = (\mathrm{false}, 0, \mathrm{acq}, 0), and the default cell metadata is meta0=(0,false,0)∈Meta\mathrm{meta}_0 = (0, \mathrm{false}, 0) \in \mathrm{Meta}.

A finite-table cell c∈Cell(q)c \in \mathrm{Cell}(q) consists of a skeleton skel(c)∈Skel(q,10)\mathrm{skel}(c) \in \mathrm{Skel}(q, 10), a palette checker state chk(c)∈Check({0,…,q−1})\mathrm{chk}(c) \in \mathrm{Check}(\{0, \dots, q - 1\}), a side-indexed 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)∈Head(q)\mathrm{head}(c) \in \mathrm{Head}(q).✦ Write pos(c)\mathrm{pos}(c), mark(c)\mathrm{mark}(c), meta(c)\mathrm{meta}(c) for the components of skel(c)\mathrm{skel}(c), and set task(c)=task(meta(c))\mathrm{task}(c) = \mathrm{task}(\mathrm{meta}(c)). A cell c∈Cell(q)c \in \mathrm{Cell}(q) is in the core if pos(c)=core(p)\mathrm{pos}(c) = \mathrm{core}(p) for some 0≤p<q0 \le p < q, in the palette if pos(c)=palette(x)\mathrm{pos}(c) = \mathrm{palette}(x) for some 0≤x<q0 \le x < q, and 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 0≤x<q0 \le x < q.

Given c∈Cell(q)c \in \mathrm{Cell}(q) and σ∈{false,true}\sigma \in \{\mathrm{false}, \mathrm{true}\}, the idle cell idle(c,σ)\mathrm{idle}(c, \sigma) preserves pos(c)\mathrm{pos}(c), sets the marker to idle\mathrm{idle}, metadata to meta0\mathrm{meta}_0, certificate bit to 00, head to head0\mathrm{head}_0, and data at each side t∈{false,true}t \in \{\mathrm{false}, \mathrm{true}\} to 00 if t=truet = \mathrm{true} and to data(c)(σ)\mathrm{data}(c)(\sigma) if t=falset = \mathrm{false}.✦ The boundary cell bnd(c,σ)\mathrm{bnd}(c, \sigma) replaces skel(c)\mathrm{skel}(c) with mark(skel(c),boundary)\mathrm{mark}(\mathrm{skel}(c), \mathrm{boundary}) and sets the head to (σ,0,acq,0)(\sigma, 0, \mathrm{acq}, 0); the wing cell wing(c,m)\mathrm{wing}(c, m) for m∈ℳm \in \mathcal{M} marks skel(c)\mathrm{skel}(c) with mm and resets the head to head0\mathrm{head}_0; and the full cell full(c,σ,j,ϕ,r)\mathrm{full}(c, \sigma, j, \phi, r) for 0≤j<q0 \le j < q, ϕ∈Φ\phi \in \Phi, and r∈𝔽23r \in \mathbb{F}_2^3 marks skel(c)\mathrm{skel}(c) with full\mathrm{full} and sets the head to (σ,j,ϕ,r)(\sigma, j, \phi, r). For a cell c∈Cell(q)c \in \mathrm{Cell}(q), a checker state χ∈Check({0,…,q−1})\chi \in \mathrm{Check}(\{0, \dots, q - 1\}), and a color index 0≤x<q0 \le x < q, the checker update updchk(c,χ)\mathrm{upd}_{\mathrm{chk}}(c, \chi) is the cell obtained from cc by replacing chk(c)\mathrm{chk}(c) with χ\chi, and the color update updcol(c,x)\mathrm{upd}_{\mathrm{col}}(c, x) is the cell obtained from cc by replacing pos(c)\mathrm{pos}(c) with palette(x)\mathrm{palette}(x). For an address a∈Addr(q)a \in \mathrm{Addr}(q) and a cell c∈Cell(q)c \in \mathrm{Cell}(q), the address value read(a,c)∈𝔽2\mathrm{read}(a, c) \in \mathbb{F}_2 is equal to data(c)(σ)\mathrm{data}(c)(\sigma) if a=data(σ,β,p)a = \mathrm{data}(\sigma, \beta, p) and pos(c)=core(p)\mathrm{pos}(c) = \mathrm{core}(p) with β(meta(c))=β\beta(\mathrm{meta}(c)) = \beta, equal to cert(c)\mathrm{cert}(c) if a=cert(p)a = \mathrm{cert}(p) and pos(c)=core(p)\mathrm{pos}(c) = \mathrm{core}(p) with β(meta(c))=0\beta(\mathrm{meta}(c)) = 0, and 00 otherwise.✦ For a verification clause C=((u0,u1,u2),τC)C = ((u_0, u_1, u_2), \tau_C) and c∈Cell(q)c \in \mathrm{Cell}(q), the clause register delta δC(c)∈𝔽23\delta_C(c) \in \mathbb{F}_2^3 has ii-th coordinate read(ui,c)\mathrm{read}(u_i, c) for i∈{0,1,2}i \in \{0, 1, 2\}.✦

For a data size d≥0d \ge 0, a cell c∈Cell(q)c \in \mathrm{Cell}(q) satisfies the cell payload format condition pfmtd(c)\mathrm{pfmt}_d(c) if chk(c)=idle\mathrm{chk}(c) = \mathrm{idle} whenever cc is not in the palette, data(c)=0\mathrm{data}(c) = 0 whenever pos(c)=core(p)\mathrm{pos}(c) = \mathrm{core}(p) with p≥dp \ge d, and data(c)=0\mathrm{data}(c) = 0 and cert(c)=0\mathrm{cert}(c) = 0 whenever cc is not in the core.✦ Given a schedule SS and data size d≥0d \ge 0, a cell c∈Cell(q)c \in \mathrm{Cell}(q) satisfies the cell formatting condition fmtS,d(c)\mathrm{fmt}_{S, d}(c) if skel(c)\mathrm{skel}(c) is admissible, pfmtd(c)\mathrm{pfmt}_d(c) holds, and five marker conditions hold: mark(c)=idle\mathrm{mark}(c) = \mathrm{idle} forces meta(c)=meta0\mathrm{meta}(c) = \mathrm{meta}_0, head(c)=head0\mathrm{head}(c) = \mathrm{head}_0, data(c)(true)=0\mathrm{data}(c)(\mathrm{true}) = 0, and cert(c)=0\mathrm{cert}(c) = 0; mark(c)∈{left,right}\mathrm{mark}(c) \in \{\mathrm{left}, \mathrm{right}\} forces head(c)=head0\mathrm{head}(c) = \mathrm{head}_0; mark(c)=boundary\mathrm{mark}(c) = \mathrm{boundary} forces j(head(c))=0j(\mathrm{head}(c)) = 0, ϕ(head(c))=acq\phi(\mathrm{head}(c)) = \mathrm{acq}, and r(head(c))=0r(\mathrm{head}(c)) = 0; an active head marker with z(meta(c))=truez(\mathrm{meta}(c)) = \mathrm{true} forces σ(head(c))=false\sigma(\mathrm{head}(c)) = \mathrm{false}; and mark(c)=full\mathrm{mark}(c) = \mathrm{full} forces j(head(c))=0j(\mathrm{head}(c)) = 0 when ϕ(head(c))=succ\phi(\mathrm{head}(c)) = \mathrm{succ}, j(head(c))<mS(task(c))j(\mathrm{head}(c)) < m_S(\mathrm{task}(c)) when ϕ(head(c))≠succ\phi(\mathrm{head}(c)) \neq \mathrm{succ}, and skel(c)\mathrm{skel}(c) terminal whenever ϕ(head(c))∈ℰ\phi(\mathrm{head}(c)) \in \mathcal{E}.✦

Two cells a,b∈Cell(q)a, b \in \mathrm{Cell}(q) satisfy checker compatibility if (chk(a),chk(b))(\mathrm{chk}(a), \mathrm{chk}(b)) is a compatible palette checker pair whenever both aa and bb are in the palette, and chk(a)\mathrm{chk}(a) satisfies the terminal palette checker condition whenever aa is in the palette and pos(b)=stop\mathrm{pos}(b) = \mathrm{stop}.✦ Two cells a,b∈Cell(q)a, b \in \mathrm{Cell}(q) form a compatible adjacent cell pair, written pair(a,b)\mathrm{pair}(a, b), if pairskel(skel(a),skel(b))\mathrm{pair}_{\mathrm{skel}}(\mathrm{skel}(a), \mathrm{skel}(b)) and checker compatibility hold.✦ For finite words u,vu, v over Cell(q)\mathrm{Cell}(q), write uvu v for concatenation and [c][c] for the one-cell word consisting of cc. A cell word w=[c0]⋯[cn−1]w = [c_0] \cdots [c_{n-1}] satisfies the cell word syntax synS,d(w)\mathrm{syn}_{S, d}(w) if its sequence of skeletons (skel(c0),…,skel(cn−1))(\mathrm{skel}(c_0), \dots, \mathrm{skel}(c_{n-1})) is closed, every consecutive pair of cells in ww satisfies checker compatibility, and every cell cc in ww satisfies fmtS,d(c)\mathrm{fmt}_{S, d}(c).✦ For a sequence f:{0,…,N−1}→Cell(q)f : \{0, \dots, N - 1\} \to \mathrm{Cell}(q), write w(f)w(f) for the length-NN word whose ii-th cell is f(i)f(i). The number of locked cells locked(w)\mathrm{locked}(w) in a cell word ww is the count of cells in ww whose marker is not idle\mathrm{idle}.✦

Given a schedule SS, the unary cell transition c1→S1c2c_1 \to_S^1 c_2 on Cell(q)\mathrm{Cell}(q) holds across the twelve boundary rules in (1), where c∈Cell(q)c \in \mathrm{Cell}(q), σ∈{false,true}\sigma \in \{\mathrm{false}, \mathrm{true}\}, 0≤j<q0 \le j < q, and r∈𝔽23r \in \mathbb{F}_2^3: idle(c,σ)→S1bnd(c,σ)if skel(c) is initial,bnd(c,σ)→S1full(c,σ,0,acq,0)if skel(c) is terminal,full(c,σ,j,acq,r)→S1full(c,σ,j,rl,r)if skel(c) is terminal,full(c,σ,j,rl,r)→S1full(c,σ,j,rr,r)if skel(c) is initial,full(c,σ,j,rr,r)→S1full(c,σ,j,bg,r)if skel(c) is terminal,full(c,σ,j,bg,r)→S1full(c,σ,j,ag,r)if skel(c) is terminal and τCS(task(c),j)(r)=true,full(c,σ,j,ag,r)→S1full(c,σ,j,ul,r)if skel(c) is terminal,full(c,σ,j,ul,r)→S1full(c,σ,j,ur,r)if skel(c) is initial,full(c,σ,j,ur,r)→S1full(c,σ,j,fin,r)if skel(c) is terminal,full(c,σ,j,fin,0)→S1full(c,σ,j+1,acq,0)if skel(c) is terminal and j+1<q,full(c,σ,j,fin,0)→S1full(c,σ,0,succ,0)if skel(c) is terminal and j+1=mS(task(c)),full(c,σ,0,succ,0)→S1full(c,¬σ,0,succ,0)if skel(c) is terminal and z(meta(c))=false.\begin{aligned} \mathrm{idle}(c, \sigma) &\to_S^1 \mathrm{bnd}(c, \sigma) && \text{if } \mathrm{skel}(c) \text{ is initial}, \\ \mathrm{bnd}(c, \sigma) &\to_S^1 \mathrm{full}(c, \sigma, 0, \mathrm{acq}, 0) && \text{if } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, \sigma, j, \mathrm{acq}, r) &\to_S^1 \mathrm{full}(c, \sigma, j, \mathrm{rl}, r) && \text{if } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, \sigma, j, \mathrm{rl}, r) &\to_S^1 \mathrm{full}(c, \sigma, j, \mathrm{rr}, r) && \text{if } \mathrm{skel}(c) \text{ is initial}, \\ \mathrm{full}(c, \sigma, j, \mathrm{rr}, r) &\to_S^1 \mathrm{full}(c, \sigma, j, \mathrm{bg}, r) && \text{if } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, \sigma, j, \mathrm{bg}, r) &\to_S^1 \mathrm{full}(c, \sigma, j, \mathrm{ag}, r) && \text{if } \mathrm{skel}(c) \text{ is terminal and } \tau_{C_S(\mathrm{task}(c), j)}(r) = \mathrm{true}, \\ \mathrm{full}(c, \sigma, j, \mathrm{ag}, r) &\to_S^1 \mathrm{full}(c, \sigma, j, \mathrm{ul}, r) && \text{if } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, \sigma, j, \mathrm{ul}, r) &\to_S^1 \mathrm{full}(c, \sigma, j, \mathrm{ur}, r) && \text{if } \mathrm{skel}(c) \text{ is initial}, \\ \mathrm{full}(c, \sigma, j, \mathrm{ur}, r) &\to_S^1 \mathrm{full}(c, \sigma, j, \mathrm{fin}, r) && \text{if } \mathrm{skel}(c) \text{ is terminal}, \\ \mathrm{full}(c, \sigma, j, \mathrm{fin}, 0) &\to_S^1 \mathrm{full}(c, \sigma, j + 1, \mathrm{acq}, 0) && \text{if } \mathrm{skel}(c) \text{ is terminal and } j + 1 < q, \\ \mathrm{full}(c, \sigma, j, \mathrm{fin}, 0) &\to_S^1 \mathrm{full}(c, \sigma, 0, \mathrm{succ}, 0) && \text{if } \mathrm{skel}(c) \text{ is terminal and } j + 1 = m_S(\mathrm{task}(c)), \\ \mathrm{full}(c, \sigma, 0, \mathrm{succ}, 0) &\to_S^1 \mathrm{full}(c, \neg \sigma, 0, \mathrm{succ}, 0) && \text{if } \mathrm{skel}(c) \text{ is terminal and } z(\mathrm{meta}(c)) = \mathrm{false}. \end{aligned}(1)✦ Writing ΔS(a,j)=δCS(task(a),j)(a)\Delta_S(a, j) = \delta_{C_S(\mathrm{task}(a), j)}(a), the binary cell transition (a1,b1)→S2(a2,b2)(a_1, b_1) \to_S^2 (a_2, b_2) relates adjacent cells in Cell(q)\mathrm{Cell}(q) across the eight rules in (2) (for a,b∈Cell(q)a, b \in \mathrm{Cell}(q), σ∈{false,true}\sigma \in \{\mathrm{false}, \mathrm{true}\}, 0≤j,x,y,v<q0 \le j, x, y, v < q, and r∈𝔽23r \in \mathbb{F}_2^3): (bnd(a,σ),idle(b,σ))→S2(wing(a,left),bnd(b,σ))if pairskel(mark(skel(a),left),mark(skel(b),boundary)),(wing(a,left),full(b,σ,j,rl,r))→S2(full(a,σ,j,rl,r+ΔS(a,j)),wing(b,right))if pairskel(mark(skel(a),full),mark(skel(b),right)),(full(a,σ,j,rr,r),wing(b,right))→S2(wing(a,left),full(b,σ,j,rr,r))if pairskel(mark(skel(a),full),mark(skel(b),right)),(wing(a,left),full(b,σ,j,ul,r))→S2(full(a,σ,j,ul,r),wing(b,right))if pairskel(mark(skel(a),full),mark(skel(b),right)),(full(a,σ,j,ur,r),wing(b,right))→S2(wing(a,left),full(b,σ,j,ur,r+ΔS(a,j)))if pairskel(mark(skel(a),full),mark(skel(b),right)),(a,updchk(b,idle))→S2(a,updchk(b,head(x)))if pos(a)=core(q−1) and b is in the palette,(updchk(a,head(x)),updchk(b,idle))→S2(updchk(a,passed(x)),updchk(b,head(x)))if pos(a)=palette(v) with v≠x and b is in the palette,(a,b)→S2(b,a)if pos(a)=palette(x),pos(b)=palette(y),updcol(a,y)=b, and a,b are head-free.\begin{aligned} (\mathrm{bnd}(a, \sigma), \mathrm{idle}(b, \sigma)) &\to_S^2 (\mathrm{wing}(a, \mathrm{left}), \mathrm{bnd}(b, \sigma)) \\ &\quad \text{if } \mathrm{pair}_{\mathrm{skel}}\bigl( \mathrm{mark}(\mathrm{skel}(a), \mathrm{left}), \mathrm{mark}(\mathrm{skel}(b), \mathrm{boundary})\bigr), \\ (\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, \sigma, j, \mathrm{rl}, r)) &\to_S^2 (\mathrm{full}(a, \sigma, j, \mathrm{rl}, r + \Delta_S(a, j)), \mathrm{wing}(b, \mathrm{right})) \\ &\quad \text{if } \mathrm{pair}_{\mathrm{skel}}\bigl( \mathrm{mark}(\mathrm{skel}(a), \mathrm{full}), \mathrm{mark}(\mathrm{skel}(b), \mathrm{right})\bigr), \\ (\mathrm{full}(a, \sigma, j, \mathrm{rr}, r), \mathrm{wing}(b, \mathrm{right})) &\to_S^2 (\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, \sigma, j, \mathrm{rr}, r)) \\ &\quad \text{if } \mathrm{pair}_{\mathrm{skel}}\bigl( \mathrm{mark}(\mathrm{skel}(a), \mathrm{full}), \mathrm{mark}(\mathrm{skel}(b), \mathrm{right})\bigr), \\ (\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, \sigma, j, \mathrm{ul}, r)) &\to_S^2 (\mathrm{full}(a, \sigma, j, \mathrm{ul}, r), \mathrm{wing}(b, \mathrm{right})) \\ &\quad \text{if } \mathrm{pair}_{\mathrm{skel}}\bigl( \mathrm{mark}(\mathrm{skel}(a), \mathrm{full}), \mathrm{mark}(\mathrm{skel}(b), \mathrm{right})\bigr), \\ (\mathrm{full}(a, \sigma, j, \mathrm{ur}, r), \mathrm{wing}(b, \mathrm{right})) &\to_S^2 (\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, \sigma, j, \mathrm{ur}, r + \Delta_S(a, j))) \\ &\quad \text{if } \mathrm{pair}_{\mathrm{skel}}\bigl( \mathrm{mark}(\mathrm{skel}(a), \mathrm{full}), \mathrm{mark}(\mathrm{skel}(b), \mathrm{right})\bigr), \\ (a, \mathrm{upd}_{\mathrm{chk}}(b, \mathrm{idle})) &\to_S^2 (a, \mathrm{upd}_{\mathrm{chk}}(b, \mathrm{head}(x))) \\ &\quad \text{if } \mathrm{pos}(a) = \mathrm{core}(q - 1) \text{ and } b \text{ is in the palette}, \\ (\mathrm{upd}_{\mathrm{chk}}(a, \mathrm{head}(x)), \mathrm{upd}_{\mathrm{chk}}(b, \mathrm{idle})) &\to_S^2 (\mathrm{upd}_{\mathrm{chk}}(a, \mathrm{passed}(x)), \mathrm{upd}_{\mathrm{chk}}(b, \mathrm{head}(x))) \\ &\quad \text{if } \mathrm{pos}(a) = \mathrm{palette}(v) \text{ with } v \neq x \text{ and } b \text{ is in the palette}, \\ (a, b) &\to_S^2 (b, a) \\ &\quad \text{if } \mathrm{pos}(a) = \mathrm{palette}(x),\; \mathrm{pos}(b) = \mathrm{palette}(y),\; \mathrm{upd}_{\mathrm{col}}(a, y) = b, \text{ and } a, b \text{ are head-free}. \end{aligned}(2)✦

For a schedule SS and data size d≥0d \ge 0, two cell words u,u′u, u' satisfy the cell list replacement relation if every cell in uu and u′u' satisfies fmtS,d\mathrm{fmt}_{S, d} and either u=[a],u′=[b]u = [a], u' = [b] with a→S1ba \to_S^1 b or b→S1ab \to_S^1 a, or u=[a,b],u′=[a′,b′]u = [a, b], u' = [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). Two cell words v,wv, w are related by a cell word rewriting step under (S,d)(S, d) if v=puyv = p u y and w=pu′yw = p u' y for words p,y,u,u′p, y, u, u' with u,u′u, u' in the cell list replacement relation; cell word reachability, written v→S,d*wv \to_{S, d}^* w, is the reflexive-transitive closure of this rewriting step relation.

A cell c∈Cell(q)c \in \mathrm{Cell}(q) satisfies the semantic zero cell condition semzeroS(c)\mathrm{semzero}_S(c) if mark(c)=full\mathrm{mark}(c) = \mathrm{full} and one of three failure conditions holds: ϕ(head(c))∈{acq,fin,succ}\phi(\mathrm{head}(c)) \in \{\mathrm{acq}, \mathrm{fin}, \mathrm{succ}\} with r(head(c))≠0r(\mathrm{head}(c)) \neq 0; ϕ(head(c))=ag\phi(\mathrm{head}(c)) = \mathrm{ag} with τCS(task(c),j(head(c)))(r(head(c)))=false\tau_{C_S(\mathrm{task}(c), j(\mathrm{head}(c)))}(r(\mathrm{head}(c))) = \mathrm{false}; or ϕ(head(c))=succ\phi(\mathrm{head}(c)) = \mathrm{succ} with z(meta(c))=truez(\mathrm{meta}(c)) = \mathrm{true}.✦ A cell c∈Cell(q)c \in \mathrm{Cell}(q) satisfies the unary zero cell condition zero1(S,d,c)\mathrm{zero}_1(S, d, c) if cc fails fmtS,d(c)\mathrm{fmt}_{S, d}(c), satisfies semzeroS(c)\mathrm{semzero}_S(c), or has pos(c)=palette(x)\mathrm{pos}(c) = \mathrm{palette}(x) and chk(c)=passed(x)\mathrm{chk}(c) = \mathrm{passed}(x) for some 0≤x<q0 \le x < q.✦ Two cells a,b∈Cell(q)a, b \in \mathrm{Cell}(q) satisfy the binary zero cell condition zero2(a,b)\mathrm{zero}_2(a, b) if they fail pair(a,b)\mathrm{pair}(a, b), share the same palette position palette(x)\mathrm{palette}(x) for some 0≤x<q0 \le x < q, or satisfy pos(a)=palette(x)\mathrm{pos}(a) = \mathrm{palette}(x) and chk(a)=head(y)\mathrm{chk}(a) = \mathrm{head}(y) for some 0≤x,y<q0 \le x, y < q with x≠yx \neq y while pos(b)=stop\mathrm{pos}(b) = \mathrm{stop}.✦ A cell word vv satisfies the zero cell word predicate zeroS,d(v)\mathrm{zero}_{S, d}(v) if either v=[c]v = [c] with zero1(S,d,c)\mathrm{zero}_1(S, d, c) or v=[a,b]v = [a, b] with zero2(a,b)\mathrm{zero}_2(a, b).✦ A cell word ww satisfies the surviving cell word predicate survS,d(w)\mathrm{surv}_{S, d}(w) if no word reachable from ww under (S,d)(S, d) admits a factorization puyp u y with zeroS,d(u)\mathrm{zero}_{S, d}(u).✦

Head Tours, Regions, and Components

For integers m,N≥1m, N \ge 1, a head-tour control state c∈Ctrl(N)c \in \mathrm{Ctrl}(N) is one of acq\mathrm{acq}, rl(p)\mathrm{rl}(p), rr(p)\mathrm{rr}(p), bg\mathrm{bg}, ag\mathrm{ag}, ul(p)\mathrm{ul}(p), ur(p)\mathrm{ur}(p), or fin\mathrm{fin} with 0≤p<N0 \le p < N, and a full-tour control state κ∈FullCtrl(m,N)\kappa \in \mathrm{FullCtrl}(m, N) is either cl(j,c)\mathrm{cl}(j, c) with 0≤j<m0 \le j < m and c∈Ctrl(N)c \in \mathrm{Ctrl}(N) or succ\mathrm{succ}. A clause tour state s∈State(N)s \in \mathrm{State}(N) is a triple (c,r,σ)∈Ctrl(N)×𝔽23×{false,true}(c, r, \sigma) \in \mathrm{Ctrl}(N) \times \mathbb{F}_2^3 \times \{\mathrm{false}, \mathrm{true}\}, and a full tour state s∈FullState(m,N)s \in \mathrm{FullState}(m, N) is a triple (κ,r,σ)∈FullCtrl(m,N)×𝔽23×{false,true}(\kappa, r, \sigma) \in \mathrm{FullCtrl}(m, N) \times \mathbb{F}_2^3 \times \{\mathrm{false}, \mathrm{true}\}, whose components are written κ(s),r(s),σ(s)\kappa(s), r(s), \sigma(s). For 0≤j<m0 \le j < m, the embedding atj:State(N)→FullState(m,N)\mathrm{at}_j : \mathrm{State}(N) \to \mathrm{FullState}(m, N) sends (c,r,σ)(c, r, \sigma) to (cl(j,c),r,σ)(\mathrm{cl}(j, c), r, \sigma).✦

A clause tour payload PP on N≥1N \ge 1 positions consists of register deltas δP:{0,…,N−1}→𝔽23\delta_P : \{0, \dots, N - 1\} \to \mathbb{F}_2^3 satisfying δP(N−1)=0\delta_P(N - 1) = 0 and a gate predicate GPG_P on 𝔽23\mathbb{F}_2^3.✦ For a clause tour payload PP on N≥1N \ge 1 positions, the payload tour transition s→Pts \to_P t on State(N)\mathrm{State}(N) consists of the eleven directed edges in (3): (acq,r,σ)→P(rl(N−1),r,σ),(rl(p),r,σ)→P(rl(p−1),r+δP(p−1),σ)(1≤p<N),(rl(0),r,σ)→P(rr(0),r,σ),(rr(p),r,σ)→P(rr(p+1),r,σ)(0≤p<N−1),(rr(N−1),r,σ)→P(bg,r,σ),(bg,r,σ)→P(ag,r,σ)(if GP(r)),(ag,r,σ)→P(ul(N−1),r,σ),(ul(p),r,σ)→P(ul(p−1),r,σ)(1≤p<N),(ul(0),r,σ)→P(ur(0),r,σ),(ur(p),r,σ)→P(ur(p+1),r+δP(p),σ)(0≤p<N−1),(ur(N−1),r,σ)→P(fin,r,σ).\begin{aligned} (\mathrm{acq}, r, \sigma) &\to_P (\mathrm{rl}(N - 1), r, \sigma), \\ (\mathrm{rl}(p), r, \sigma) &\to_P (\mathrm{rl}(p - 1), r + \delta_P(p - 1), \sigma) && (1 \le p < N), \\ (\mathrm{rl}(0), r, \sigma) &\to_P (\mathrm{rr}(0), r, \sigma), \\ (\mathrm{rr}(p), r, \sigma) &\to_P (\mathrm{rr}(p + 1), r, \sigma) && (0 \le p < N - 1), \\ (\mathrm{rr}(N - 1), r, \sigma) &\to_P (\mathrm{bg}, r, \sigma), \\ (\mathrm{bg}, r, \sigma) &\to_P (\mathrm{ag}, r, \sigma) && (\text{if } G_P(r)), \\ (\mathrm{ag}, r, \sigma) &\to_P (\mathrm{ul}(N - 1), r, \sigma), \\ (\mathrm{ul}(p), r, \sigma) &\to_P (\mathrm{ul}(p - 1), r, \sigma) && (1 \le p < N), \\ (\mathrm{ul}(0), r, \sigma) &\to_P (\mathrm{ur}(0), r, \sigma), \\ (\mathrm{ur}(p), r, \sigma) &\to_P (\mathrm{ur}(p + 1), r + \delta_P(p), \sigma) && (0 \le p < N - 1), \\ (\mathrm{ur}(N - 1), r, \sigma) &\to_P (\mathrm{fin}, r, \sigma). \end{aligned}(3)✦ A clause tour state (c,r,σ)∈State(N)(c, r, \sigma) \in \mathrm{State}(N) satisfies the payload semantic zero condition for PP if c∈{acq,fin}c \in \{\mathrm{acq}, \mathrm{fin}\} with r≠0r \neq 0, or c=agc = \mathrm{ag} with ¬GP(r)\neg G_P(r).✦

A head-tour plan QQ of m≥1m \ge 1 clauses on N≥1N \ge 1 positions consists of mm clause tour payloads P0,…,Pm−1P_0, \dots, P_{m - 1} on NN positions and a Boolean zero-task flag zQz_Q.✦ For a head-tour plan QQ of mm clauses on NN positions, the plan tour transition s→Qts \to_Q t on FullState(m,N)\mathrm{FullState}(m, N) consists of the four rules in (4): atj(s)→Qatj(t)if s→Pjt(0≤j<m),ati(fin,0,σ)→Qati+1(acq,0,σ)(0≤i<m−1),atm−1(fin,0,σ)→Q(succ,0,σ),(succ,0,σ)→Q(succ,0,¬σ)if zQ=false.\begin{aligned} \mathrm{at}_j(s) &\to_Q \mathrm{at}_j(t) && \text{if } s \to_{P_j} t \quad (0 \le j < m), \\ \mathrm{at}_i(\mathrm{fin}, 0, \sigma) &\to_Q \mathrm{at}_{i + 1}(\mathrm{acq}, 0, \sigma) && (0 \le i < m - 1), \\ \mathrm{at}_{m - 1}(\mathrm{fin}, 0, \sigma) &\to_Q (\mathrm{succ}, 0, \sigma), \\ (\mathrm{succ}, 0, \sigma) &\to_Q (\mathrm{succ}, 0, \neg \sigma) && \text{if } z_Q = \mathrm{false}. \end{aligned}(4)✦ Two full tour states s,t∈FullState(m,N)s, t \in \mathrm{FullState}(m, N) are joined by a symmetric plan tour step if s→Qts \to_Q t or t→Qst \to_Q s; plan reachability s→Q*ts \to_Q^* t is the reflexive-transitive closure of this symmetric step relation. A full tour state s∈FullState(m,N)s \in \mathrm{FullState}(m, N) is a bad tour state for QQ, written BadQ(s)\mathrm{Bad}_Q(s), if κ(s)=cl(j,c)\kappa(s) = \mathrm{cl}(j, c) and (c,r(s),σ(s))(c, r(s), \sigma(s)) satisfies the payload semantic zero condition for PjP_j, or if κ(s)=succ\kappa(s) = \mathrm{succ} and r(s)≠0r(s) \neq 0.✦

For parameters (q,d)(q, d) with q≥1q \ge 1 and d≥0d \ge 0, an acquired prefix PP consists of a length |P|>0|P| > 0 and cells c0,…,c|P|−1∈Cell(q)c_0, \dots, c_{|P| - 1} \in \mathrm{Cell}(q) such that skel(ci)\mathrm{skel}(c_i) is initial if and only if i=0i = 0, adjacent skeletons skel(ci)\mathrm{skel}(c_i) and skel(ci+1)\mathrm{skel}(c_{i + 1}) satisfy both struct\mathrm{struct} and int\mathrm{int} for each 0≤i<|P|−10 \le i < |P| - 1, and every cic_i satisfies pfmtd(ci)\mathrm{pfmt}_d(c_i).✦ A cell region RR of parameters (q,d)(q, d) consists of a length |R|>0|R| > 0, a verification task tRt_R, and cells c0,…,c|R|−1∈Cell(q)c_0, \dots, c_{|R| - 1} \in \mathrm{Cell}(q) such that task(ci)=tR\mathrm{task}(c_i) = t_R and pfmtd(ci)\mathrm{pfmt}_d(c_i) hold for every 0≤i<|R|0 \le i < |R|, skel(ci)\mathrm{skel}(c_i) is initial if and only if i=0i = 0 and terminal if and only if i=|R|−1i = |R| - 1, and adjacent skeletons skel(ci)\mathrm{skel}(c_i) and skel(ci+1)\mathrm{skel}(c_{i + 1}) satisfy both struct\mathrm{struct} and int\mathrm{int} for each 0≤i<|R|−10 \le i < |R| - 1.✦ Write w(P)w(P) and w(R)w(R) for the cell words of PP and RR. For σ∈{false,true}\sigma \in \{\mathrm{false}, \mathrm{true}\}, the idle word of an acquired prefix PP is idleP(σ)=[idle(c0,σ)]⋯[idle(c|P|−1,σ)]\mathrm{idle}_P(\sigma) = [\mathrm{idle}(c_0, \sigma)] \cdots [\mathrm{idle}(c_{|P| - 1}, \sigma)], and the idle word of a cell region RR is idleR(σ)=[idle(c0,σ)]⋯[idle(c|R|−1,σ)]\mathrm{idle}_R(\sigma) = [\mathrm{idle}(c_0, \sigma)] \cdots [\mathrm{idle}(c_{|R| - 1}, \sigma)].

Given a cell region RR of parameters (q,d)(q, d) with cells c0,…,cN−1∈Cell(q)c_0, \dots, c_{N - 1} \in \mathrm{Cell}(q) and a schedule SS, set m=mS(tR)m = m_S(t_R) and N=|R|N = |R|. A full tour state s∈FullState(m,N)s \in \mathrm{FullState}(m, N) satisfies the region side condition for RR and SS if z(tR)=truez(t_R) = \mathrm{true} implies σ(s)=false\sigma(s) = \mathrm{false}.✦ The tour plan of RR, written QR(S)Q_R(S), is the head-tour plan of mm clauses on NN positions with zero-task flag z(tR)z(t_R) whose jj-th payload (0≤j<m0 \le j < m) has deltas δ(i)=δCS(tR,j)(ci)\delta(i) = \delta_{C_S(t_R, j)}(c_i) for 0≤i<N0 \le i < N (vanishing at N−1N - 1) and gate predicate τCS(tR,j)(r)=true\tau_{C_S(t_R, j)}(r) = \mathrm{true}.✦ For a full tour state s=(κ,r,σ)∈FullState(m,N)s = (\kappa, r, \sigma) \in \mathrm{FullState}(m, N), the head position pR(s)∈{0,…,N−1}p_R(s) \in \{0, \dots, N - 1\} is pp if κ=cl(j,c)\kappa = \mathrm{cl}(j, c) with cc one of rl(p)\mathrm{rl}(p), rr(p)\mathrm{rr}(p), ul(p)\mathrm{ul}(p), or ur(p)\mathrm{ur}(p), and N−1N - 1 otherwise; the clause index jR(s)∈{0,…,m−1}j_R(s) \in \{0, \dots, m - 1\} is jj if κ=cl(j,c)\kappa = \mathrm{cl}(j, c) and 00 if κ=succ\kappa = \mathrm{succ}; and the head phase ϕR(s)∈Φ\phi_R(s) \in \Phi is the computation phase obtained by dropping any position argument on cc when κ=cl(j,c)\kappa = \mathrm{cl}(j, c) and equal to succ\mathrm{succ} when κ=succ\kappa = \mathrm{succ}. For such RR, SS, and s=(κ,r,σ)s = (\kappa, r, \sigma), the realized cell ρR,S(s,i)\rho_{R, S}(s, i) at position 0≤i<N0 \le i < N is given by (5), and the realized word realizeR,S(s)\mathrm{realize}_{R, S}(s) is [ρR,S(s,0)]⋯[ρR,S(s,N−1)][\rho_{R, S}(s, 0)] \cdots [\rho_{R, S}(s, N - 1)]: ρR,S(s,i)={wing(ci,left)if i<pR(s),full(ci,σ,jR(s),ϕR(s),r)if i=pR(s),wing(ci,right)if i>pR(s).\rho_{R, S}(s, i) = \begin{cases} \mathrm{wing}(c_i, \mathrm{left}) & \text{if } i < p_R(s), \\ \mathrm{full}(c_i, \sigma, j_R(s), \phi_R(s), r) & \text{if } i = p_R(s), \\ \mathrm{wing}(c_i, \mathrm{right}) & \text{if } i > p_R(s). \end{cases}(5)

On a finite index set {0,…,N−1}\{0, \dots, N - 1\}, two indices i,ji, j satisfy connectivity without cuts with respect to a predicate cut\mathrm{cut} if cut(k)\mathrm{cut}(k) fails for every kk satisfying min⁡(i,j)≤k<max⁡(i,j)\min(i, j) \le k < \max(i, j).✦ For a cell sequence f:{0,…,N−1}→Cell(q)f : \{0, \dots, N - 1\} \to \mathrm{Cell}(q), the cell cut predicate cutf(i)\mathrm{cut}_f(i) holds when skel(f(i))\mathrm{skel}(f(i)) is right-external, and the same-region relation samef(i,j)\mathrm{same}_f(i, j) is connectivity without cuts with respect to cutf\mathrm{cut}_f. At any index i∈{0,…,N−1}i \in \{0, \dots, N - 1\}, the component member set is M(f,i)={k∈{0,…,N−1}:samef(i,k)}M(f, i) = \{k \in \{0, \dots, N - 1\} : \mathrm{same}_f(i, k)\}, with left endpoint ℓ(f,i)=min⁡M(f,i)\ell(f, i) = \min M(f, i), right boundary r(f,i)=max⁡M(f,i)r(f, i) = \max M(f, i), component size N(f,i)=r(f,i)+1−ℓ(f,i)N(f, i) = r(f, i) + 1 - \ell(f, i), and component word w(f,i)=[f(ℓ(f,i))]⋯[f(r(f,i))]w(f, i) = [f(\ell(f, i))] \cdots [f(r(f, i))]. Given a schedule SS, data size d≥0d \ge 0, a cell sequence f:{0,…,N−1}→Cell(q)f : \{0, \dots, N - 1\} \to \mathrm{Cell}(q), and 0≤i<N0 \le i < N such that w(f)w(f) satisfies synS,d(w(f))\mathrm{syn}_{S, d}(w(f)), if mark(f(i))=full\mathrm{mark}(f(i)) = \mathrm{full} then the component region Rf,iR_{f, i} is the cell region of size N(f,i)N(f, i), task task(f(i))\mathrm{task}(f(i)), and cells f(ℓ(f,i)+j)f(\ell(f, i) + j) for 0≤j<N(f,i)0 \le j < N(f, i) (having word w(Rf,i)=w(f,i)w(R_{f, i}) = w(f, i)); if mark(f(i))=boundary\mathrm{mark}(f(i)) = \mathrm{boundary} then the component partial region Pf,iP_{f, i} is the acquired prefix of size N(f,i)N(f, i) and cells f(ℓ(f,i)+j)f(\ell(f, i) + j) for 0≤j<N(f,i)0 \le j < N(f, i) (having word w(Pf,i)=w(f,i)w(P_{f, i}) = w(f, i)).

The Claim

Theorem 1. Let q≥1q \ge 1 and d≥0d \ge 0, and let SS be a verification clause schedule of bound qq.

  1. For any head-tour plan QQ of m≥1m \ge 1 clauses on N≥1N \ge 1 positions and any full tour state s∈FullState(m,N)s \in \mathrm{FullState}(m, N), plan reachability satisfies (6): s→Q*at0(acq,0,σ(s))or∃z,s→Q*zwithBadQ(z).s \to_Q^* \mathrm{at}_0(\mathrm{acq}, 0, \sigma(s)) \quad\text{or}\quad \exists\, z,\; s \to_Q^* z \;\text{with}\; \mathrm{Bad}_Q(z).(6)✦

  2. Given a cell region RR of parameters (q,d)(q, d) and a full tour state s∈FullState(mS(tR),|R|)s \in \mathrm{FullState}(m_S(t_R), |R|) satisfying the region side condition for RR and SS, the realized word satisfies (7): realizeR,S(s)→S,d*realizeR,S(at0(acq,0,σ(s)))or∃w,p,a,z,realizeR,S(s)→S,d*w=p[a]zwithzeroS,d([a]),\mathrm{realize}_{R, S}(s) \to_{S, d}^* \mathrm{realize}_{R, S}\bigl(\mathrm{at}_0(\mathrm{acq}, 0, \sigma(s))\bigr) \quad\text{or}\quad \exists\, w, p, a, z,\; \mathrm{realize}_{R, S}(s) \to_{S, d}^* w = p [a] z \;\text{with}\; \mathrm{zero}_{S, d}([a]),(7)✦ and under the same hypotheses the realized word satisfies (8): realizeR,S(s)→S,d*idleR(σ(s))or∃w,p,a,z,realizeR,S(s)→S,d*w=p[a]zwithzeroS,d([a]).\mathrm{realize}_{R, S}(s) \to_{S, d}^* \mathrm{idle}_R(\sigma(s)) \quad\text{or}\quad \exists\, w, p, a, z,\; \mathrm{realize}_{R, S}(s) \to_{S, d}^* w = p [a] z \;\text{with}\; \mathrm{zero}_{S, d}([a]).(8)✦

  3. For a cell region RR of parameters (q,d)(q, d) whose cells cic_i all satisfy fmtS,d(ci)\mathrm{fmt}_{S, d}(c_i), suppose an index 0≤h<|R|0 \le h < |R| has mark(ch)=full\mathrm{mark}(c_h) = \mathrm{full}, mark(ci)=left\mathrm{mark}(c_i) = \mathrm{left} for all i<hi < h, and mark(ci)=right\mathrm{mark}(c_i) = \mathrm{right} for all i>hi > h. Writing σh=σ(head(ch))\sigma_h = \sigma(\mathrm{head}(c_h)), the region word satisfies (9): w(R)→S,d*idleR(σh)or∃w,p,a,z,w(R)→S,d*w=p[a]zwithzeroS,d([a]).w(R) \to_{S, d}^* \mathrm{idle}_R(\sigma_h) \quad\text{or}\quad \exists\, w, p, a, z,\; w(R) \to_{S, d}^* w = p [a] z \;\text{with}\; \mathrm{zero}_{S, d}([a]).(9)✦

  4. Let f:{0,…,N−1}→Cell(q)f : \{0, \dots, N - 1\} \to \mathrm{Cell}(q) satisfy synS,d(w(f))\mathrm{syn}_{S, d}(w(f)), fix 0≤i<N0 \le i < N, and put σi=σ(head(f(i)))\sigma_i = \sigma(\mathrm{head}(f(i))). If mark(f(i))=full\mathrm{mark}(f(i)) = \mathrm{full}, the component region Rf,iR_{f, i} satisfies (10): w(Rf,i)→S,d*idleRf,i(σi)or∃w,p,a,z,w(Rf,i)→S,d*w=p[a]zwithzeroS,d([a]).w(R_{f, i}) \to_{S, d}^* \mathrm{idle}_{R_{f, i}}(\sigma_i) \quad\text{or}\quad \exists\, w, p, a, z,\; w(R_{f, i}) \to_{S, d}^* w = p [a] z \;\text{with}\; \mathrm{zero}_{S, d}([a]).(10)✦ If mark(f(i))=boundary\mathrm{mark}(f(i)) = \mathrm{boundary}, the component partial region Pf,iP_{f, i} satisfies (11): w(Pf,i)→S,d*idlePf,i(σi).w(P_{f, i}) \to_{S, d}^* \mathrm{idle}_{P_{f, i}}(\sigma_i).(11)✦

  5. For any sequence f:{0,…,N−1}→Cell(q)f : \{0, \dots, N - 1\} \to \mathrm{Cell}(q) satisfying synS,d(w(f))\mathrm{syn}_{S, d}(w(f)) and survS,d(w(f))\mathrm{surv}_{S, d}(w(f)) and any index 0≤i<N0 \le i < N such that skel(f(i))\mathrm{skel}(f(i)) carries an active head marker, the component word w(f,i)w(f, i) satisfies (12): ∃v,w(f,i)→S,d*vwithlocked(v)=0.\exists\, v,\; w(f, i) \to_{S, d}^* v \;\text{with}\; \mathrm{locked}(v) = 0.(12)✦

What Is Checked

The claims above are stated over head-tour plans and their full states, cell regions and their realized words, formatted cell regions, acquired prefixes, cell words satisfying cell word syntax and survival, and cut-free connected components of finite cell sequences. For these constructions, the library also proves that for every finite cell sequence and every index in it, the component member set is nonempty✦ and the component size is positive.✦