OctoInformBeta

OpenAI preprint, September 2026 ยท ยง2. A hierarchy defined by finite local rules

Lemma 2.5: Tour success precisely when clauses hold, semantic-zero and pivot soundness, good-word invariance under rewriting, and circuit-tableau equivalence

Head tours verify regions and match coded table certificates.

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

Write ๐”น={false,true}\mathbb{B} = \{\mathrm{false}, \mathrm{true}\} for the Boolean truth values and ๐”ฝ2\mathbb{F}_2 for the two-element field. Consider a finite schedule of three-wire Boolean clauses reading data and certificate bits stored across contiguous blocks of finite-table cells. Checking that all scheduled clauses hold by strictly local, reversible moves requires sweeping a head across each block region while keeping interleaved heads across neighboring regions consistent with their register sums, and linking clause satisfiability on circuit tableaux to the raw bitstring table of a universal stack machine.

Head Tours

Fix integers m,N>0m, N > 0. The control set ๐’žN\mathcal{C}_N for a single-clause sweep on positions {0,โ€ฆ,Nโˆ’1}\{0, \dots, N - 1\} consists of acq\mathrm{acq} (acquisition), rdL(p)\mathrm{rd}_{\mathrm{L}}(p) and rdR(p)\mathrm{rd}_{\mathrm{R}}(p) (left and right read at p<Np < N), bg\mathrm{bg} (before-gate), ag\mathrm{ag} (after-gate), unL(p)\mathrm{un}_{\mathrm{L}}(p) and unR(p)\mathrm{un}_{\mathrm{R}}(p) (left and right undo at p<Np < N), and fin\mathrm{fin} (finish).โœฆ A clause tour payload ฯ€=(ฮด,ฮณ)\pi = (\delta, \gamma) on NN positions specifies a delta map ฮด:{0,โ€ฆ,Nโˆ’1}โ†’๐”ฝ23\delta : \{0, \dots, N - 1\} \to \mathbb{F}_2^3 with ฮด(Nโˆ’1)=0\delta(N - 1) = 0 and a gate predicate ฮณ\gamma on three-bit registers ๐”ฝ23\mathbb{F}_2^3; its total delta is ฯƒ(ฯ€)=โˆ‘p=0Nโˆ’1ฮด(p)โˆˆ๐”ฝ23\sigma(\pi) = \sum_{p = 0}^{N - 1} \delta(p) \in \mathbb{F}_2^3. A clause tour state is a triple (c,r,s)โˆˆ๐’žNร—๐”ฝ23ร—๐”น(c, r, s) \in \mathcal{C}_N \times \mathbb{F}_2^3 \times \mathbb{B}.

Directed tour transitions โ†’ฯ€\to_\pi on ๐’žNร—๐”ฝ23ร—๐”น\mathcal{C}_N \times \mathbb{F}_2^3 \times \mathbb{B} advance as follows: (acq,r,s)โ†’ฯ€(rdL(Nโˆ’1),r,s)(\mathrm{acq}, r, s) \to_\pi (\mathrm{rd}_{\mathrm{L}}(N - 1), r, s); (rdL(p),r,s)โ†’ฯ€(rdL(pโˆ’1),r+ฮด(pโˆ’1),s)(\mathrm{rd}_{\mathrm{L}}(p), r, s) \to_\pi (\mathrm{rd}_{\mathrm{L}}(p - 1), r + \delta(p - 1), s) for 1โ‰คp<N1 \le p < N; (rdL(0),r,s)โ†’ฯ€(rdR(0),r,s)(\mathrm{rd}_{\mathrm{L}}(0), r, s) \to_\pi (\mathrm{rd}_{\mathrm{R}}(0), r, s); (rdR(p),r,s)โ†’ฯ€(rdR(p+1),r,s)(\mathrm{rd}_{\mathrm{R}}(p), r, s) \to_\pi (\mathrm{rd}_{\mathrm{R}}(p + 1), r, s) for p+1<Np + 1 < N; (rdR(Nโˆ’1),r,s)โ†’ฯ€(bg,r,s)(\mathrm{rd}_{\mathrm{R}}(N - 1), r, s) \to_\pi (\mathrm{bg}, r, s); (bg,r,s)โ†’ฯ€(ag,r,s)(\mathrm{bg}, r, s) \to_\pi (\mathrm{ag}, r, s) when ฮณ(r)\gamma(r) holds; (ag,r,s)โ†’ฯ€(unL(Nโˆ’1),r,s)(\mathrm{ag}, r, s) \to_\pi (\mathrm{un}_{\mathrm{L}}(N - 1), r, s); (unL(p),r,s)โ†’ฯ€(unL(pโˆ’1),r,s)(\mathrm{un}_{\mathrm{L}}(p), r, s) \to_\pi (\mathrm{un}_{\mathrm{L}}(p - 1), r, s) for 1โ‰คp<N1 \le p < N; (unL(0),r,s)โ†’ฯ€(unR(0),r,s)(\mathrm{un}_{\mathrm{L}}(0), r, s) \to_\pi (\mathrm{un}_{\mathrm{R}}(0), r, s); (unR(p),r,s)โ†’ฯ€(unR(p+1),r+ฮด(p),s)(\mathrm{un}_{\mathrm{R}}(p), r, s) \to_\pi (\mathrm{un}_{\mathrm{R}}(p + 1), r + \delta(p), s) for p+1<Np + 1 < N; and (unR(Nโˆ’1),r,s)โ†’ฯ€(fin,r,s)(\mathrm{un}_{\mathrm{R}}(N - 1), r, s) \to_\pi (\mathrm{fin}, r, s). A clause tour state (c,r,s)(c, r, s) is a payload semantic zero for ฯ€\pi if either cโˆˆ{acq,fin}c \in \{\mathrm{acq}, \mathrm{fin}\} and rโ‰ 0r \neq 0, or c=agc = \mathrm{ag} and ฮณ(r)\gamma(r) fails.โœฆ

A head-tour plan Q=({ฯ€j}j=0mโˆ’1,zQ)Q = (\{\pi_j\}_{j = 0}^{m - 1}, z_Q) pairs mm clause tour payloads ฯ€j=(ฮดj,ฮณj)\pi_j = (\delta_j, \gamma_j) on NN positions with a zero-task flag zQโˆˆ๐”นz_Q \in \mathbb{B}; clause j<mj < m holds in QQ, written QโŠจjQ \models j, when ฮณj(ฯƒ(ฯ€j))\gamma_j(\sigma(\pi_j)) holds. A full control state is either a clause control (j,c)(j, c) with j<mj < m and cโˆˆ๐’žNc \in \mathcal{C}_N or the terminal control succ\mathrm{succ}; write โ„ฑm,N\mathcal{F}_{m, N} for the set of full tour states t=(ctrl⁡(t),reg⁡(t),side⁡(t))t = (\operatorname{ctrl}(t), \operatorname{reg}(t), \operatorname{side}(t)) pairing a full control state with a register in ๐”ฝ23\mathbb{F}_2^3 and a side in ๐”น\mathbb{B}, and write ฮนj(c,r,s)=((j,c),r,s)\iota_j(c, r, s) = ((j, c), r, s)โœฆ. Directed plan transitions โ†’Q\to_Q apply a ฯ€j\pi_j-transition inside clause jj, move ฮนi(fin,0,s)โ†’Qฮนi+1(acq,0,s)\iota_i(\mathrm{fin}, 0, s) \to_Q \iota_{i + 1}(\mathrm{acq}, 0, s) for i+1<mi + 1 < m, move ฮนmโˆ’1(fin,0,s)โ†’Q(succ,0,s)\iota_{m - 1}(\mathrm{fin}, 0, s) \to_Q (\mathrm{succ}, 0, s), and flip (succ,0,s)โ†’Q(succ,0,ยฌs)(\mathrm{succ}, 0, s) \to_Q (\mathrm{succ}, 0, \neg s) when zQ=falsez_Q = \mathrm{false}. The symmetric step relation tโ†”Qtโ€ฒt \leftrightarrow_Q t' holds when tโ†’Qtโ€ฒt \to_Q t' or tโ€ฒโ†’Qtt' \to_Q t, and tour reachability tโˆผQtโ€ฒt \sim_Q t' is the reflexive transitive closure of โ†”Q\leftrightarrow_Q. A full tour state tt of QQ is bad for QQ if either ctrl⁡(t)=(j,c)\operatorname{ctrl}(t) = (j, c) and (c,reg⁡(t),side⁡(t))(c, \operatorname{reg}(t), \operatorname{side}(t)) is a payload semantic zero for ฯ€j\pi_j, or ctrl⁡(t)=succ\operatorname{ctrl}(t) = \mathrm{succ} and reg⁡(t)โ‰ 0\operatorname{reg}(t) \neq 0; a full tour state tt is semantically zero for QQ, written ๐’ตQ(t)\mathcal{Z}_Q(t), if tt is bad for QQ or both ctrl⁡(t)=succ\operatorname{ctrl}(t) = \mathrm{succ} and zQ=truez_Q = \mathrm{true}.

Cells, Regions, and Local Rewriting

