OctoInformBeta

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

Lemma 2.8: Bounds in a parameter qq on surviving palette words, surviving cut-free words, and surviving words cut-free after their first cell

Length bounds for surviving palette or cut-free 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 local computation cells evolving under local single-cell and adjacent-pair rewriting rules, where each cell carries a block position, a color-checking state, ๐”ฝ2\mathbb{F}_2-valued data and certificate bits, and a reading head executing a schedule of three-bit clauses. A word survives if no rewriting sequence exposes a forbidden one-cell or two-cell zero pattern. How is the length of a surviving word bounded in terms of a position parameter qโˆˆโ„•q \in \mathbb{N} when all cells lie in the palette, when cut cells are absent, or when no cut cell appears after the first cell?

Block Skeletons and Palette Checkers

For each parameter qโˆˆโ„•q \in \mathbb{N}, write Cq={xโˆˆโ„•:x<q}C_q = \{x \in \mathbb{N} : x < q\}. A block cell position of parameter qq is one of three kinds: a core position core(p)\mathrm{core}(p) indexed by pโˆˆCqp \in C_q, a palette position palette(a)\mathrm{palette}(a) carrying a color aโˆˆCqa \in C_q, or the terminal stop position stop\mathrm{stop}.โœฆ A cell marker is one of five syntactic tags: idle\mathrm{idle}, left\mathrm{left} (left wing), boundary\mathrm{boundary}, full\mathrm{full} (full active head), or right\mathrm{right} (right wing).โœฆ For an arity bound kโˆˆโ„•k \in \mathbb{N}, a block metadata triple is a triple (ฮฑ,z,ฮฒ)(\alpha, z, \beta) consisting of an arity ฮฑโˆˆCk\alpha \in C_k, a Boolean zero-task flag zโˆˆ{false,true}z \in \{\mathrm{false}, \mathrm{true}\}, and a block index ฮฒโˆˆโ„•\beta \in \mathbb{N} with ฮฒโ‰คฮฑ\beta \le \alpha.โœฆ For q,kโˆˆโ„•q, k \in \mathbb{N}, a cell syntactic skeleton ss of parameters qq and kk is a triple (pos(s),marker(s),meta(s))(\mathrm{pos}(s), \mathrm{marker}(s), \mathrm{meta}(s)) consisting of a block cell position pos(s)\mathrm{pos}(s) of parameter qq, a cell marker marker(s)\mathrm{marker}(s), and a block metadata triple meta(s)\mathrm{meta}(s) of arity bound kk.โœฆ Given a cell syntactic skeleton ss and a cell marker mm, the marked skeleton mark(s,m)\mathrm{mark}(s, m) is the skeleton (pos(s),m,meta(s))(\mathrm{pos}(s), m, \mathrm{meta}(s)) obtained by replacing marker(s)\mathrm{marker}(s) with mm while keeping pos(s)\mathrm{pos}(s) and meta(s)\mathrm{meta}(s) unchanged.โœฆ

A cell syntactic skeleton ss of parameters qq and kk with metadata (ฮฑ,z,ฮฒ)=meta(s)(\alpha, z, \beta) = \mathrm{meta}(s) is initial if ฮฒ=0\beta = 0 and pos(s)=core(0)\mathrm{pos}(s) = \mathrm{core}(0), and terminal if ฮฒ=ฮฑ\beta = \alpha and pos(s)=stop\mathrm{pos}(s) = \mathrm{stop}. A cell syntactic skeleton ss of parameters qq and kk carries an active head marker if marker(s)โˆˆ{boundary,full}\mathrm{marker}(s) \in \{\mathrm{boundary}, \mathrm{full}\}.โœฆ An admissible cell syntactic skeleton ss of parameters qq and kk is a cell syntactic skeleton of parameters qq and kk that satisfies marker(s)โ‰ right\mathrm{marker}(s) \neq \mathrm{right} whenever ss is initial and marker(s)โ‰ left\mathrm{marker}(s) \neq \mathrm{left} whenever ss is terminal.โœฆ

