The Setting
Consider finite words of cells under symmetric one-cell and two-cell local replacement rules relative to forbidden one-cell and two-cell zero patterns. In a finite-table verification block, the segment between the final core position and the stop position consists of palette cells carrying a color and a checker state alongside transaction-head and memory fields governed by a verification clause schedule. The question is how avoiding all reachable zero factors constrains coloring and checker rollback on such a palette segment, first in an abstract model where auxiliary moves are governed by a head predicate and then in concrete finite-table cell words.
Abstract Palette Words
Let be a set of colors and a set of auxiliary states. The set of palette checker states over consists of , for , and for .✦ A palette cell over is a triple comprising a color , a checker state , and an auxiliary state . A palette word over is a finite sequence () of palette cells over , with length and color list ; write juxtaposition for word concatenation, identifying each cell with the one-cell word .
Given a palette cell over and , the checker update is the palette cell . For a palette word over , the idle-checker word of is the palette word over .
Two palette checker states form a compatible checker pair if both equal , both equal for some , for some , or for some .✦ A palette checker state satisfies the terminal checker condition if or for some .✦ A palette word over satisfies the palette syntax condition if every adjacent pair () is a compatible checker pair and, when , satisfies the terminal checker condition.✦
The set of palette zeros over is the set of all palette words over for which at least one of three conditions holds: some cell in satisfies with ; two adjacent cells in satisfy ; or is nonempty and its last cell satisfies with .✦
Fix a predicate on . A directed palette rewrite between palette words over holds when and are related by one of the four rules in (1), for any , palette cells over , palette words over , and : (1)✦ A symmetric palette step between palette words over holds if or ✦, and the palette reachability relation on palette words over is the reflexive-transitive closure of .✦ A palette word over survives under if no palette word with belongs to .✦
Block Syntactic Skeletons
The set of cell markers is the set . For each integer arity bound , a block metadata record of bound is a triple consisting of an arity , a Boolean zero-task flag , and a block index , and is the set of these records.
For an integer position bound , the set of block cell positions consists of core positions for , palette positions for , and the position .✦ A cell syntactic skeleton of bounds is a triple . For a cell syntactic skeleton of bounds and a marker , the re-marked skeleton is the cell syntactic skeleton of bounds .
A syntactic skeleton of bounds is initial if and ✦, and terminal if and .✦ A syntactic skeleton of bounds is admissible if implies is not initial and implies is not terminal✦, and carries an active head marker if .✦
Two syntactic skeletons of bounds satisfy structural position adjacency if has one of the five forms with , with , , , or . A pair of syntactic skeletons of bounds satisfies internal consistency if , , the block indices satisfy when and otherwise, is not initial, and is not terminal.
A syntactic skeleton of bounds accepts a marker on the left if when and otherwise✦, and accepts on the right if when and otherwise.✦ A syntactic skeleton of bounds is left-external if or both and is initial✦, and right-external if or both and is terminal.✦
The set of compatible adjacent skeleton pairs of bounds is the set of all pairs of syntactic skeletons of bounds that satisfy structural position adjacency and either have right-external and left-external, or have neither right-external nor left-external while accepts on the right, accepts on the left, and satisfies internal consistency.✦
Cells and Survival in Finite Tables
Fix a positive integer bound . A cell memory address of bound is either a data address specified by a Boolean side , a block index , and a position index , or a certificate address with ; write for the set of these addresses.✦ The additive group of three-bit register states is the group of functions over .✦ A verification clause of bound is a pair consisting of an address triple and a Boolean truth function .✦
A verification task is a pair consisting of an arity and a Boolean zero-task flag .✦ A verification clause schedule of bound assigns to each verification task a clause count satisfying and a family of verification clauses of bound indexed by .✦
The set of head computation phases consists of nine sequential stages: , , , , , , , , and .✦ A reading head state of bound is a quadruple consisting of a Boolean side , a clause index , a head computation phase , and a three-bit register state ; the default reading head state of bound is the reading head state of bound .✦
A cell arity metadata record is an element of ✦, and the associated task of is the verification task .✦ The default cell metadata record is the element .✦
A finite-table cell of bound is a tuple consisting of a syntactic skeleton of bounds , a palette checker state , a data function , a certificate bit , and a reading head state of bound . Write , , and for the position, marker, and metadata of ; a finite-table cell of bound is a core cell if for some and a palette cell if for some .
For a finite-table cell of bound , its color equals when and otherwise; for a finite sequence (or cell word) of finite-table cells of bound , write and .✦ For a finite-table cell of bound and , the recolored cell is the finite-table cell of bound obtained by replacing with while preserving all other fields of ✦, and the color erasure of is the finite-table cell of bound .✦ For a finite-table cell of bound and , the checker update is the finite-table cell of bound obtained by replacing with while preserving all other fields of .✦ A finite-table cell of bound is head-free if does not carry an active head marker and for every .
Four operations modify the marker and transaction fields of a finite-table cell of bound : for , the boundary cell replaces with and sets the head to ✦; for , the wing cell replaces with and sets the head to ✦; for , , phase , and , the full cell replaces with and sets the head to ✦; and for , the idle cell replaces with , sets the head to and the certificate bit to , keeps unchanged, and replaces with the function mapping to and to .✦
The bit read from a finite-table cell of bound at an address is given by (2): (2)✦ For a verification clause of bound and a finite-table cell of bound , the clause register delta is defined at each by .✦
A head computation phase is an endpoint phase if . Given a verification clause schedule of bound and a data size , a finite-table cell of bound satisfies the cell formatting condition for if the following conditions hold: is admissible; if is not a palette cell then ; if with then ; if is not a core cell then and ; if then , , , and ; if then ; if then , , and ; if carries an active head marker and then ; and if then implies , implies , and being an endpoint phase implies is terminal.
Two finite-table cells of bound satisfy checker compatibility if whenever both are palette cells the pair is a compatible checker pair in , and whenever is a palette cell and the checker state satisfies the terminal checker condition.✦ A pair of finite-table cells of bound forms a compatible adjacent cell pair if and satisfy checker compatibility.
Given a verification clause schedule of bound , the unary cell transition between finite-table cells of bound holds in the twelve cases of (3), for any cell , side with opposite side , clause indices , and register : (3)✦
For a verification clause schedule of bound , let denote and write . The binary cell transition on pairs of finite-table cells of bound holds in the eight cases of (4), for any cells , , , and : (4)
Two cell words of bound satisfy the cell-list replacement relation for if every cell appearing in or satisfies the cell formatting condition for and either and with or , or and with or .✦ A cell-word rewriting step holds between cell words of bound if and for some cell words of bound and pair satisfying the cell-list replacement relation for ✦, and the cell-word reachability relation on cell words of bound is the reflexive-transitive closure of .✦
A finite-table cell of bound is a semantic zero cell for if and its head satisfies one of three failure conditions: and ; and ; or and . A finite-table cell of bound is a unary zero cell for if fails the cell formatting condition for , is a semantic zero cell for , or and for some .✦ Two finite-table cells of bound form a binary zero pair if is not a compatible adjacent cell pair, for some , or , , , and .✦ The set of zero cell words for is the set of one-cell words where is a unary zero cell for and two-cell words where is a binary zero pair✦; a cell word of bound survives under if whenever for cell words of bound , the factor does not belong to .✦
For a cell word of bound , the idle-checker cell word of is the cell word of bound .✦ Given , a vector , and a position , the canonical cell is the finite-table cell of bound with skeleton , checker state , certificate bit , head state , data bit , and data bit equal to when with and otherwise.✦ Given , a vector , and a finite list of colors in , the canonical palette word of for is the cell word of bound .
The Claim
Theorem 1. Let be a color set, an auxiliary state set, and a predicate on . If is a palette word over satisfying the palette syntax condition whose cells all have checker state and whose color list has pairwise distinct entries containing every element of , then every palette word over with satisfies (5): (5)✦ For any palette word over satisfying the palette syntax condition, (6) holds: (6)✦ Every nonempty palette word over that survives under and has checker state on every cell satisfies (7): (7)✦ When satisfies and is a palette word over surviving under with and for all , condition (8) holds: (8)✦ Under the hypotheses of (8), if is also nonempty and is a finite list of pairwise distinct elements of containing every element of , then (9) holds: (9)✦
Fix an integer bound , a verification clause schedule of bound , and a data size . Suppose and are finite-table cells of bound with for some satisfying and , and suppose is a word of palette cells of bound such that survives under ; then (10) holds: (10)✦ If, in addition to the hypotheses of (10), is nonempty, then (11) holds: (11)✦ Whenever , , and satisfy the hypotheses of (11) and every cell of has marker and checker state , for every vector condition (12) holds: (12)✦ If is any word of palette cells of bound that survives under and satisfies for all , then (13) holds: (13)✦
In the paper, the result reads: a complete palette containing each color exactly once, initially idle on its checker track, cannot reach a palette zero under palette operations arbitrarily interleaved with transaction operations; conversely, if a palette together with its preceding core cell at (the paper’s , with standing for ) and following stop cell at (the paper’s ) occurs in a nonzero word, its checker can be removed by replacements supported on those cells, and once its transaction track is also idle, the palette has each color once and can be sorted into increasing color order. Parts (5) through (9) isolate the abstract palette invariants with the auxiliary state set and predicate representing interleaved transaction moves, while parts (10) through (13) formulate the finite-table invariants for surviving cell words with idle markers representing an idle transaction track.
What Is Checked
The abstract claims (5) through (9) are stated over palette words in an arbitrary color set and auxiliary state set equipped with a head predicate under the palette syntax, idle-checker, zero-word, reachability, and survival conditions, while the finite-table claims (10) through (13) are stated over cell words of positive bound relative to a verification clause schedule and data size under the cell projections, color-erasure, idle-checker, and canonical-palette maps and the cell-word reachability and survival relations built from block syntactic skeletons, cell formatting, unary and binary transitions, and zero patterns.