A verification task ฯ„=(ar⁡(ฯ„),z(ฯ„))\tau = (\operatorname{ar}(\tau), z(\tau)) consists of an arity ar⁡(ฯ„)โˆˆ{0,โ€ฆ,9}\operatorname{ar}(\tau) \in \{0, \dots, 9\} and a zero-task flag z(ฯ„)โˆˆ๐”นz(\tau) \in \mathbb{B}. For a capacity bound qโˆˆโ„•q \in \mathbb{N}, a data bit address in ๐’Ÿq=๐”นร—{0,โ€ฆ,9}ร—{0,โ€ฆ,qโˆ’1}\mathcal{D}_q = \mathbb{B} \times \{0, \dots, 9\} \times \{0, \dots, q - 1\} specifies a side, a block index, and a position below qq, and the set Addr⁡q\operatorname{Addr}_q of cell memory addresses consists of data addresses data(s,b,p)\mathrm{data}(s, b, p) for (s,b,p)โˆˆ๐’Ÿq(s, b, p) \in \mathcal{D}_q and certificate addresses cert(p)\mathrm{cert}(p) for p<qp < q. A verification clause C=(a,ฮธ)C = (a, \theta) of bound qq pairs three addresses a:{0,1,2}โ†’Addr⁡qa : \{0, 1, 2\} \to \operatorname{Addr}_q with a truth function ฮธ:๐”ฝ23โ†’๐”น\theta : \mathbb{F}_2^3 \to \mathbb{B}. A verification clause schedule SS of bound qq assigns to each task ฯ„\tau a positive clause count 1โ‰คcnt⁡S(ฯ„)โ‰คq1 \le \operatorname{cnt}_S(\tau) \le q and a family of verification clauses CS,ฯ„,j=(aS,ฯ„,j,ฮธS,ฯ„,j)C_{S, \tau, j} = (a_{S, \tau, j}, \theta_{S, \tau, j}) for j<qj < q.โœฆ