Two cell syntactic skeletons aa and bb of parameters qq and kk satisfy structural position adjacency if (pos(a),pos(b))(\mathrm{pos}(a), \mathrm{pos}(b)) is one of five configurations for some indices p,r,c,cโ€ฒโˆˆCqp, r, c, c' \in C_q: (core(p),core(r))(\mathrm{core}(p), \mathrm{core}(r)) with p+1=rp + 1 = r, (core(p),palette(c))(\mathrm{core}(p), \mathrm{palette}(c)) with p+1=qp + 1 = q, (palette(c),palette(cโ€ฒ))(\mathrm{palette}(c), \mathrm{palette}(c')), (palette(c),stop)(\mathrm{palette}(c), \mathrm{stop}), or (stop,core(0))(\mathrm{stop}, \mathrm{core}(0)).โœฆ A cell syntactic skeleton ss of parameters qq and kk accepts a cell marker mm on the left if mโˆˆ{full,right}m \in \{\mathrm{full}, \mathrm{right}\} when marker(s)=right\mathrm{marker}(s) = \mathrm{right} and m=leftm = \mathrm{left} otherwise.โœฆ For parameters qq and kk, a cell syntactic skeleton ss accepts a cell marker mm on the right if mโˆˆ{left,boundary,full}whenmarker(s)=leftm \in \{\mathrm{left}, \mathrm{boundary}, \mathrm{full}\} when \mathrm{marker}(s) = \mathrm{left} and m=rightm = \mathrm{right} otherwise.โœฆ A cell syntactic skeleton ss of parameters qq and kk is left-external if marker(s)=idle\mathrm{marker}(s) = \mathrm{idle} or if marker(s)โ‰ right\mathrm{marker}(s) \neq \mathrm{right} and ss is initialโœฆ, and right-external if marker(s)โˆˆ{idle,boundary}\mathrm{marker}(s) \in \{\mathrm{idle}, \mathrm{boundary}\} or if marker(s)โ‰ left\mathrm{marker}(s) \neq \mathrm{left} and ss is terminal.โœฆ Given two cell syntactic skeletons aa and bb of parameters qq and kk with metadata (ฮฑa,za,ฮฒa)=meta(a)(\alpha_a, z_a, \beta_a) = \mathrm{meta}(a) and (ฮฑb,zb,ฮฒb)=meta(b)(\alpha_b, z_b, \beta_b) = \mathrm{meta}(b), they satisfy internal skeleton consistency if ฮฑa=ฮฑb\alpha_a = \alpha_b, za=zbz_a = z_b, ฮฒa+1=ฮฒb\beta_a + 1 = \beta_b when pos(a)=stop\mathrm{pos}(a) = \mathrm{stop} and ฮฒa=ฮฒb\beta_a = \beta_b otherwise, bb is not initial, and aa is not terminal.โœฆ Two cell syntactic skeletons aa and bb of parameters qq and kk form a compatible adjacent skeleton pair if they satisfy structural position adjacency and either aa is right-external and bb is left-external, or aa is not right-external, bb is not left-external, aa accepts marker(b)\mathrm{marker}(b) on the right, bb accepts marker(a)\mathrm{marker}(a) on the left, and (a,b)(a, b) satisfies internal skeleton consistency.โœฆ

Over an arbitrary color set CC, a palette checker state is either idle\mathrm{idle}, passed(x)\mathrm{passed}(x) seeking a color xโˆˆCx \in C, or an active head head(x)\mathrm{head}(x) seeking xโˆˆCx \in C.โœฆ A palette checker state ฯ‡\chi over CC 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 palette checker states (ฯ‡1,ฯ‡2)(\chi_1, \chi_2) over CC form a compatible adjacent 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.โœฆ

Clauses, Schedules, and Finite Table Cells

For a parameter qโˆˆโ„•q \in \mathbb{N}, a cell memory address in Addrq\mathrm{Addr}_q 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 pโˆˆCqp \in C_q, or a certificate address cert(p)\mathrm{cert}(p) specified by pโˆˆCqp \in C_q.โœฆ A three-bit register state rโˆˆRegr \in \mathrm{Reg} is a function r:{0,1,2}โ†’๐”ฝ2r : \{0, 1, 2\} \to \mathbb{F}_2.โœฆ A verification task is a pair (ฮฑ,z)(\alpha, z) consisting of an arity ฮฑโˆˆ{0,โ€ฆ,9}\alpha \in \{0, \dots, 9\} and a Boolean zero-task flag zโˆˆ{false,true}z \in \{\mathrm{false}, \mathrm{true}\}.โœฆ For qโˆˆโ„•q \in \mathbb{N}, a verification clause CC of parameter qq is a pair (addrC,truthC)(\mathrm{addr}_C, \mathrm{truth}_C) consisting of a triple of cell memory addresses 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 clause schedule SS of parameter qq specifies for each verification task tt a positive clause count 1โ‰คmS(t)โ‰คq1 \le m_S(t) \le q, together with a verification clause CS(t,j)C_S(t, j) of parameter qq for every task tt and every clause index jโˆˆCqj \in C_q.โœฆ

