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, -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 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 , write . A block cell position of parameter is one of three kinds: a core position indexed by , a palette position carrying a color , or the terminal stop position .โฆ A cell marker is one of five syntactic tags: , (left wing), , (full active head), or (right wing).โฆ For an arity bound , a block metadata triple is a triple consisting of an arity , a Boolean zero-task flag , and a block index with .โฆ For , a cell syntactic skeleton of parameters and is a triple consisting of a block cell position of parameter , a cell marker , and a block metadata triple of arity bound .โฆ Given a cell syntactic skeleton and a cell marker , the marked skeleton is the skeleton obtained by replacing with while keeping and unchanged.โฆ
A cell syntactic skeleton of parameters and with metadata is initial if and , and terminal if and . A cell syntactic skeleton of parameters and carries an active head marker if .โฆ An admissible cell syntactic skeleton of parameters and is a cell syntactic skeleton of parameters and that satisfies whenever is initial and whenever is terminal.โฆ
Two cell syntactic skeletons and of parameters and satisfy structural position adjacency if is one of five configurations for some indices : with , with , , , or .โฆ A cell syntactic skeleton of parameters and accepts a cell marker on the left if when and otherwise.โฆ For parameters and , a cell syntactic skeleton accepts a cell marker on the right if and otherwise.โฆ A cell syntactic skeleton of parameters and is left-external if or if and is initialโฆ, and right-external if or if and is terminal.โฆ Given two cell syntactic skeletons and of parameters and with metadata and , they satisfy internal skeleton consistency if , , when and otherwise, is not initial, and is not terminal.โฆ Two cell syntactic skeletons and of parameters and form a compatible adjacent skeleton pair if they satisfy structural position adjacency and either is right-external and is left-external, or is not right-external, is not left-external, accepts on the right, accepts on the left, and satisfies internal skeleton consistency.โฆ
Over an arbitrary color set , a palette checker state is either , seeking a color , or an active head seeking .โฆ A palette checker state over satisfies the terminal palette checker condition if or for some .โฆ Two palette checker states over form a compatible adjacent palette checker pair if equals , , , or for some .โฆ
Clauses, Schedules, and Finite Table Cells
For a parameter , a cell memory address in is either a data address specified by a Boolean side , a block index , and a position , or a certificate address specified by .โฆ A three-bit register state is a function .โฆ A verification task is a pair consisting of an arity and a Boolean zero-task flag .โฆ For , a verification clause of parameter is a pair consisting of a triple of cell memory addresses and a Boolean truth function .โฆ A verification clause schedule of parameter specifies for each verification task a positive clause count , together with a verification clause of parameter for every task and every clause index .โฆ
A head computation phase is one of nine stages: , , , , , , , , or โฆ; a head computation phase satisfies the endpoint phase condition if .โฆ For , a reading head state of parameter is a quadruple consisting of a Boolean side , a clause index , a head computation phase , and a three-bit register state โฆ, and the default head state is (with denoting clause index and the zero register in the second and fourth coordinates).โฆ A cell arity metadata triple is a block metadata triple of arity bound .โฆ The task projection is the map sending a cell arity metadata triple to the verification task , and the default cell metadata is the cell arity metadata triple .
For , a finite table cell of parameter is a five-tuple consisting of a cell syntactic skeleton of position parameter and arity bound , a palette checker state over , a data bit function , a certificate bit , and a reading head state of parameter .โฆ The position , marker , and metadata of a finite table cell are those of , and its task is . A cell lies in the core if for some โฆ, and lies in the palette if for some .โฆ A cut cell of parameter is a cell such that and either or the block index of equals .โฆ A cell is head-free if does not carry an active head marker and for every .โฆ
For a cell and an address , the read bit is if , , and the block index of equals ; if , , and the block index of equals ; and otherwise.โฆ Given a verification clause and a cell , the clause register delta is the three-bit register state given at each by .โฆ
Given a finite table cell and a Boolean side , the idle cell is the cell with position , checker , marker , metadata , certificate bit , head state , and data function given at by when and when .โฆ For a cell and a side , the boundary cell is the cell obtained by replacing with and with , leaving , , and unchanged.โฆ The wing cell of a cell and a cell marker is the cell obtained by replacing with and with , leaving , , and unchanged.โฆ For a cell , a side , a clause index , a head computation phase , and a register state , the full cell is the cell obtained by replacing with and with in , while leaving , , and unchanged. For a cell and a palette checker state over , the updated cell is the cell obtained by replacing with and leaving all other components unchanged.โฆ The updated cell , for a cell and a color , is obtained by replacing in with while leaving all other components unchanged.โฆ
Given a verification clause schedule of parameter and a data size , a cell satisfies the cell formatting condition for and if:
is admissible;
whenever does not lie in the palette;
whenever with ;
and whenever does not lie in the core;
, , , and whenever ;
whenever ;
has clause index , phase , and register whenever ;
the side of is whenever carries an active head marker and the zero-task flag of is ; and
whenever and , the index equals if , satisfies if , and is terminal if satisfies the endpoint phase condition.
Two finite table cells satisfy checker compatibility if forms a compatible adjacent palette checker pair whenever both and lie in the palette, and satisfies the terminal palette checker condition whenever lies in the palette and .โฆ Two finite table cells form a compatible adjacent cell pair if and form a compatible adjacent skeleton pair and satisfies checker compatibility.โฆ
Local Moves, Rewriting, and Survival
Under a verification clause schedule of parameter , the unary cell transition on cells of parameter holds for any cell , side , clause indices , and register state in twelve cases:
when is initial: , , and ;
when is terminal: , together with for equal to , , , or , as well as for provided ;
when is terminal and : ;
when is terminal and : ; and
when is terminal and the zero-task flag of is : .
Adjacent pairs of cells of parameter evolve under by the binary cell transition , which holds for any cells , side , indices , and register state in eight cases (writing ):
when and form a compatible adjacent skeleton pair;
when and form a compatible adjacent skeleton pair, , , , and ;
when with and lies in the palette;
when , lies in the palette, and ; and
when , , , and both and are head-free.
A cell word of parameter is a finite word over , with length and concatenation . Given a verification clause schedule of parameter and a data size , two cell words satisfy the cell word replacement relation for and if every cell appearing in or satisfies the cell formatting condition for and , and either and are one-cell words with or , or and are two-cell words with or . Given and , a rewriting step relates two cell words if and for some words such that and satisfy the cell word replacement relation for and .โฆ A cell word is reachable from a cell word under and if is obtained from by a finite sequence of zero or more rewriting steps under and .โฆ
Under a verification clause schedule of parameter , a finite table cell satisfies the semantic zero condition for if and, writing , either with , with , or with the zero-task flag of equal to .โฆ Given and a data size , a cell satisfies the unary zero condition for and if fails the cell formatting condition for and , satisfies the semantic zero condition for , or satisfies and for some .โฆ Two cells satisfy the binary zero condition if fails to form a compatible adjacent cell pair, if for some , or if , with , and for some .โฆ A cell word is a zero word for and if either is a one-cell word satisfying the unary zero condition for and , or is a two-cell word satisfying the binary zero condition.โฆ Given a verification clause schedule of parameter and a data size , a cell word survives (or is surviving) under and if for every cell word reachable from under and and every factorization with , the subword is not a zero word for and .โฆ
For a parameter , the fragment length bound is defined by (1)โฆ
The Claim
Theorem 1. Let , let be a verification clause schedule of parameter , and let be a data size. For every surviving cell word under and :
if every cell of lies in the palette, then (2)โฆ
if no cell of is a cut cell, then (3)โฆ
if no cell of after its first cell is a cut cell, then (4)โฆ
In the paper, the result reads: for level with , where stands for , there is a bound depending only on for every palette fragment in a nonzero word (one may take ), and an interval without a cut has bounded length depending only on , including when the interval reaches an end of the word. Boundsย (2), (3), andย (4) are stated for an arbitrary parameter and any surviving cell word rather than only for nonzero words at parameter , 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 ) are stated over an arbitrary parameter , a verification clause schedule of parameter , a data size , and a surviving cell word under and whose cells all lie in the palette, contain no cut cells, or contain no cut cells after the first cell.