Over a color set XX, a palette checker state is idle\mathrm{idle}, passed(x)\mathrm{passed}(x), or head(x)\mathrm{head}(x) for xโˆˆXx \in X; two adjacent checker states form a compatible checker pair when they are (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โˆˆXx \in X, and a checker state satisfies the terminal checker condition when it is idle\mathrm{idle} or head(x)\mathrm{head}(x). For bound qq, a block position is core(p)\mathrm{core}(p) (p<qp < q), pal(x)\mathrm{pal}(x) (x<qx < q), or stop\mathrm{stop}, and a cell marker is one of idle\mathrm{idle}, left\mathrm{left}, bdry\mathrm{bdry}, full\mathrm{full}, or right\mathrm{right}. For an arity bound kk, a block metadata record m=(ar⁡(m),z(m),blk⁡(m))m = (\operatorname{ar}(m), z(m), \operatorname{blk}(m)) has arity ar⁡(m)<k\operatorname{ar}(m) < k, zero-task flag z(m)โˆˆ๐”นz(m) \in \mathbb{B}, and block index blk⁡(m)โ‰คar⁡(m)\operatorname{blk}(m) \le \operatorname{ar}(m); when k=10k = 10, its task projection is task⁡(m)=(ar⁡(m),z(m))\operatorname{task}(m) = (\operatorname{ar}(m), z(m)). A cell skeleton ฮพ=(pos⁡(ฮพ),mrk⁡(ฮพ),meta⁡(ฮพ))\xi = (\operatorname{pos}(\xi), \operatorname{mrk}(\xi), \operatorname{meta}(\xi)) joins a position, marker, and metadata record; marking ฮพ\xi with ฮผ\mu replaces only mrk⁡(ฮพ)\operatorname{mrk}(\xi) by ฮผ\muโœฆ. A skeleton ฮพ\xi is initial when blk⁡(ฮพ)=0\operatorname{blk}(\xi) = 0 and pos⁡(ฮพ)=core(0)\operatorname{pos}(\xi) = \mathrm{core}(0), terminal when blk⁡(ฮพ)=ar⁡(ฮพ)\operatorname{blk}(\xi) = \operatorname{ar}(\xi) and pos⁡(ฮพ)=stop\operatorname{pos}(\xi) = \mathrm{stop}, active-head when mrk⁡(ฮพ)โˆˆ{bdry,full}\operatorname{mrk}(\xi) \in \{\mathrm{bdry}, \mathrm{full}\}, and admissible when mrk⁡(ฮพ)=right\operatorname{mrk}(\xi) = \mathrm{right} implies ฮพ\xi is not initial and mrk⁡(ฮพ)=left\operatorname{mrk}(\xi) = \mathrm{left} implies ฮพ\xi is not terminal; a skeleton ฮพ\xi is left-external when mrk⁡(ฮพ)=idle\operatorname{mrk}(\xi) = \mathrm{idle} or (mrk⁡(ฮพ)โ‰ right\operatorname{mrk}(\xi) \neq \mathrm{right} and ฮพ\xi is initial), and right-external when mrk⁡(ฮพ)โˆˆ{idle,bdry}\operatorname{mrk}(\xi) \in \{\mathrm{idle}, \mathrm{bdry}\} or (mrk⁡(ฮพ)โ‰ left\operatorname{mrk}(\xi) \neq \mathrm{left} and ฮพ\xi is terminal).

Two skeletons ฮพ1,ฮพ2\xi_1, \xi_2 are structurally adjacent precisely in the position pairs (core(p),core(p+1))(\mathrm{core}(p), \mathrm{core}(p + 1)), (core(qโˆ’1),pal(x))(\mathrm{core}(q - 1), \mathrm{pal}(x)), (pal(x),pal(y))(\mathrm{pal}(x), \mathrm{pal}(y)), (pal(x),stop)(\mathrm{pal}(x), \mathrm{stop}), and (stop,core(0))(\mathrm{stop}, \mathrm{core}(0)); two skeletons ฮพ1,ฮพ2\xi_1, \xi_2 are internally consistent when they share arity and zero-task flag, blk⁡(ฮพ2)=blk⁡(ฮพ1)+1\operatorname{blk}(\xi_2) = \operatorname{blk}(\xi_1) + 1 if pos⁡(ฮพ1)=stop\operatorname{pos}(\xi_1) = \mathrm{stop} and blk⁡(ฮพ2)=blk⁡(ฮพ1)\operatorname{blk}(\xi_2) = \operatorname{blk}(\xi_1) otherwise, ฮพ2\xi_2 is not initial, and ฮพ1\xi_1 is not terminal. A skeleton ฮพ\xi accepts marker ฮผ\mu on the left if ฮผโˆˆ{full,right}\mu \in \{\mathrm{full}, \mathrm{right}\} when mrk⁡(ฮพ)=right\operatorname{mrk}(\xi) = \mathrm{right} and ฮผ=left\mu = \mathrm{left} otherwise, and accepts ฮผ\mu on the right if ฮผโˆˆ{left,bdry,full}\mu \in \{\mathrm{left}, \mathrm{bdry}, \mathrm{full}\} when mrk⁡(ฮพ)=left\operatorname{mrk}(\xi) = \mathrm{left} and ฮผ=right\mu = \mathrm{right} otherwise. Two skeletons (ฮพ1,ฮพ2)(\xi_1, \xi_2) form a compatible skeleton pair when they are structurally adjacent and either ฮพ1\xi_1 is right-external and ฮพ2\xi_2 is left-external, or neither is external, ฮพ1\xi_1 accepts mrk⁡(ฮพ2)\operatorname{mrk}(\xi_2) on the right, ฮพ2\xi_2 accepts mrk⁡(ฮพ1)\operatorname{mrk}(\xi_1) on the left, and (ฮพ1,ฮพ2)(\xi_1, \xi_2) are internally consistent.โœฆ A finite sequence of skeletons ฮพ0,โ€ฆ,ฮพNโˆ’1\xi_0, \dots, \xi_{N - 1} is closed if every ฮพi\xi_i is admissible, every adjacent pair (ฮพi,ฮพi+1)(\xi_i, \xi_{i + 1}) is a compatible skeleton pair, and whenever Nโ‰ฅ1N \ge 1, ฮพ0\xi_0 is left-external and ฮพNโˆ’1\xi_{N - 1} is right-external.โœฆ

The nine head computation phases are acq\mathrm{acq}, rdL\mathrm{rd}_{\mathrm{L}}, rdR\mathrm{rd}_{\mathrm{R}}, bg\mathrm{bg}, ag\mathrm{ag}, unL\mathrm{un}_{\mathrm{L}}, unR\mathrm{un}_{\mathrm{R}}, fin\mathrm{fin}, and succ\mathrm{succ}; among them, acq\mathrm{acq}, bg\mathrm{bg}, ag\mathrm{ag}, fin\mathrm{fin}, and succ\mathrm{succ} are endpoint phases. A reading head state (s,j,ฯ•,r)(s, j, \phi, r) specifies a side sโˆˆ๐”นs \in \mathbb{B}, clause j<qj < q, phase ฯ•\phi, and register rโˆˆ๐”ฝ23r \in \mathbb{F}_2^3; the default metadata and default head are (0,false,0)(0, \mathrm{false}, 0) and (false,0,acq,0)(\mathrm{false}, 0, \mathrm{acq}, 0). A finite-table cell c=(ฮพc,ฯ‡c,dc,ฮถc,ฮทc)c = (\xi_c, \chi_c, d_c, \zeta_c, \eta_c) of bound qq consists of a skeleton ฮพc\xi_c with arity bound 1010 (determining pos⁡(c)\operatorname{pos}(c), mrk⁡(c)\operatorname{mrk}(c), meta⁡(c)\operatorname{meta}(c), and task⁡(c)\operatorname{task}(c)), a palette checker ฯ‡c\chi_c over {0,โ€ฆ,qโˆ’1}\{0, \dots, q - 1\}, data bits dc:๐”นโ†’๐”ฝ2d_c : \mathbb{B} \to \mathbb{F}_2, a certificate bit ฮถcโˆˆ๐”ฝ2\zeta_c \in \mathbb{F}_2, and a head state ฮทc=(side⁡(c),cl⁡(c),ph⁡(c),reg⁡(c))\eta_c = (\operatorname{side}(c), \operatorname{cl}(c), \operatorname{ph}(c), \operatorname{reg}(c)). A finite-table cell cc of bound qq is in the core when pos⁡(c)=core(p)\operatorname{pos}(c) = \mathrm{core}(p), in the palette when pos⁡(c)=pal(x)\operatorname{pos}(c) = \mathrm{pal}(x), and head-free when ฮพc\xi_c is not active-head and ฯ‡cโ‰ head(x)\chi_c \neq \mathrm{head}(x) for all x<qx < q. Cell constructors act on cc as follows: c.idle(s)c.\mathrm{idle}(s) keeps pos⁡(c)\operatorname{pos}(c), sets marker idle\mathrm{idle}, default metadata, default head, ฮถ=0\zeta = 0, d(true)=0d(\mathrm{true}) = 0, and d(false)=dc(s)d(\mathrm{false}) = d_c(s); c.bdry(s)c.\mathrm{bdry}(s) marks bdry\mathrm{bdry} and sets head (s,0,acq,0)(s, 0, \mathrm{acq}, 0); c.wing(ฮผ)c.\mathrm{wing}(\mu) marks ฮผ\mu and sets default head; and c.full(s,j,ฯ•,r)c.\mathrm{full}(s, j, \phi, r) marks full\mathrm{full} and sets head (s,j,ฯ•,r)(s, j, \phi, r). Write c[ฯ‡โ†ฯ‡โ€ฒ]c[\chi \leftarrow \chi'] for replacing ฯ‡c\chi_c by ฯ‡โ€ฒ\chi', and c[palโ†y]c[\mathrm{pal} \leftarrow y] for replacing pos⁡(c)\operatorname{pos}(c) by pal(y)\mathrm{pal}(y).

A finite-table cell cc of bound qq is payload-formatted for data size dd if non-palette cells have ฯ‡c=idle\chi_c = \mathrm{idle}, core cells at positions pโ‰ฅdp \ge d have dc=0d_c = 0, and non-core cells have dc=0d_c = 0 and ฮถc=0\zeta_c = 0. A finite-table cell cc of bound qq is formatted for (S,d)(S, d) if ฮพc\xi_c is admissible, cc is payload-formatted for dd, and the following conditions hold: mrk⁡(c)=idle\operatorname{mrk}(c) = \mathrm{idle} forces default metadata, default head, dc(true)=0d_c(\mathrm{true}) = 0, and ฮถc=0\zeta_c = 0; mrk⁡(c)โˆˆ{left,right}\operatorname{mrk}(c) \in \{\mathrm{left}, \mathrm{right}\} forces default head; mrk⁡(c)=bdry\operatorname{mrk}(c) = \mathrm{bdry} forces cl⁡(c)=0\operatorname{cl}(c) = 0, ph⁡(c)=acq\operatorname{ph}(c) = \mathrm{acq}, and reg⁡(c)=0\operatorname{reg}(c) = 0; an active-head skeleton with z(meta⁡(c))=truez(\operatorname{meta}(c)) = \mathrm{true} forces side⁡(c)=false\operatorname{side}(c) = \mathrm{false}; and mrk⁡(c)=full\operatorname{mrk}(c) = \mathrm{full} forces cl⁡(c)=0\operatorname{cl}(c) = 0 when ph⁡(c)=succ\operatorname{ph}(c) = \mathrm{succ}, cl⁡(c)<cnt⁡S(task⁡(c))\operatorname{cl}(c) < \operatorname{cnt}_S(\operatorname{task}(c)) when ph⁡(c)โ‰ succ\operatorname{ph}(c) \neq \mathrm{succ}, and terminal ฮพc\xi_c whenever ph⁡(c)\operatorname{ph}(c) is an endpoint phase. Two cells c1,c2c_1, c_2 satisfy checker compatibility when both being in the palette implies (ฯ‡c1,ฯ‡c2)(\chi_{c_1}, \chi_{c_2}) is a compatible checker pair and c1c_1 in the palette with pos⁡(c2)=stop\operatorname{pos}(c_2) = \mathrm{stop} implies ฯ‡c1\chi_{c_1} satisfies the terminal checker condition; two cells c1,c2c_1, c_2 form a compatible cell pair when both their skeletons and checkers are compatible. A cell word ww of bound qq satisfies word syntax for (S,d)(S, d), written ๐’ฑS,d(w)\mathcal{V}_{S, d}(w), if its skeletons form a closed sequence, every adjacent pair in ww satisfies checker compatibility, and every cell in ww is formatted for (S,d)(S, d).โœฆ For a finite-table cell cc of bound qq and an address aโˆˆAddr⁡qa \in \operatorname{Addr}_q, the reading val⁡c(a)\operatorname{val}_c(a) is dc(s)d_c(s) if a=data(s,b,p)a = \mathrm{data}(s, b, p), pos⁡(c)=core(p)\operatorname{pos}(c) = \mathrm{core}(p), and blk⁡(meta⁡(c))=b\operatorname{blk}(\operatorname{meta}(c)) = b; ฮถc\zeta_c if a=cert(p)a = \mathrm{cert}(p), pos⁡(c)=core(p)\operatorname{pos}(c) = \mathrm{core}(p), and blk⁡(meta⁡(c))=0\operatorname{blk}(\operatorname{meta}(c)) = 0; and 00 otherwise. For a verification clause C=(a,ฮธ)C = (a, \theta) and a cell cc of bound qq, the register delta ฮ”(C,c)โˆˆ๐”ฝ23\Delta(C, c) \in \mathbb{F}_2^3 has ii-th entry val⁡c(a(i))\operatorname{val}_c(a(i)).

Under schedule SS, the unary cell transitions relate single cells as follows: c.idle(s)โ†’c.bdry(s)c.\mathrm{idle}(s) \to c.\mathrm{bdry}(s) when ฮพc\xi_c is initial; c.bdry(s)โ†’c.full(s,0,acq,0)c.\mathrm{bdry}(s) \to c.\mathrm{full}(s, 0, \mathrm{acq}, 0) when ฮพc\xi_c is terminal; at terminal ฮพc\xi_c, c.full(s,j,acq,r)โ†’c.full(s,j,rdL,r)c.\mathrm{full}(s, j, \mathrm{acq}, r) \to c.\mathrm{full}(s, j, \mathrm{rd}_{\mathrm{L}}, r), c.full(s,j,rdR,r)โ†’c.full(s,j,bg,r)c.\mathrm{full}(s, j, \mathrm{rd}_{\mathrm{R}}, r) \to c.\mathrm{full}(s, j, \mathrm{bg}, r), c.full(s,j,bg,r)โ†’c.full(s,j,ag,r)c.\mathrm{full}(s, j, \mathrm{bg}, r) \to c.\mathrm{full}(s, j, \mathrm{ag}, r) when ฮธS,task⁡(c),j(r)=true\theta_{S, \operatorname{task}(c), j}(r) = \mathrm{true}, c.full(s,j,ag,r)โ†’c.full(s,j,unL,r)c.\mathrm{full}(s, j, \mathrm{ag}, r) \to c.\mathrm{full}(s, j, \mathrm{un}_{\mathrm{L}}, r), c.full(s,j,unR,r)โ†’c.full(s,j,fin,r)c.\mathrm{full}(s, j, \mathrm{un}_{\mathrm{R}}, r) \to c.\mathrm{full}(s, j, \mathrm{fin}, r), c.full(s,j,fin,0)โ†’c.full(s,j+1,acq,0)c.\mathrm{full}(s, j, \mathrm{fin}, 0) \to c.\mathrm{full}(s, j + 1, \mathrm{acq}, 0) (j+1<qj + 1 < q), c.full(s,j,fin,0)โ†’c.full(s,0,succ,0)c.\mathrm{full}(s, j, \mathrm{fin}, 0) \to c.\mathrm{full}(s, 0, \mathrm{succ}, 0) when j+1=cnt⁡S(task⁡(c))j + 1 = \operatorname{cnt}_S(\operatorname{task}(c)), and c.full(s,0,succ,0)โ†’c.full(ยฌs,0,succ,0)c.\mathrm{full}(s, 0, \mathrm{succ}, 0) \to c.\mathrm{full}(\neg s, 0, \mathrm{succ}, 0) when z(meta⁡(c))=falsez(\operatorname{meta}(c)) = \mathrm{false}; and at initial ฮพc\xi_c, c.full(s,j,rdL,r)โ†’c.full(s,j,rdR,r)c.\mathrm{full}(s, j, \mathrm{rd}_{\mathrm{L}}, r) \to c.\mathrm{full}(s, j, \mathrm{rd}_{\mathrm{R}}, r) and c.full(s,j,unL,r)โ†’c.full(s,j,unR,r)c.\mathrm{full}(s, j, \mathrm{un}_{\mathrm{L}}, r) \to c.\mathrm{full}(s, j, \mathrm{un}_{\mathrm{R}}, r). The binary cell transitions relate adjacent cell pairs (a,b)โ†’(aโ€ฒ,bโ€ฒ)(a, b) \to (a', b') in eight ways: (a.bdry(s),b.idle(s))โ†’(a.wing(left),b.bdry(s))(a.\mathrm{bdry}(s), b.\mathrm{idle}(s)) \to (a.\mathrm{wing}(\mathrm{left}), b.\mathrm{bdry}(s)) when (a,b)(a, b) marked (left,bdry)(\mathrm{left}, \mathrm{bdry}) form a compatible skeleton pair; four sweep moves when (a,b)(a, b) marked (full,right)(\mathrm{full}, \mathrm{right}) form a compatible skeleton pair, sending (a.wing(left),b.full(s,j,rdL,r))โ†’(a.full(s,j,rdL,r+ฮ”(CS,task⁡(a),j,a)),b.wing(right))(a.\mathrm{wing}(\mathrm{left}), b.\mathrm{full}(s, j, \mathrm{rd}_{\mathrm{L}}, r)) \to (a.\mathrm{full}(s, j, \mathrm{rd}_{\mathrm{L}}, r + \Delta(C_{S, \operatorname{task}(a), j}, a)), b.\mathrm{wing}(\mathrm{right})), (a.full(s,j,rdR,r),b.wing(right))โ†’(a.wing(left),b.full(s,j,rdR,r))(a.\mathrm{full}(s, j, \mathrm{rd}_{\mathrm{R}}, r), b.\mathrm{wing}(\mathrm{right})) \to (a.\mathrm{wing}(\mathrm{left}), b.\mathrm{full}(s, j, \mathrm{rd}_{\mathrm{R}}, r)), (a.wing(left),b.full(s,j,unL,r))โ†’(a.full(s,j,unL,r),b.wing(right))(a.\mathrm{wing}(\mathrm{left}), b.\mathrm{full}(s, j, \mathrm{un}_{\mathrm{L}}, r)) \to (a.\mathrm{full}(s, j, \mathrm{un}_{\mathrm{L}}, r), b.\mathrm{wing}(\mathrm{right})), and (a.full(s,j,unR,r),b.wing(right))โ†’(a.wing(left),b.full(s,j,unR,r+ฮ”(CS,task⁡(a),j,a)))(a.\mathrm{full}(s, j, \mathrm{un}_{\mathrm{R}}, r), b.\mathrm{wing}(\mathrm{right})) \to (a.\mathrm{wing}(\mathrm{left}), b.\mathrm{full}(s, j, \mathrm{un}_{\mathrm{R}}, r + \Delta(C_{S, \operatorname{task}(a), j}, a))); creating a checker head (a,b[ฯ‡โ†idle])โ†’(a,b[ฯ‡โ†head(x)])(a, b[\chi \leftarrow \mathrm{idle}]) \to (a, b[\chi \leftarrow \mathrm{head}(x)]) when pos⁡(a)=core(qโˆ’1)\operatorname{pos}(a) = \mathrm{core}(q - 1) and bb is in the palette; advancing (a[ฯ‡โ†head(x)],b[ฯ‡โ†idle])โ†’(a[ฯ‡โ†passed(x)],b[ฯ‡โ†head(x)])(a[\chi \leftarrow \mathrm{head}(x)], b[\chi \leftarrow \mathrm{idle}]) \to (a[\chi \leftarrow \mathrm{passed}(x)], b[\chi \leftarrow \mathrm{head}(x)]) when pos⁡(a)=pal(v)\operatorname{pos}(a) = \mathrm{pal}(v) with vโ‰ xv \neq x and bb is in the palette; and swapping (a,b)โ†’(b,a)(a, b) \to (b, a) when a,ba, b are head-free palette cells at positions x,yx, y satisfying a[palโ†y]=ba[\mathrm{pal} \leftarrow y] = b. Two cell words (u,w)(u, w) satisfy replacement for (S,d)(S, d) if every cell in uu and ww is formatted for (S,d)(S, d) and either u=[a],w=[b]u = [a], w = [b] are related in either direction by a unary transition or u=[a,b],w=[aโ€ฒ,bโ€ฒ]u = [a, b], w = [a', b'] are related in either direction by a binary transition. For any cell words pp and ss, a rewriting step sends pusp u s to pwsp w s whenever (u,w)(u, w) is a replacement, and cell-word reachability vโคณS,dwv \leadsto_{S, d} w is the reflexive transitive closure of rewriting steps.

A cell region โ„›\mathcal{R} of bound qq and data size dd consists of a positive size N>0N > 0, a task ฯ„\tau, and cells c0,โ€ฆ,cNโˆ’1c_0, \dots, c_{N - 1} of bound qq such that every cic_i satisfies task⁡(ci)=ฯ„\operatorname{task}(c_i) = \tau and payload formatting for dd, the skeleton of cic_i is initial if and only if i=0i = 0 and terminal if and only if i=Nโˆ’1i = N - 1, and every adjacent pair (ci,ci+1)(c_i, c_{i + 1}) has structurally adjacent and internally consistent skeletons. For a schedule SS, the induced head-tour plan P(โ„›,S)P(\mathcal{R}, S) has cnt⁡S(ฯ„)\operatorname{cnt}_S(\tau) clauses on NN positions and zero-task flag z(ฯ„)z(\tau), where the jj-th payload (j<cnt⁡S(ฯ„)j < \operatorname{cnt}_S(\tau)) has delta iโ†ฆฮ”(CS,ฯ„,j,ci)i \mapsto \Delta(C_{S, \tau, j}, c_i) and gate rโ†ฆ(ฮธS,ฯ„,j(r)=true)r \mapsto (\theta_{S, \tau, j}(r) = \mathrm{true}). Given a full tour state tโˆˆโ„ฑcnt⁡S(ฯ„),Nt \in \mathcal{F}_{\operatorname{cnt}_S(\tau), N}, write j(t),ฯ•(t),p(t)j(t), \phi(t), p(t) for the clause, phase, and position induced by ctrl⁡(t)\operatorname{ctrl}(t): when ctrl⁡(t)=(j,c)\operatorname{ctrl}(t) = (j, c), j(t)=jj(t) = j, ฯ•(t)\phi(t) is the phase corresponding to cc, and p(t)p(t) is the sweep index pp for read or undo sweeps and Nโˆ’1N - 1 otherwise; when ctrl⁡(t)=succ\operatorname{ctrl}(t) = \mathrm{succ}, j(t)=0j(t) = 0, ฯ•(t)=succ\phi(t) = \mathrm{succ}, and p(t)=Nโˆ’1p(t) = N - 1. The realized word ฯโ„›,S(t)\rho_{\mathcal{R}, S}(t) has length NN and ii-th cell ci.wing(left)c_i.\mathrm{wing}(\mathrm{left}) for i<p(t)i < p(t), ci.wing(right)c_i.\mathrm{wing}(\mathrm{right}) for i>p(t)i > p(t), and ci.full(side⁡(t),j(t),ฯ•(t),reg⁡(t))c_i.\mathrm{full}(\operatorname{side}(t), j(t), \phi(t), \operatorname{reg}(t)) for i=p(t)i = p(t).

A cell cc is semantically zero for SS, written ๐’ตS(c)\mathcal{Z}_S(c), if mrk⁡(c)=full\operatorname{mrk}(c) = \mathrm{full} and either ph⁡(c)โˆˆ{acq,fin,succ}\operatorname{ph}(c) \in \{\mathrm{acq}, \mathrm{fin}, \mathrm{succ}\} with reg⁡(c)โ‰ 0\operatorname{reg}(c) \neq 0, ph⁡(c)=ag\operatorname{ph}(c) = \mathrm{ag} with ฮธS,task⁡(c),cl⁡(c)(reg⁡(c))=false\theta_{S, \operatorname{task}(c), \operatorname{cl}(c)}(\operatorname{reg}(c)) = \mathrm{false}, or ph⁡(c)=succ\operatorname{ph}(c) = \mathrm{succ} with z(meta⁡(c))=truez(\operatorname{meta}(c)) = \mathrm{true}. A finite-table cell cc of bound qq is a unary zero for (S,d)(S, d) if cc fails formatting for (S,d)(S, d), ๐’ตS(c)\mathcal{Z}_S(c) holds, or pos⁡(c)=pal(x)\operatorname{pos}(c) = \mathrm{pal}(x) with ฯ‡c=passed(x)\chi_c = \mathrm{passed}(x) for some x<qx < q. A pair (a,b)(a, b) of cells is a binary zero if it is not a compatible cell pair, if pos⁡(a)=pos⁡(b)=pal(x)\operatorname{pos}(a) = \operatorname{pos}(b) = \mathrm{pal}(x) for some x<qx < q, or if pos⁡(a)=pal(x)\operatorname{pos}(a) = \mathrm{pal}(x), ฯ‡a=head(y)\chi_a = \mathrm{head}(y) for yโ‰ xy \neq x, and pos⁡(b)=stop\operatorname{pos}(b) = \mathrm{stop}.

Good Words and Pivots

Given a finite sequence f=(f0,โ€ฆ,fNโˆ’1)f = (f_0, \dots, f_{N - 1}) of cells of bound qq, a cut occurs at k<Nk < N if ฮพfk\xi_{f_k} is right-external; two indices i,j<Ni, j < N lie in the same region, written SameReg⁡f(i,j)\operatorname{SameReg}_f(i, j), when no cut occurs at any kk with min⁡(i,j)โ‰คk<max⁡(i,j)\min(i, j) \le k < \max(i, j). For a schedule SS, indices h<Nh < N and j<qj < q, and bound tโˆˆโ„•t \in \mathbb{N}, define the partial sum ฮฃS(f,h,j,t)=โˆ‘ฮ”(CS,task⁡(fh),j,fi)โˆˆ๐”ฝ23\Sigma_S(f, h, j, t) = \sum \Delta(C_{S, \operatorname{task}(f_h), j}, f_i) \in \mathbb{F}_2^3 over all i<min⁡(t,N)i < \min(t, N) satisfying SameReg⁡f(h,i)\operatorname{SameReg}_f(h, i), together with the total sum ฮฃtot(S,f,h,j)=ฮฃS(f,h,j,N)\Sigma_{\mathrm{tot}}(S, f, h, j) = \Sigma_S(f, h, j, N) and left sum ฮฃL(S,f,h,j)=ฮฃS(f,h,j,h)\Sigma_{\mathrm{L}}(S, f, h, j) = \Sigma_S(f, h, j, h). Clause j<qj < q holds for head hh in ff, written (S,f,h)โŠจj(S, f, h) \models j, if ฮธS,task⁡(fh),j(ฮฃtot(S,f,h,j))=true\theta_{S, \operatorname{task}(f_h), j}(\Sigma_{\mathrm{tot}}(S, f, h, j)) = \mathrm{true}. A phase ฯ•\phi has passed the gate when ฯ•โˆˆ{ag,unL,unR,fin}\phi \in \{\mathrm{ag}, \mathrm{un}_{\mathrm{L}}, \mathrm{un}_{\mathrm{R}}, \mathrm{fin}\}, and the register potential ฮ S(f,h,j,ฯ•)โˆˆ๐”ฝ23\Pi_S(f, h, j, \phi) \in \mathbb{F}_2^3 is given by ฮ S(f,h,j,ฯ•)={ฮฃtot(S,f,h,j)โˆ’ฮฃL(S,f,h,j),ฯ•=rdL,ฮฃtot(S,f,h,j)+ฮฃL(S,f,h,j),ฯ•=unR,ฮฃtot(S,f,h,j),ฯ•โˆˆ{rdR,bg,ag,unL},0,otherwise.\Pi_S(f, h, j, \phi) = \begin{cases} \Sigma_{\mathrm{tot}}(S, f, h, j) - \Sigma_{\mathrm{L}}(S, f, h, j), & \phi = \mathrm{rd}_{\mathrm{L}}, \\ \Sigma_{\mathrm{tot}}(S, f, h, j) + \Sigma_{\mathrm{L}}(S, f, h, j), & \phi = \mathrm{un}_{\mathrm{R}}, \\ \Sigma_{\mathrm{tot}}(S, f, h, j), & \phi \in \{\mathrm{rd}_{\mathrm{R}}, \mathrm{bg}, \mathrm{ag}, \mathrm{un}_{\mathrm{L}}\}, \\ 0, & \text{otherwise.} \end{cases}(1) A finite sequence f=(f0,โ€ฆ,fNโˆ’1)f = (f_0, \dots, f_{N - 1}) of cells of bound qq has a good head at h<Nh < N under SS, written ๐’ขS(f,h)\mathcal{G}_S(f, h), if reg⁡(fh)=ฮ S(f,h,cl⁡(fh),ph⁡(fh))\operatorname{reg}(f_h) = \Pi_S(f, h, \operatorname{cl}(f_h), \operatorname{ph}(f_h)) by (1) and either ph⁡(fh)=succ\operatorname{ph}(f_h) = \mathrm{succ} with (S,f,h)โŠจj(S, f, h) \models j for all j<cnt⁡S(task⁡(fh))j < \operatorname{cnt}_S(\operatorname{task}(f_h)), or ph⁡(fh)โ‰ succ\operatorname{ph}(f_h) \neq \mathrm{succ} with (S,f,h)โŠจj(S, f, h) \models j for all j<cl⁡(fh)j < \operatorname{cl}(f_h) and (S,f,h)โŠจcl⁡(fh)(S, f, h) \models \operatorname{cl}(f_h) whenever ph⁡(fh)\operatorname{ph}(f_h) has passed the gate. A finite sequence f=(f0,โ€ฆ,fNโˆ’1)f = (f_0, \dots, f_{N - 1}) of cells of bound qq is all-good under SS, written ๐’ขS(f)\mathcal{G}_S(f), if ๐’ขS(f,h)\mathcal{G}_S(f, h) holds for every h<Nh < N with mrk⁡(fh)=full\operatorname{mrk}(f_h) = \mathrm{full}; a cell word ww of length NN is good under SS, written ๐’ฒS(w)\mathcal{W}_S(w), if (w0,โ€ฆ,wNโˆ’1)(w_0, \dots, w_{N - 1}) is all-good under SS.

Two cell sequences f,fโ€ฒf, f' of length NN satisfy the pivot relation at index i<Ni < N, written fโ‹ˆifโ€ฒf \bowtie_i f', if there exist a cell aa and a side sโˆˆ๐”นs \in \mathbb{B} such that fi=a.full(s,0,succ,0)f_i = a.\mathrm{full}(s, 0, \mathrm{succ}, 0), fiโ€ฒ=a.full(ยฌs,0,succ,0)f'_i = a.\mathrm{full}(\neg s, 0, \mathrm{succ}, 0), fh=fhโ€ฒf_h = f'_h for all hโ‰ ih \neq i, the skeleton ฮพa\xi_a is terminal, and z(meta⁡(a))=falsez(\operatorname{meta}(a)) = \mathrm{false}.

Circuits, Tableaux, and Addressable Clauses

For a wire bound nโˆˆโ„•n \in \mathbb{N}, a circuit wire is an element of ๐”นโŠ•{0,โ€ฆ,nโˆ’1}\mathbb{B} \oplus \{0, \dots, n - 1\}; under an assignment v:{0,โ€ฆ,nโˆ’1}โ†’๐”นv : \{0, \dots, n - 1\} \to \mathbb{B}, a constant bit bโˆˆ๐”นb \in \mathbb{B} evaluates to bb and a wire index i<ni < n evaluates to v(i)v(i). A combinational not-and (NAND) circuit cc with II inputs and gg gates is an ordered sequence of gg two-input NAND gates built recursively from the empty circuit by appending gates whose two input wires lie in ๐”นโŠ•{0,โ€ฆ,I+kโˆ’1}\mathbb{B} \oplus \{0, \dots, I + k - 1\} at step k<gk < g.โœฆ On an input vector v:{0,โ€ฆ,Iโˆ’1}โ†’๐”นv : \{0, \dots, I - 1\} \to \mathbb{B}, circuit evaluation extends vv to ev⁡c(v):{0,โ€ฆ,I+gโˆ’1}โ†’๐”น\operatorname{ev}_c(v) : \{0, \dots, I + g - 1\} \to \mathbb{B} by assigning to each successive gate the NAND of its two input-wire evaluations.โœฆ A three-wire circuit clause over nn wires pairs three circuit wires (w0,w1,w2)(w_0, w_1, w_2) with a truth function ฮธ:๐”น3โ†’๐”น\theta : \mathbb{B}^3 \to \mathbb{B}; the defining clauses of cc form the list of 3g3g three-wire circuit clauses over I+gI + g wires obtained recursively by embedding earlier clauses and appending the three NAND constraint clauses for each new gate.

With bound qq, an addressable wire reading is an element of ๐”นโŠ•Addr⁡q\mathbb{B} \oplus \operatorname{Addr}_q, evaluating under v:Addr⁡qโ†’๐”นv : \operatorname{Addr}_q \to \mathbb{B} to bb on constant bโˆˆ๐”นb \in \mathbb{B} and to v(a)v(a) on address aโˆˆAddr⁡qa \in \operatorname{Addr}_q. A three-wire addressable clause C=(w,ฮธ)C = (w, \theta) consists of three addressable wire readings w:{0,1,2}โ†’๐”นโŠ•Addr⁡qw : \{0, 1, 2\} \to \mathbb{B} \oplus \operatorname{Addr}_q and a truth function ฮธ:๐”น3โ†’๐”น\theta : \mathbb{B}^3 \to \mathbb{B}; an assignment v:Addr⁡qโ†’๐”นv : \operatorname{Addr}_q \to \mathbb{B} satisfies CC, written vโŠจCv \models C, if applying ฮธ\theta to the evaluations of (w0,w1,w2)(w_0, w_1, w_2) under vv yields true\mathrm{true}. Writing ฯˆ:๐”ฝ2โ†’๐”น\psi : \mathbb{F}_2 \to \mathbb{B} for the conversion sending 11 to true\mathrm{true} and 00 to false\mathrm{false}, compiling CC produces a verification clause whose ii-th address is aa if wi=aโˆˆAddr⁡qw_i = a \in \operatorname{Addr}_q and cert(0)\mathrm{cert}(0) if wiw_i is constant, and whose truth function evaluates ฮธ\theta on the tuple taking constant wires to their fixed bits and addressed wires to ฯˆ(ri)\psi(r_i) for register rโˆˆ๐”ฝ23r \in \mathbb{F}_2^3.โœฆ Special addressable clauses include: the unit clause Cunit(w,b)C^{\mathrm{unit}}(w, b) on wires (w,w,w)(w, w, w) requiring v0=bv_0 = b; the equality clause Ceq(w,wโ€ฒ,i)C^{\mathrm{eq}}(w, w', i) (iโˆˆ{0,1}i \in \{0, 1\}) on wires (w,wโ€ฒ,w)(w, w', w) requiring ยฌv0โˆจv1\neg v_0 \lor v_1 for i=0i = 0 and v0โˆจยฌv1v_0 \lor \neg v_1 for i=1i = 1; and the circuit lift Cmlift(C0)C^{\mathrm{lift}}_m(C_0) along m:{0,โ€ฆ,nโˆ’1}โ†’Addr⁡qm : \{0, \dots, n - 1\} \to \operatorname{Addr}_q of a circuit clause C0C_0, mapping wire indices via mm and fixing constants. An addressable input bit is either a fixed bit bโˆˆ๐”นb \in \mathbb{B} or a data reference (p,neg)โˆˆ๐’Ÿqร—๐”น(p, \mathrm{neg}) \in \mathcal{D}_q \times \mathbb{B}; for reading ww and direction iโˆˆ{0,1}i \in \{0, 1\}, the initial-value constraint clause Cinit(w,u,i)C^{\mathrm{init}}(w, u, i) is Cunit(w,b)C^{\mathrm{unit}}(w, b) when uu is fixed bb, and on u=(p,neg)u = (p, \mathrm{neg}) is the three-wire clause on (w,data(p),w)(w, \mathrm{data}(p), w) enforcing ยฌv0โˆจx\neg v_0 \lor x for i=0i = 0 and v0โˆจยฌxv_0 \lor \neg x for i=1i = 1, where x=v1โŠ•negx = v_1 \oplus \mathrm{neg}.

For integers q,ฮฒ,g,T,Wq, \beta, g, T, W with ฮฒ>0\beta > 0, T>0T > 0, Wโ‰ฅ3W \ge 3, total certificate variable count ฮฒWT+g(Wโˆ’2)(Tโˆ’1)โ‰คq\beta W T + g(W - 2)(T - 1) \le q, and total tableau clause count M(ฮฒ,g,T,W)=2ฮฒW+2ฮฒ(Tโˆ’1)+(3g+2ฮฒ)(Wโˆ’2)(Tโˆ’1)+ฮฒโ‰คqM(\beta, g, T, W) = 2\beta W + 2\beta(T - 1) + (3g + 2\beta)(W - 2)(T - 1) + \beta \le q, a tableau layout LL specifies an origin column o<Wo < W. Enumerating the tape variables (t,j,r)(t, j, r) (t<T,j<W,r<ฮฒt < T, j < W, r < \beta) and gate variables (t,j,v)(t, j, v) (t<Tโˆ’1,j<Wโˆ’2,v<gt < T - 1, j < W - 2, v < g) injectively into {0,โ€ฆ,qโˆ’1}\{0, \dots, q - 1\} defines certificate addresses xL(t,j,r)x_L(t, j, r) and yL(t,j,v)y_L(t, j, v); for t<Tโˆ’1t < T - 1 and j<Wโˆ’2j < W - 2, the local circuit address map locL,t,j:{0,โ€ฆ,3ฮฒ+gโˆ’1}โ†’Addr⁡q\mathrm{loc}_{L, t, j} : \{0, \dots, 3\beta + g - 1\} \to \operatorname{Addr}_q sends input index ฮดฮฒ+r\delta \beta + r (ฮด<3,r<ฮฒ\delta < 3, r < \beta) to xL(t,j+ฮด,r)x_L(t, j + \delta, r) and gate index 3ฮฒ+v3\beta + v (v<gv < g) to yL(t,j,v)y_L(t, j, v). Given a NAND circuit cc with 3ฮฒ3\beta inputs and gg gates, output wires outr\mathrm{out}_r (r<ฮฒr < \beta), an initial row init:{0,โ€ฆ,Wโˆ’1}ร—{0,โ€ฆ,ฮฒโˆ’1}โ†’๐”นโŠ•(๐’Ÿqร—๐”น)\mathrm{init} : \{0, \dots, W - 1\} \times \{0, \dots, \beta - 1\} \to \mathbb{B} \oplus (\mathcal{D}_q \times \mathbb{B}), and vectors blank,accept:{0,โ€ฆ,ฮฒโˆ’1}โ†’๐”น\mathrm{blank}, \mathrm{accept} : \{0, \dots, \beta - 1\} \to \mathbb{B}, the indexed layout clause CL(c,out,init,blank,accept,i)C_L(c, \mathrm{out}, \mathrm{init}, \mathrm{blank}, \mathrm{accept}, i) for i<M(ฮฒ,g,T,W)i < M(\beta, g, T, W) enumerates four blocks of addressable clauses: the 2ฮฒW2\beta W initial constraints Cinit(xL(0,j,r),init(j,r),k)C^{\mathrm{init}}(x_L(0, j, r), \mathrm{init}(j, r), k) (kโˆˆ{0,1}k \in \{0, 1\}); the 2ฮฒ(Tโˆ’1)2\beta(T - 1) boundary constraints Cunit(xL(t+1,bโ€ฒ,r),blank(r))C^{\mathrm{unit}}(x_L(t + 1, b', r), \mathrm{blank}(r)) at columns bโ€ฒโˆˆ{0,Wโˆ’1}b' \in \{0, W - 1\}; the (3g+2ฮฒ)(Wโˆ’2)(Tโˆ’1)(3g + 2\beta)(W - 2)(T - 1) local transition clauses, comprising for each (t,j)(t, j) the 3g3g defining clauses of cc lifted by locL,t,j\mathrm{loc}_{L, t, j} and the 2ฮฒ2\beta equality constraints Ceq(xL(t+1,j+1,r),outrโ€ฒ,k)C^{\mathrm{eq}}(x_L(t + 1, j + 1, r), \mathrm{out}'_r, k) where outrโ€ฒ\mathrm{out}'_r relabels outr\mathrm{out}_r via locL,t,j\mathrm{loc}_{L, t, j}; and the ฮฒ\beta acceptance constraints Cunit(xL(Tโˆ’1,o,r),accept(r))C^{\mathrm{unit}}(x_L(T - 1, o, r), \mathrm{accept}(r)). For a task-indexed family initฯ„\mathrm{init}_\tau, the tableau schedule SL(c,out,init,blank,accept)S_L(c, \mathrm{out}, \mathrm{init}, \mathrm{blank}, \mathrm{accept}) has clause count M(ฮฒ,g,T,W)M(\beta, g, T, W) for every task and assigns to p<qp < q the compiled indexed layout clause for p<M(ฮฒ,g,T,W)p < M(\beta, g, T, W) and the compiled clause Cunit(true,true)C^{\mathrm{unit}}(\mathrm{true}, \mathrm{true}) otherwise. Given ฮฑ:๐’Ÿqโ†’๐”น\alpha : \mathcal{D}_q \to \mathbb{B} and ฮณ:{0,โ€ฆ,qโˆ’1}โ†’๐”น\gamma : \{0, \dots, q - 1\} \to \mathbb{B}, the assembled assignment [ฮฑ,ฮณ]:Addr⁡qโ†’๐”น[\alpha, \gamma] : \operatorname{Addr}_q \to \mathbb{B} sends data(s,b,p)\mathrm{data}(s, b, p) to ฮฑ(s,b,p)\alpha(s, b, p) and cert(p)\mathrm{cert}(p) to ฮณ(p)\gamma(p).

The Source Machine and the Raw Codec

A one-tape Turing machine over alphabet ฮ“\Gamma and state set ๐’ฌTM\mathcal{Q}_{\mathrm{TM}} has head motions left,stay,right\mathrm{left}, \mathrm{stay}, \mathrm{right}, commands (w,qโ€ฒ,ฮผ)โˆˆฮ“ร—๐’ฌTMร—{left,stay,right}(w, q', \mu) \in \Gamma \times \mathcal{Q}_{\mathrm{TM}} \times \{\mathrm{left}, \mathrm{stay}, \mathrm{right}\}, tape labels (sym,orig,hd)โˆˆฮ“ร—๐”นร—(๐’ฌTMโˆช{โŠฅ})(\mathrm{sym}, \mathrm{orig}, \mathrm{hd}) \in \Gamma \times \mathbb{B} \times (\mathcal{Q}_{\mathrm{TM}} \cup \{\bot\}), and a local transition updating each center label from its left, center, and right neighbors according to ฮด:๐’ฌTMร—ฮ“โ†’ฮ“ร—๐’ฌTMร—{left,stay,right}\delta : \mathcal{Q}_{\mathrm{TM}} \times \Gamma \to \Gamma \times \mathcal{Q}_{\mathrm{TM}} \times \{\mathrm{left}, \mathrm{stay}, \mathrm{right}\}: an active center head writes ww, keeps orig\mathrm{orig}, and retains head qโ€ฒq' only on stay\mathrm{stay}, whereas an absent center head preserves symbol and origin and adopts the next state from a left neighbor moving right (taking precedence over a right neighbor moving left) if present, remaining headless otherwise. A binary coding KcK_{\mathrm{c}} of width ฮฒ>0\beta > 0 encodes labels into ๐”นฮฒ\mathbb{B}^\beta with left-inverse decoding, lifting the neighborhood rule to a Boolean transition ๐”น3ฮฒโ†’๐”นฮฒ\mathbb{B}^{3\beta} \to \mathbb{B}^\beta; for finite ฮ“,๐’ฌTM\Gamma, \mathcal{Q}_{\mathrm{TM}}, the one-hot coding takes bit width equal to the cardinality of labels and sends each label to its standard basis vector (decoding off-image vectors to a fixed blank label with orig=false\mathrm{orig} = \mathrm{false} and absent head). A NAND-circuit realization of ฮด\delta under KcK_{\mathrm{c}} consists of a gate count gg, a NAND circuit with 3ฮฒ3\beta inputs and gg gates, and ฮฒ\beta output wires computing the lifted Boolean transition.โœฆ Given stack indices K0K_0, tokens ฮ“0\Gamma_0, and states ๐’ฌ0\mathcal{Q}_0, a stack machine program assigns to each state either a push (k,a,qโ€ฒ)(k, a, q'), a pop (k,qโ€ฒ:(ฮ“0โˆช{โŠฅ})โ†’๐’ฌ0)(k, q' : (\Gamma_0 \cup \{\bot\}) \to \mathcal{Q}_0), or halt; it compiles to a one-tape transition table on multi-track symbols ๐”นร—(K0โ†’(ฮ“0โˆช{โŠฅ}))\mathbb{B} \times (K_0 \to (\Gamma_0 \cup \{\bot\})) and five simulation modes (ready, push-find, pop-find, pop-read, and back) scanning right to the first empty slot on track kk to push or pop and returning left to the origin-marked cell.

Take stack register indices K={0,1}โˆช{โŠฅ}K = \{0, 1\} \cup \{\bot\} with source ksrc=1k_{\mathrm{src}} = 1 and destination kdst=0k_{\mathrm{dst}} = 0. Operating over stacks reg(k)\mathrm{reg}(k) (kโˆˆKk \in K), front\mathrm{front}, back\mathrm{back}, and pc\mathrm{pc}, with instruction token set Token⁡(K)\operatorname{Token}(K) consisting of push(k,b)\mathrm{push}(k, b), pop(k)\mathrm{pop}(k), halt(b)\mathrm{halt}(b), bit(b)\mathrm{bit}(b), tick\mathrm{tick}, sep\mathrm{sep}, and stop\mathrm{stop}, interpreter modes (skip\mathrm{skip}, opcode\mathrm{opcode}, target(u)\mathrm{target}(u) for target phase uโˆˆ{before-two,before-one,during,after}u \in \{\text{before-two}, \text{before-one}, \mathrm{during}, \mathrm{after}\}), and nine control states (reset\mathrm{reset}, restore\mathrm{restore}, pick\mathrm{pick}, read\mathrm{read}, remember\mathrm{remember}, push\mathrm{push}, pop\mathrm{pop}, save-target\text{save-target}, stopped\mathrm{stopped}), the universal stack interpreter transfers tokens between back\mathrm{back} and front\mathrm{front}, pops unary tick\mathrm{tick} counts from pc\mathrm{pc} to skip to an instruction, executes simulated pushes and pops on reg(k)\mathrm{reg}(k) entering target mode at during\mathrm{during} (on false), before-one\text{before-one} (on true), or before-two\text{before-two} (on empty), records ticks onto pc\mathrm{pc} during the target phase, and halts at stopped(b)\mathrm{stopped}(b). For finite KK, input packets belong to Token⁡(K)โˆช{โŠฅ}\operatorname{Token}(K) \cup \{\bot\} of cardinality ฯ‰(K)\omega(K), with one-hot bit representation and left-inverse packet decoding; the universal input decoder reverses bits from reg(ksrc)\mathrm{reg}(k_{\mathrm{src}}) to reg(kdst)\mathrm{reg}(k_{\mathrm{dst}}), skips a unary header, collects fixed-width packets onto back\mathrm{back} starting from the all-false initial collection state, and delegates to the universal interpreter. For nโˆˆโ„•n \in \mathbb{N}, write ฮป(n)\lambda(n) for 11 when n=0n = 0 and the binary bit length of nn otherwise, B(n)B(n) for the ฮป(n)\lambda(n) binary digits of nn (most to least significant), and E(n)=trueฮป(n)โ‹…falseโ‹…B(n)E(n) = \mathrm{true}^{\lambda(n)} \cdot \mathrm{false} \cdot B(n) for its prefix encoding. The program specialization encoding is wrap⁡(t0,v)=trueโ‹…E(|t0|)โ‹…t0โ‹…E(|v|)โ‹…v\operatorname{wrap}(t_0, v) = \mathrm{true} \cdot E(|t_0|) \cdot t_0 \cdot E(|v|) \cdot v, and the wrapped input machine peels off unary-prefixed header blocks (repeating on marker true\mathrm{true} and entering universal packet collection on false\mathrm{false}). Instantiating this wrapped machine at (ksrc,kdst)(k_{\mathrm{src}}, k_{\mathrm{dst}}) and compiling yields the timed tape alphabet ฮ“\Gamma, states ๐’ฌTM\mathcal{Q}_{\mathrm{TM}}, and transition table ฮด\delta, with blank symbol (origin false\mathrm{false}, empty tracks), origin symbol (origin true\mathrm{true}, empty tracks), bit symbol for bb (origin false\mathrm{false}, bit(b)\mathrm{bit}(b) on track reg(ksrc)\mathrm{reg}(k_{\mathrm{src}})), initial state (ready at reverse), halting state for bb, and output label (origin symbol, orig=true\mathrm{orig} = \mathrm{true}, halting state).

For d>0d > 0 with dโ‰คqd \le q, arity 1โ‰คlโ‰ค101 \le l \le 10, and flag Zโˆˆ๐”นZ \in \mathbb{B}, the input data sequence has length ldl d when Z=trueZ = \mathrm{true} and 2ld2 l d when Z=falseZ = \mathrm{false}, placing at index ii the unnegated data reference ((iโ‰ฅld),โŒŠi/dโŒ‹mod⁡l,imod⁡d)((i \ge l d),\, \lfloor i/d \rfloor \bmod l,\, i \bmod d), where (iโ‰ฅld)(i \ge l d) is true\mathrm{true} if iโ‰ฅldi \ge l d and false\mathrm{false} otherwise; for Boolean list aa and 10000Hโ‰คq10000 H \le q (H>0H > 0), the source input sequence prepends the fixed bits E(|a|)โ‹…aโ‹…E(H)โ‹…E(l)โ‹…[Z]E(|a|) \cdot a \cdot E(H) \cdot E(l) \cdot [Z] to the input data sequence. Given f:๐”นโ†’๐”นf : \mathbb{B} \to \mathbb{B}, transforming an input bit sends fixed bb to fixed f(b)f(b) and sends (p,neg)(p, \mathrm{neg}) to fixed f(false)f(\mathrm{false}) if f(false)=f(true)f(\mathrm{false}) = f(\mathrm{true}) and to (p,negโŠ•f(false))(p, \mathrm{neg} \oplus f(\mathrm{false})) otherwise; for vectors blank,orig:{0,โ€ฆ,ฮฒโˆ’1}โ†’๐”น\mathrm{blank}, \mathrm{orig} : \{0, \dots, \beta - 1\} \to \mathbb{B}, encoding sym:๐”นโ†’๐”นฮฒ\mathrm{sym} : \mathbb{B} \to \mathbb{B}^\beta, origin oo, and input list in\mathrm{in}, the initial row places fixed orig(r)\mathrm{orig}(r) at column oo, transforms injโˆ’oโˆ’1\mathrm{in}_{j - o - 1} by bโ†ฆsym(b)(r)b \mapsto \mathrm{sym}(b)(r) when o<jo < j and jโˆ’oโˆ’1<|in|j - o - 1 < |\mathrm{in}|, and places fixed blank(r)\mathrm{blank}(r) elsewhere. Let ฮฒ\beta be the bit width of the one-hot coding of the timed tape machine, let csrcc_{\mathrm{src}} with gg gates and output wires outsrc\mathrm{out}_{\mathrm{src}} be a NAND-circuit realization of ฮด\delta, and write blank0\mathrm{blank}_0, init0\mathrm{init}_0, acc0\mathrm{acc}_0, and bit0(b)\mathrm{bit}_0(b) for the one-hot encodings of the blank, initial, accepting-output, and bit labels. For parameters ฮฒ,g,D,h,n\beta, g, D, h, n, setting T=2โŒŠh/5โŒ‹T = 2^{\lfloor h/5 \rfloor} and W=4TW = 4T, the layout parameter bounds โ„ฌ(ฮฒ,g,D,h,n)\mathcal{B}(\beta, g, D, h, n) require: 64h+512โ‰ค10000h,10โ‰ค22h,2hโ‰ค22h,10000Dhโ‰ค2h,ฮฒWT+g(Wโˆ’2)(Tโˆ’1)โ‰ค2h,M(ฮฒ,g,T,W)โ‰ค2h,n+2ฮป(n)+2ฮป(Dh)+12+20(10000Dh)<โŒŠT/4โŒ‹.\begin{aligned} &64h + 512 \le 10000h, \quad 10 \le 2^{2h}, \quad 2^h \le 2^{2h}, \quad 10000 D h \le 2^h, \\ &\beta W T + g(W - 2)(T - 1) \le 2^h, \quad M(\beta, g, T, W) \le 2^h, \\ &n + 2\lambda(n) + 2\lambda(D h) + 12 + 20(10000 D h) < \lfloor T/4 \rfloor. \end{aligned}(2) Whenever (2) holds for (ฮฒ,g,D,h,|a|)(\beta, g, D, h, |a|) with 10000Dh>010000 D h > 0, the source layout Lsrc(h,|a|,D)L_{\mathrm{src}}(h, |a|, D) takes capacity 2h2^h, time TT, width WW, and origin 2T2T; the source initial row Isrc(a,D,h,ฯ„)I_{\mathrm{src}}(a, D, h, \tau) applies the initial-row rule at origin 2T2T with blank0\mathrm{blank}_0, init0\mathrm{init}_0, bit0\mathrm{bit}_0, and the source input sequence for aa, H=DhH = D h, l=ar⁡(ฯ„)+1l = \operatorname{ar}(\tau) + 1, and Z=z(ฯ„)Z = z(\tau); and the source schedule Ssrc(a,D,h)S_{\mathrm{src}}(a, D, h) is the tableau schedule of Lsrc(h,|a|,D)L_{\mathrm{src}}(h, |a|, D) for csrcc_{\mathrm{src}}, outsrc\mathrm{out}_{\mathrm{src}}, Isrc(a,D,h,โ‹…)I_{\mathrm{src}}(a, D, h, \cdot), blank0\mathrm{blank}_0, and acc0\mathrm{acc}_0. Write Ci(a,D,h,ฯ„)C_i(a, D, h, \tau) for the addressable indexed layout clause CLsrc(h,|a|,D)(csrc,outsrc,Isrc(a,D,h,ฯ„),blank0,acc0,i)C_{L_{\mathrm{src}}(h, |a|, D)}(c_{\mathrm{src}}, \mathrm{out}_{\mathrm{src}}, I_{\mathrm{src}}(a, D, h, \tau), \mathrm{blank}_0, \mathrm{acc}_0, i) (i<M(ฮฒ,g,T,W)i < M(\beta, g, T, W)).

For a height h>0h > 0, a raw bitstring is a vector in ๐”น10000h\mathbb{B}^{10000 h}.โœฆ Cell encoding maps a cell cc of capacity 2h2^h to a raw bitstring by packing 3232 natural-number slots in 2h2h-bit little-endian binary at indices 0,โ€ฆ,64hโˆ’10, \dots, 64h - 1 (slots 00 through 88 storing position tag and coordinate, marker tag, arity, block, checker tag and sought color, head clause, and head phase tag, and remaining slots 00) followed at indices 64h,โ€ฆ,64h+51164h, \dots, 64h + 511 by 512512 Boolean flags (indices 00 through 77 storing z(meta⁡(c))z(\operatorname{meta}(c)), side⁡(c)\operatorname{side}(c), ฯˆโˆ’1(dc(false))\psi^{-1}(d_c(\mathrm{false})), ฯˆโˆ’1(dc(true))\psi^{-1}(d_c(\mathrm{true})), ฯˆโˆ’1(ฮถc)\psi^{-1}(\zeta_c), and the three bits of ฯˆโˆ’1(reg⁡(c))\psi^{-1}(\operatorname{reg}(c)), and remaining flags false\mathrm{false}) and false\mathrm{false} thereafter. When all tags and bounded indices lie in range, cell decoding parses these slots and flags into a cell cc and accepts cc only if encoding cc recovers the raw bitstring; word decoding decodes a finite word of raw bitstrings letterwise, failing if any letter fails to decode. Given 10000Hโ‰คq10000 H \le q, lโ‰ค10l \le 10, ฮฑ:๐’Ÿqโ†’๐”น\alpha : \mathcal{D}_q \to \mathbb{B}, and bโˆˆ๐”นb \in \mathbb{B}, the candidate word list U(ฮฑ,H,l,b)U(\alpha, H, l, b) consists of the ll raw bitstrings at height HH whose ii-th word (i<li < l) has jj-th bit ฮฑ(b,i,j)\alpha(b, i, j) (j<10000Hj < 10000 H). For h>0h > 0, schedule SS of bound 2h2^h, and data size dd, a raw bitstring satisfies raw unary zero if it fails to decode or decodes to a unary zero for (S,d)(S, d); two raw bitstrings satisfy raw binary zero if both decode to a binary zero pair; a raw word vv satisfies raw zero if v=[a]v = [a] with aa a raw unary zero or v=[a,b]v = [a, b] with (a,b)(a, b) a raw binary zero; and two raw words (v,w)(v, w) satisfy raw replacement if they decode to cell words related by replacement for (S,d)(S, d). For zโˆˆ๐”นz \in \mathbb{B}, the raw table entry Eh(S,d,z,v,w)โˆˆ๐”นE_h(S, d, z, v, w) \in \mathbb{B} is true\mathrm{true} if and only if either z=truez = \mathrm{true}, ww is empty, and vv satisfies raw zero, or z=falsez = \mathrm{false} and (v,w)(v, w) satisfies raw replacement.

The Claim

Theorem 1. Let Q=({ฯ€j}j=0mโˆ’1,zQ)Q = (\{\pi_j\}_{j = 0}^{m - 1}, z_Q) be a head-tour plan of m>0m > 0 clauses on N>0N > 0 positions, and let sโˆˆ๐”นs \in \mathbb{B}. Then QQ-reachability of the success state satisfies (3): ฮน0(acq,0,s)โˆผQ(succ,0,s)โ‡”โˆ€jโˆˆ{0,โ€ฆ,mโˆ’1},QโŠจj.\iota_0(\mathrm{acq}, 0, s) \sim_Q (\mathrm{succ}, 0, s) \iff \forall j \in \{0, \dots, m - 1\},\ Q \models j.(3)โœฆ

If a full tour state tt satisfies ฮน0(acq,0,s)โˆผQt\iota_0(\mathrm{acq}, 0, s) \sim_Q t and ๐’ตQ(t)\mathcal{Z}_Q(t), then (4) holds: ctrl⁡(t)=succ,zQ=true,reg⁡(t)=0,andโˆ€jโˆˆ{0,โ€ฆ,mโˆ’1},QโŠจj.\operatorname{ctrl}(t) = \mathrm{succ}, \qquad z_Q = \mathrm{true}, \qquad \operatorname{reg}(t) = 0, \qquad \text{and} \qquad \forall j \in \{0, \dots, m - 1\},\ Q \models j.(4)โœฆ

Let SS be a verification clause schedule of bound qโˆˆโ„•q \in \mathbb{N}, let dโˆˆโ„•d \in \mathbb{N}, and let โ„›\mathcal{R} be a cell region of bound qq and data size dd with task ฯ„\tau. If bโˆˆ๐”นb \in \mathbb{B} satisfies b=falseb = \mathrm{false} whenever z(ฯ„)=truez(\tau) = \mathrm{true}, and P(โ„›,S)โŠจjP(\mathcal{R}, S) \models j for every j<cnt⁡S(ฯ„)j < \operatorname{cnt}_S(\tau), then the realized cell words satisfy (5): ฯโ„›,S(ฮน0(acq,0,b))โคณS,dฯโ„›,S(succ,0,b).\rho_{\mathcal{R}, S}(\iota_0(\mathrm{acq}, 0, b)) \leadsto_{S, d} \rho_{\mathcal{R}, S}(\mathrm{succ}, 0, b).(5)โœฆ

If vv and ww are cell words of bound qq such that ๐’ฑS,d(v)\mathcal{V}_{S, d}(v) and vโคณS,dwv \leadsto_{S, d} w, then (6) holds: ๐’ฒS(v)โ‡”๐’ฒS(w).\mathcal{W}_S(v) \iff \mathcal{W}_S(w).(6)โœฆ

For any sequence f=(f0,โ€ฆ,fNโˆ’1)f = (f_0, \dots, f_{N - 1}) of NN cells of bound qq and any index i<Ni < N, if ๐’ขS(f,i)\mathcal{G}_S(f, i) and ๐’ตS(fi)\mathcal{Z}_S(f_i) hold, then (7) holds: ph⁡(fi)=succ,z(meta⁡(fi))=true,reg⁡(fi)=0,andโˆ€j<cnt⁡S(task⁡(fi)),(S,f,i)โŠจj.\operatorname{ph}(f_i) = \mathrm{succ}, \quad z(\operatorname{meta}(f_i)) = \mathrm{true}, \quad \operatorname{reg}(f_i) = 0, \quad \text{and} \quad \forall j < \operatorname{cnt}_S(\operatorname{task}(f_i)),\ (S, f, i) \models j.(7)โœฆ

If ff and fโ€ฒf' are sequences of NN cells of bound qq such that ๐’ขS(f)\mathcal{G}_S(f) and fโ‹ˆifโ€ฒf \bowtie_i f' hold for some i<Ni < N, then (8) holds: z(meta⁡(fi))=falseandโˆ€j<cnt⁡S(task⁡(fi)),(S,f,i)โŠจj.z(\operatorname{meta}(f_i)) = \mathrm{false} \qquad \text{and} \qquad \forall j < \operatorname{cnt}_S(\operatorname{task}(f_i)),\ (S, f, i) \models j.(8)โœฆ

Fix an integer Dโ‰ฅ2D \ge 2. There exist a finite Boolean word t0t_0 and an integer h0โ‰ฅ4h_0 \ge 4 such that, for every integer hโ‰ฅh0h \ge h_0 with a=wrap⁡(t0,t0)a = \operatorname{wrap}(t_0, t_0), the layout parameter bounds (2) hold for (ฮฒ,g,D,h,|a|)(\beta, g, D, h, |a|) and (ฮฒ,g,D,Dh,|a|)(\beta, g, D, D h, |a|), and for every task ฯ„\tau and data assignment ฮฑ:๐’Ÿ2hโ†’๐”น\alpha : \mathcal{D}_{2^h} \to \mathbb{B}, setting WL=U(ฮฑ,Dh,ar⁡(ฯ„)+1,false)W_{\mathrm{L}} = U(\alpha, D h, \operatorname{ar}(\tau) + 1, \mathrm{false}) and letting WRW_{\mathrm{R}} be empty when z(ฯ„)=truez(\tau) = \mathrm{true} and U(ฮฑ,Dh,ar⁡(ฯ„)+1,true)U(\alpha, D h, \operatorname{ar}(\tau) + 1, \mathrm{true}) otherwise, (9) holds: (โˆƒฮณ:{0,โ€ฆ,2hโˆ’1}โ†’๐”น,โˆ€i<M(ฮฒ,g,2โŒŠh/5โŒ‹,4โ‹…2โŒŠh/5โŒ‹),[ฮฑ,ฮณ]โŠจCi(a,D,h,ฯ„))โ‡”EDh(Ssrc(a,D,Dh),10000D2h,z(ฯ„),WL,WR)=true.\begin{aligned} &\bigl(\exists \gamma : \{0, \dots, 2^h - 1\} \to \mathbb{B},\ \forall i < M(\beta, g, 2^{\lfloor h/5 \rfloor}, 4 \cdot 2^{\lfloor h/5 \rfloor}),\ [\alpha, \gamma] \models C_i(a, D, h, \tau)\bigr) \\ &\qquad \iff E_{D h}\bigl(S_{\mathrm{src}}(a, D, D h),\, 10000 D^2 h,\, z(\tau),\, W_{\mathrm{L}},\, W_{\mathrm{R}}\bigr) = \mathrm{true}. \end{aligned}(9)โœฆ

In the paper, the result reads: fixing the data slots and certificate of a complete syntactically admissible transaction region, and using only full-head control moves starting at the first-clause acquisition state (denoted A1A_1 in the paper, standing for ฮน0(acq,0,s)\iota_0(\mathrm{acq}, 0, s) for a side sโˆˆ๐”นs \in \mathbb{B}) with zero registers, a full head can reach success precisely when every clause is true on those fixed bits; no such path reaches a format, nonblank-register, or false-after-gate zero; and after a replacement success changes the committed side, verification can be reversed to the acquisition interface.

What Is Checked

Claims (3) and (4) are stated over any head-tour plan QQ of m>0m > 0 clauses on N>0N > 0 positions, Boolean side ss, and reachable full tour state tt; claim (5) is stated over a verification clause schedule SS of bound qq, data size dd, cell region โ„›\mathcal{R}, and side bb; claims (6), (7), and (8) are stated over a schedule SS, data size dd, cell words v,wv, w with vโคณS,dwv \leadsto_{S, d} w, and finite cell sequences f,fโ€ฒf, f'; and claim (9) is stated over any dilation Dโ‰ฅ2D \ge 2, tasks ฯ„\tau, data assignments on ๐’Ÿ2h\mathcal{D}_{2^h}, and the source-machine tableau layouts, schedules, and raw codec bounded by (2). For those constructions, the packet width ฯ‰(K)\omega(K) of any finite register index set KK, the one-hot tape-label bit width ฮฒ\beta, and the clause count M(ฮฒ,g,T,W)M(\beta, g, T, W) of any tableau layout of time TT and width WW are positive; the one-hot coding is left-invertible on every label; and every one-tape transition table admits a combinational NAND-circuit realization.