A head computation phase is one of nine stages: acquisition\mathrm{acquisition}, read-left\text{read-left}, read-right\text{read-right}, before-gate\text{before-gate}, after-gate\text{after-gate}, undo-left\text{undo-left}, undo-right\text{undo-right}, finish\mathrm{finish}, or success\mathrm{success}โœฆ; a head computation phase pp satisfies the endpoint phase condition if pโˆˆ{acquisition,before-gate,after-gate,finish,success}p \in \{\mathrm{acquisition}, \text{before-gate}, \text{after-gate}, \mathrm{finish}, \mathrm{success}\}.โœฆ For qโˆˆโ„•q \in \mathbb{N}, a reading head state of parameter qq is a quadruple (s,j,p,r)(s, j, p, r) consisting of a Boolean side sโˆˆ{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, a clause index jโˆˆCqj \in C_q, a head computation phase pp, and a three-bit register state rโˆˆRegr \in \mathrm{Reg}โœฆ, and the default head state h0h_0 is (false,0,acquisition,0)(\mathrm{false}, 0, \mathrm{acquisition}, 0) (with 00 denoting clause index 00 and the zero register in the second and fourth coordinates).โœฆ A cell arity metadata triple is a block metadata triple of arity bound 1010.โœฆ The task projection task\mathrm{task} is the map sending a cell arity metadata triple m=(ฮฑ,z,ฮฒ)m = (\alpha, z, \beta) to the verification task task(m)=(ฮฑ,z)\mathrm{task}(m) = (\alpha, z), and the default cell metadata m0m_0 is the cell arity metadata triple (0,false,0)(0, \mathrm{false}, 0).

For qโˆˆโ„•q \in \mathbb{N}, a finite table cell cโˆˆ๐’žqc \in \mathcal{C}_q of parameter qq is a five-tuple (skel(c),chk(c),Dc,ฮณc,hc)(\mathrm{skel}(c), \mathrm{chk}(c), D_c, \gamma_c, h_c) consisting of a cell syntactic skeleton skel(c)\mathrm{skel}(c) of position parameter qq and arity bound 1010, a palette checker state chk(c)\mathrm{chk}(c) over CqC_q, a data bit function Dc:{false,true}โ†’๐”ฝ2D_c : \{\mathrm{false}, \mathrm{true}\} \to \mathbb{F}_2, a certificate bit ฮณcโˆˆ๐”ฝ2\gamma_c \in \mathbb{F}_2, and a reading head state hch_c of parameter qq.โœฆ The position pos(c)\mathrm{pos}(c), marker marker(c)\mathrm{marker}(c), and metadata meta(c)\mathrm{meta}(c) of a finite table cell cโˆˆ๐’žqc \in \mathcal{C}_q are those of skel(c)\mathrm{skel}(c), and its task is task(meta(c))\mathrm{task}(\mathrm{meta}(c)). A cell cโˆˆ๐’žqc \in \mathcal{C}_q lies in the core if pos(c)=core(p)\mathrm{pos}(c) = \mathrm{core}(p) for some pโˆˆCqp \in C_qโœฆ, and lies in the palette if pos(c)=palette(a)\mathrm{pos}(c) = \mathrm{palette}(a) for some aโˆˆCqa \in C_q.โœฆ A cut cell of parameter qq is a cell cโˆˆ๐’žqc \in \mathcal{C}_q such that pos(c)=core(0)\mathrm{pos}(c) = \mathrm{core}(0) and either marker(c)=idle\mathrm{marker}(c) = \mathrm{idle} or the block index of meta(c)\mathrm{meta}(c) equals 00.โœฆ A cell cโˆˆ๐’žqc \in \mathcal{C}_q 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โˆˆCqx \in C_q.โœฆ

For a cell cโˆˆ๐’žqc \in \mathcal{C}_q and an address aโˆˆAddrqa \in \mathrm{Addr}_q, the read bit read(a,c)โˆˆ๐”ฝ2\mathrm{read}(a, c) \in \mathbb{F}_2 is Dc(s)D_c(s) if a=data(s,b,p)a = \mathrm{data}(s, b, p), pos(c)=core(p)\mathrm{pos}(c) = \mathrm{core}(p), and the block index of meta(c)\mathrm{meta}(c) equals bb; ฮณc\gamma_c if a=cert(p)a = \mathrm{cert}(p), pos(c)=core(p)\mathrm{pos}(c) = \mathrm{core}(p), and the block index of meta(c)\mathrm{meta}(c) equals 00; and 00 otherwise.โœฆ Given a verification clause CC and a cell cโˆˆ๐’žqc \in \mathcal{C}_q, the clause register delta ฮด(C,c)โˆˆReg\delta(C, c) \in \mathrm{Reg} is the three-bit register state given 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).โœฆ

Given a finite table cell cโˆˆ๐’žqc \in \mathcal{C}_q and a Boolean side uโˆˆ{false,true}u \in \{\mathrm{false}, \mathrm{true}\}, the idle cell idle(c,u)\mathrm{idle}(c, u) is the cell with position pos(c)\mathrm{pos}(c), checker chk(c)\mathrm{chk}(c), marker idle\mathrm{idle}, metadata m0m_0, certificate bit 00, head state h0h_0, and data function given at sโˆˆ{false,true}s \in \{\mathrm{false}, \mathrm{true}\} by 00 when s=trues = \mathrm{true} and Dc(u)D_c(u) when s=falses = \mathrm{false}.โœฆ For a cell cโˆˆ๐’žqc \in \mathcal{C}_q and a side sโˆˆ{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, the boundary cell boundary(c,s)\mathrm{boundary}(c, s) is the cell obtained by replacing skel(c)\mathrm{skel}(c) with mark(skel(c),boundary)\mathrm{mark}(\mathrm{skel}(c), \mathrm{boundary}) and hch_c with (s,0,acquisition,0)(s, 0, \mathrm{acquisition}, 0), leaving chk(c)\mathrm{chk}(c), DcD_c, and ฮณc\gamma_c unchanged.โœฆ The wing cell wing(c,m)\mathrm{wing}(c, m) of a cell cโˆˆ๐’žqc \in \mathcal{C}_q and a cell marker mm is the cell obtained by replacing skel(c)\mathrm{skel}(c) with mark(skel(c),m)\mathrm{mark}(\mathrm{skel}(c), m) and hch_c with h0h_0, leaving chk(c)\mathrm{chk}(c), DcD_c, and ฮณc\gamma_c unchanged.โœฆ For a cell cโˆˆ๐’žqc \in \mathcal{C}_q, a side sโˆˆ{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, a clause index jโˆˆCqj \in C_q, a head computation phase pp, and a register state rโˆˆRegr \in \mathrm{Reg}, the full cell full(c,s,j,p,r)\mathrm{full}(c, s, j, p, r) is the cell obtained by replacing skel(c)\mathrm{skel}(c) with mark(skel(c),full)\mathrm{mark}(\mathrm{skel}(c), \mathrm{full}) and hch_c with (s,j,p,r)(s, j, p, r) in cc, while leaving chk(c)\mathrm{chk}(c), DcD_c, and ฮณc\gamma_c unchanged. For a cell cโˆˆ๐’žqc \in \mathcal{C}_q and a palette checker state ฯ‡\chi over CqC_q, the updated cell c[chkโ†ฆฯ‡]c[\mathrm{chk} \mapsto \chi] is the cell obtained by replacing chk(c)\mathrm{chk}(c) with ฯ‡\chi and leaving all other components unchanged.โœฆ The updated cell c[colโ†ฆa]c[\mathrm{col} \mapsto a], for a cell cโˆˆ๐’žqc \in \mathcal{C}_q and a color aโˆˆCqa \in C_q, is obtained by replacing pos(c)\mathrm{pos}(c) in skel(c)\mathrm{skel}(c) with palette(a)\mathrm{palette}(a) while leaving all other components unchanged.โœฆ

Given a verification clause schedule SS of parameter qq and a data size dโˆˆโ„•d \in \mathbb{N}, a cell cโˆˆ๐’žqc \in \mathcal{C}_q satisfies the cell formatting condition for SS and dd if:

  1. skel(c)\mathrm{skel}(c) is admissible;

  2. chk(c)=idle\mathrm{chk}(c) = \mathrm{idle} whenever cc does not lie in the palette;

  3. Dc(false)=Dc(true)=0D_c(\mathrm{false}) = D_c(\mathrm{true}) = 0 whenever pos(c)=core(p)\mathrm{pos}(c) = \mathrm{core}(p) with pโ‰ฅdp \ge d;

  4. Dc(false)=Dc(true)=0D_c(\mathrm{false}) = D_c(\mathrm{true}) = 0 and ฮณc=0\gamma_c = 0 whenever cc does not lie in the core;

  5. meta(c)=m0\mathrm{meta}(c) = m_0, hc=h0h_c = h_0, Dc(true)=0D_c(\mathrm{true}) = 0, and ฮณc=0\gamma_c = 0 whenever marker(c)=idle\mathrm{marker}(c) = \mathrm{idle};

  6. hc=h0h_c = h_0 whenever marker(c)โˆˆ{left,right}\mathrm{marker}(c) \in \{\mathrm{left}, \mathrm{right}\};

  7. hch_c has clause index 00, phase acquisition\mathrm{acquisition}, and register 00 whenever marker(c)=boundary\mathrm{marker}(c) = \mathrm{boundary};

  8. the side of hch_c is false\mathrm{false} whenever skel(c)\mathrm{skel}(c) carries an active head marker and the zero-task flag of meta(c)\mathrm{meta}(c) is true\mathrm{true}; and

  9. whenever marker(c)=full\mathrm{marker}(c) = \mathrm{full} and hc=(s,j,p,r)h_c = (s, j, p, r), the index jj equals 00 if p=successp = \mathrm{success}, satisfies j<mS(task(c))j < m_S(\mathrm{task}(c)) if pโ‰ successp \neq \mathrm{success}, and skel(c)\mathrm{skel}(c) is terminal if pp satisfies the endpoint phase condition.

Two finite table cells a,bโˆˆ๐’žqa, b \in \mathcal{C}_q satisfy checker compatibility if (chk(a),chk(b))(\mathrm{chk}(a), \mathrm{chk}(b)) forms a compatible adjacent palette checker pair whenever both aa and bb lie in the palette, and chk(a)\mathrm{chk}(a) satisfies the terminal palette checker condition whenever aa lies in the palette and pos(b)=stop\mathrm{pos}(b) = \mathrm{stop}.โœฆ Two finite table cells a,bโˆˆ๐’žqa, b \in \mathcal{C}_q form a compatible adjacent cell pair if skel(a)\mathrm{skel}(a) and skel(b)\mathrm{skel}(b) form a compatible adjacent skeleton pair and (a,b)(a, b) satisfies checker compatibility.โœฆ

Local Moves, Rewriting, and Survival

Under a verification clause schedule SS of parameter qq, the unary cell transition c1โ†’Sc2c_1 \to_S c_2 on cells of parameter qq holds for any cell cโˆˆ๐’žqc \in \mathcal{C}_q, side sโˆˆ{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, clause indices j,jโ€ฒโˆˆCqj, j' \in C_q, and register state rโˆˆRegr \in \mathrm{Reg} in twelve cases:

  1. when skel(c)\mathrm{skel}(c) is initial: idle(c,s)โ†’Sboundary(c,s)\mathrm{idle}(c, s) \to_S \mathrm{boundary}(c, s), full(c,s,j,read-left,r)โ†’Sfull(c,s,j,read-right,r)\mathrm{full}(c, s, j, \text{read-left}, r) \to_S \mathrm{full}(c, s, j, \text{read-right}, r), and full(c,s,j,undo-left,r)โ†’Sfull(c,s,j,undo-right,r)\mathrm{full}(c, s, j, \text{undo-left}, r) \to_S \mathrm{full}(c, s, j, \text{undo-right}, r);

  2. when skel(c)\mathrm{skel}(c) is terminal: boundary(c,s)โ†’Sfull(c,s,0,acquisition,0)\mathrm{boundary}(c, s) \to_S \mathrm{full}(c, s, 0, \mathrm{acquisition}, 0), together with full(c,s,j,p,r)โ†’Sfull(c,s,j,pโ€ฒ,r)\mathrm{full}(c, s, j, p, r) \to_S \mathrm{full}(c, s, j, p', r) for (p,pโ€ฒ)(p, p') equal to (acquisition,read-left)(\mathrm{acquisition}, \text{read-left}), (read-right,before-gate)(\text{read-right}, \text{before-gate}), (after-gate,undo-left)(\text{after-gate}, \text{undo-left}), or (undo-right,finish)(\text{undo-right}, \mathrm{finish}), as well as for (p,pโ€ฒ)=(before-gate,after-gate)(p, p') = (\text{before-gate}, \text{after-gate}) provided truthCS(task(c),j)(r)=true\mathrm{truth}_{C_S(\mathrm{task}(c), j)}(r) = \mathrm{true};

  3. when skel(c)\mathrm{skel}(c) is terminal and j+1=jโ€ฒj + 1 = j': full(c,s,j,finish,0)โ†’Sfull(c,s,jโ€ฒ,acquisition,0)\mathrm{full}(c, s, j, \mathrm{finish}, 0) \to_S \mathrm{full}(c, s, j', \mathrm{acquisition}, 0);

  4. when skel(c)\mathrm{skel}(c) is terminal and j+1=mS(task(c))j + 1 = m_S(\mathrm{task}(c)): full(c,s,j,finish,0)โ†’Sfull(c,s,0,success,0)\mathrm{full}(c, s, j, \mathrm{finish}, 0) \to_S \mathrm{full}(c, s, 0, \mathrm{success}, 0); and

  5. when skel(c)\mathrm{skel}(c) is terminal and the zero-task flag of meta(c)\mathrm{meta}(c) is false\mathrm{false}: full(c,s,0,success,0)โ†’Sfull(c,ยฌs,0,success,0)\mathrm{full}(c, s, 0, \mathrm{success}, 0) \to_S \mathrm{full}(c, \neg s, 0, \mathrm{success}, 0).

Adjacent pairs of cells of parameter qq evolve under SS by the binary cell transition (c1,c2)โ‡’S(c1โ€ฒ,c2โ€ฒ)(c_1, c_2) \Rightarrow_S (c'_1, c'_2), which holds for any cells a,bโˆˆ๐’žqa, b \in \mathcal{C}_q, side sโˆˆ{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, indices j,p,x,y,vโˆˆCqj, p, x, y, v \in C_q, and register state rโˆˆRegr \in \mathrm{Reg} in eight cases (writing ฮ”=ฮด(CS(task(a),j),a)\Delta = \delta(C_S(\mathrm{task}(a), j), a)):

  1. (boundary(a,s),idle(b,s))โ‡’S(wing(a,left),boundary(b,s))(\mathrm{boundary}(a, s), \mathrm{idle}(b, s)) \Rightarrow_S (\mathrm{wing}(a, \mathrm{left}), \mathrm{boundary}(b, s)) when mark(skel(a),left)\mathrm{mark}(\mathrm{skel}(a), \mathrm{left}) and mark(skel(b),boundary)\mathrm{mark}(\mathrm{skel}(b), \mathrm{boundary}) form a compatible adjacent skeleton pair;

  2. when mark(skel(a),full)\mathrm{mark}(\mathrm{skel}(a), \mathrm{full}) and mark(skel(b),right)\mathrm{mark}(\mathrm{skel}(b), \mathrm{right}) form a compatible adjacent skeleton pair, (wing(a,left),full(b,s,j,read-left,r))โ‡’S(full(a,s,j,read-left,r+ฮ”),wing(b,right))(\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, s, j, \text{read-left}, r)) \Rightarrow_S (\mathrm{full}(a, s, j, \text{read-left}, r + \Delta), \mathrm{wing}(b, \mathrm{right})), (full(a,s,j,read-right,r),wing(b,right))โ‡’S(wing(a,left),full(b,s,j,read-right,r))(\mathrm{full}(a, s, j, \text{read-right}, r), \mathrm{wing}(b, \mathrm{right})) \Rightarrow_S (\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, s, j, \text{read-right}, r)), (wing(a,left),full(b,s,j,undo-left,r))โ‡’S(full(a,s,j,undo-left,r),wing(b,right))(\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, s, j, \text{undo-left}, r)) \Rightarrow_S (\mathrm{full}(a, s, j, \text{undo-left}, r), \mathrm{wing}(b, \mathrm{right})), and (full(a,s,j,undo-right,r),wing(b,right))โ‡’S(wing(a,left),full(b,s,j,undo-right,r+ฮ”))(\mathrm{full}(a, s, j, \text{undo-right}, r), \mathrm{wing}(b, \mathrm{right})) \Rightarrow_S (\mathrm{wing}(a, \mathrm{left}), \mathrm{full}(b, s, j, \text{undo-right}, r + \Delta));

  3. (a,b[chkโ†ฆidle])โ‡’S(a,b[chkโ†ฆhead(x)])(a, b[\mathrm{chk} \mapsto \mathrm{idle}]) \Rightarrow_S (a, b[\mathrm{chk} \mapsto \mathrm{head}(x)]) when pos(a)=core(p)\mathrm{pos}(a) = \mathrm{core}(p) with p+1=qp + 1 = q and bb lies in the palette;

  4. (a[chkโ†ฆhead(x)],b[chkโ†ฆidle])โ‡’S(a[chkโ†ฆpassed(x)],b[chkโ†ฆhead(x)])(a[\mathrm{chk} \mapsto \mathrm{head}(x)], b[\mathrm{chk} \mapsto \mathrm{idle}]) \Rightarrow_S (a[\mathrm{chk} \mapsto \mathrm{passed}(x)], b[\mathrm{chk} \mapsto \mathrm{head}(x)]) when pos(a)=palette(v)\mathrm{pos}(a) = \mathrm{palette}(v), bb lies in the palette, and vโ‰ xv \neq x; and

  5. (a,b)โ‡’S(b,a)(a, b) \Rightarrow_S (b, a) when pos(a)=palette(x)\mathrm{pos}(a) = \mathrm{palette}(x), pos(b)=palette(y)\mathrm{pos}(b) = \mathrm{palette}(y), a[colโ†ฆy]=ba[\mathrm{col} \mapsto y] = b, and both aa and bb are head-free.

A cell word of parameter qq is a finite word wโˆˆ๐’žq*w \in \mathcal{C}_q^* over ๐’žq\mathcal{C}_q, with length |w||w| and concatenation uvu v. Given a verification clause schedule SS of parameter qq and a data size dโˆˆโ„•d \in \mathbb{N}, two cell words v,wโˆˆ๐’žq*v, w \in \mathcal{C}_q^* satisfy the cell word replacement relation for SS and dd if every cell appearing in vv or ww satisfies the cell formatting condition for SS and dd, and either v=av = a and w=bw = b are one-cell words with aโ†’Sba \to_S b or bโ†’Sab \to_S a, or v=abv = ab and w=aโ€ฒbโ€ฒw = a'b' are two-cell words with (a,b)โ‡’S(aโ€ฒ,bโ€ฒ)(a, b) \Rightarrow_S (a', b') or (aโ€ฒ,bโ€ฒ)โ‡’S(a,b)(a', b') \Rightarrow_S (a, b). Given SS and dd, a rewriting step vโ†’S,dwv \to_{S, d} w relates two cell words v,wโˆˆ๐’žq*v, w \in \mathcal{C}_q^* if v=pusv = p u s and w=puโ€ฒsw = p u' s for some words p,s,u,uโ€ฒโˆˆ๐’žq*p, s, u, u' \in \mathcal{C}_q^* such that uu and uโ€ฒu' satisfy the cell word replacement relation for SS and dd.โœฆ A cell word wโ€ฒโˆˆ๐’žq*w' \in \mathcal{C}_q^* is reachable from a cell word wโˆˆ๐’žq*w \in \mathcal{C}_q^* under SS and dd if wโ€ฒw' is obtained from ww by a finite sequence of zero or more rewriting steps under SS and dd.โœฆ

Under a verification clause schedule SS of parameter qq, a finite table cell cโˆˆ๐’žqc \in \mathcal{C}_q satisfies the semantic zero condition for SS if marker(c)=full\mathrm{marker}(c) = \mathrm{full} and, writing hc=(s,j,p,r)h_c = (s, j, p, r), either pโˆˆ{acquisition,finish,success}p \in \{\mathrm{acquisition}, \mathrm{finish}, \mathrm{success}\} with rโ‰ 0r \neq 0, p=after-gatep = \text{after-gate} with truthCS(task(c),j)(r)=false\mathrm{truth}_{C_S(\mathrm{task}(c), j)}(r) = \mathrm{false}, or p=successp = \mathrm{success} with the zero-task flag of meta(c)\mathrm{meta}(c) equal to true\mathrm{true}.โœฆ Given SS and a data size dโˆˆโ„•d \in \mathbb{N}, a cell cโˆˆ๐’žqc \in \mathcal{C}_q satisfies the unary zero condition for SS and dd if cc fails the cell formatting condition for SS and dd, satisfies the semantic zero condition for SS, or satisfies pos(c)=palette(x)\mathrm{pos}(c) = \mathrm{palette}(x) and chk(c)=passed(x)\mathrm{chk}(c) = \mathrm{passed}(x) for some xโˆˆCqx \in C_q.โœฆ Two cells a,bโˆˆ๐’žqa, b \in \mathcal{C}_q satisfy the binary zero condition if (a,b)(a, b) fails to form a compatible adjacent cell pair, if pos(a)=pos(b)=palette(x)\mathrm{pos}(a) = \mathrm{pos}(b) = \mathrm{palette}(x) for some xโˆˆCqx \in C_q, or if pos(a)=palette(x)\mathrm{pos}(a) = \mathrm{palette}(x), chk(a)=head(y)\mathrm{chk}(a) = \mathrm{head}(y) with xโ‰ yx \neq y, and pos(b)=stop\mathrm{pos}(b) = \mathrm{stop} for some x,yโˆˆCqx, y \in C_q.โœฆ A cell word vโˆˆ๐’žq*v \in \mathcal{C}_q^* is a zero word for SS and dd if either v=cv = c is a one-cell word satisfying the unary zero condition for SS and dd, or v=abv = ab is a two-cell word satisfying the binary zero condition.โœฆ Given a verification clause schedule SS of parameter qq and a data size dโˆˆโ„•d \in \mathbb{N}, a cell word wโˆˆ๐’žq*w \in \mathcal{C}_q^* survives (or is surviving) under SS and dd if for every cell word wโ€ฒโˆˆ๐’žq*w' \in \mathcal{C}_q^* reachable from ww under SS and dd and every factorization wโ€ฒ=pzsw' = p z s with p,z,sโˆˆ๐’žq*p, z, s \in \mathcal{C}_q^*, the subword zz is not a zero word for SS and dd.โœฆ

For a parameter qโˆˆโ„•q \in \mathbb{N}, the fragment length bound B(q)โˆˆโ„•B(q) \in \mathbb{N} is defined by B(q)=12(17q+3).B(q) = 12(17q + 3).(1)โœฆ

The Claim

Theorem 1. Let qโˆˆโ„•q \in \mathbb{N}, let SS be a verification clause schedule of parameter qq, and let dโˆˆโ„•d \in \mathbb{N} be a data size. For every surviving cell word wโˆˆ๐’žq*w \in \mathcal{C}_q^* under SS and dd:

  1. if every cell of ww lies in the palette, then |w|โ‰ค16q+2;|w| \le 16q + 2;(2)โœฆ

  2. if no cell of ww is a cut cell, then |w|โ‰ค77q+11;|w| \le 77q + 11;(3)โœฆ

  3. if no cell of ww after its first cell is a cut cell, then |w|โ‰ค(10+2)(17q+3).|w| \le (10 + 2)(17q + 3).(4)โœฆ

In the paper, the result reads: for level hh with qh=2hq_h = 2^h, where qq stands for qhq_h, there is a bound depending only on hh for every palette fragment in a nonzero word (one may take 16qh+216q_h + 2), and an interval without a cut has bounded length depending only on hh, including when the interval reaches an end of the word. Boundsย (2), (3), andย (4) are stated for an arbitrary parameter qq and any surviving cell word ww rather than only for nonzero words at parameter qhq_h, with the fragment length boundย (1) giving the right-hand side ofย (4).

What Is Checked

Boundsย (2), (3), andย (4) (together with the fragment length boundย (1) in qq) are stated over an arbitrary parameter qโˆˆโ„•q \in \mathbb{N}, a verification clause schedule SS of parameter qq, a data size dโˆˆโ„•d \in \mathbb{N}, and a surviving cell word wโˆˆ๐’žq*w \in \mathcal{C}_q^* under SS and dd whose cells all lie in the palette, contain no cut cells, or contain no cut cells after the first cell.