The Setting
Consider finite words of finite-table cells governed by symmetric local rewriting rules of length one and two, together with local zero patterns that mark degenerate configurations. Inside such a word, an active transaction spans a cut-free connected component containing either a full reading head executing a sequence of verification clauses or a boundary cursor at the edge of an acquired prefix. Can every complete transaction region carrying one full head in a valid control state be rolled back to its acquisition state and released to an idle word or else hit a zero cell, and can every boundary-cursor region be released within its acquired interval so that surviving active components unlock completely?
Local Syntax and Palette Checkers
Fix integers . A cell marker is an element of the five-element set . A block metadata record of arity bound is a triple consisting of an arity integer , a Boolean zero-task flag , and a block index .✦ A block cell position of bound is an element of . A cell syntactic skeleton of parameters is a triple , whose components are written . For a skeleton and a cell marker , the marker update of by is the skeleton .✦
A skeleton is initial if and , and terminal if and . A skeleton carries an active head marker if .✦ A skeleton is admissible if implies is not initial and implies is not terminal.✦ A skeleton is left-external if or both and is initial, and right-external if or both and is terminal.
Two skeletons are structurally adjacent, written , when one of four position relations holds: and ; with and ; and is either or ; or and .✦ Two skeletons satisfy internal skeleton consistency, written , when and share the same arity and zero-task flag, if and otherwise, is not initial, and is not terminal.✦
A skeleton accepts a marker on the left if when and otherwise✦; likewise, accepts on the right if when and otherwise.✦ Two skeletons form a compatible adjacent skeleton pair, written , if holds 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 holds.✦ Adjoining a blank boundary symbol to , the skeleton link relation on holds for , for with when is left-external, for with when is right-external, and for with when holds.✦ A finite sequence of skeletons in is closed if every is admissible and every consecutive pair in satisfies the skeleton link relation.✦
For any color set , a palette checker state over is an element of . A checker state satisfies the terminal palette checker condition if or for some .✦ Two adjacent checker states in form a compatible palette checker pair if equals , , , or for some .✦
Finite-table Cells and Local Rewriting
Fix a positive integer and arity bound , and set .✦ A cell memory address in is either a data address with , , and , or a certificate address with .✦ A three-bit register state is a vector .✦ A verification clause of bound consists of three addresses and a truth function .✦ A verification task is a pair consisting of an arity and a Boolean zero-task flag ; the task projection of a metadata record is the verification task . A verification clause schedule of bound assigns to each verification task a positive clause count and verification clauses for .✦
A head computation phase belongs to the nine-element set , standing respectively for acquisition, read-left, read-right, before-gate, after-gate, undo-left, undo-right, finish, and success. An endpoint phase is a computation phase belonging to . A reading head state is a quadruple , whose components are written . The default head state is , and the default cell metadata is .
A finite-table cell consists of a skeleton , a palette checker state , a side-indexed data function , a certificate bit , and a reading head state .✦ Write , , for the components of , and set . A cell is in the core if for some , in the palette if for some , and head-free if does not carry an active head marker and for every .
Given and , the idle cell preserves , sets the marker to , metadata to , certificate bit to , head to , and data at each side to if and to if .✦ The boundary cell replaces with and sets the head to ; the wing cell for marks with and resets the head to ; and the full cell for , , and marks with and sets the head to . For a cell , a checker state , and a color index , the checker update is the cell obtained from by replacing with , and the color update is the cell obtained from by replacing with . For an address and a cell , the address value is equal to if and with , equal to if and with , and otherwise.✦ For a verification clause and , the clause register delta has -th coordinate for .✦
For a data size , a cell satisfies the cell payload format condition if whenever is not in the palette, whenever with , and and whenever is not in the core.✦ Given a schedule and data size , a cell satisfies the cell formatting condition if is admissible, holds, and five marker conditions hold: forces , , , and ; forces ; forces , , and ; an active head marker with forces ; and forces when , when , and terminal whenever .✦
Two cells satisfy checker compatibility if is a compatible palette checker pair whenever both and are in the palette, and satisfies the terminal palette checker condition whenever is in the palette and .✦ Two cells form a compatible adjacent cell pair, written , if and checker compatibility hold.✦ For finite words over , write for concatenation and for the one-cell word consisting of . A cell word satisfies the cell word syntax if its sequence of skeletons is closed, every consecutive pair of cells in satisfies checker compatibility, and every cell in satisfies .✦ For a sequence , write for the length- word whose -th cell is . The number of locked cells in a cell word is the count of cells in whose marker is not .✦
Given a schedule , the unary cell transition on holds across the twelve boundary rules in (1), where , , , and : (1)✦ Writing , the binary cell transition relates adjacent cells in across the eight rules in (2) (for , , , and ): (2)✦
For a schedule and data size , two cell words satisfy the cell list replacement relation if every cell in and satisfies and either with or , or with or . Two cell words are related by a cell word rewriting step under if and for words with in the cell list replacement relation; cell word reachability, written , is the reflexive-transitive closure of this rewriting step relation.
A cell satisfies the semantic zero cell condition if and one of three failure conditions holds: with ; with ; or with .✦ A cell satisfies the unary zero cell condition if fails , satisfies , or has and for some .✦ Two cells satisfy the binary zero cell condition if they fail , share the same palette position for some , or satisfy and for some with while .✦ A cell word satisfies the zero cell word predicate if either with or with .✦ A cell word satisfies the surviving cell word predicate if no word reachable from under admits a factorization with .✦
Head Tours, Regions, and Components
For integers , a head-tour control state is one of , , , , , , , or with , and a full-tour control state is either with and or . A clause tour state is a triple , and a full tour state is a triple , whose components are written . For , the embedding sends to .✦
A clause tour payload on positions consists of register deltas satisfying and a gate predicate on .✦ For a clause tour payload on positions, the payload tour transition on consists of the eleven directed edges in (3): (3)✦ A clause tour state satisfies the payload semantic zero condition for if with , or with .✦
A head-tour plan of clauses on positions consists of clause tour payloads on positions and a Boolean zero-task flag .✦ For a head-tour plan of clauses on positions, the plan tour transition on consists of the four rules in (4): (4)✦ Two full tour states are joined by a symmetric plan tour step if or ; plan reachability is the reflexive-transitive closure of this symmetric step relation. A full tour state is a bad tour state for , written , if and satisfies the payload semantic zero condition for , or if and .✦
For parameters with and , an acquired prefix consists of a length and cells such that is initial if and only if , adjacent skeletons and satisfy both and for each , and every satisfies .✦ A cell region of parameters consists of a length , a verification task , and cells such that and hold for every , is initial if and only if and terminal if and only if , and adjacent skeletons and satisfy both and for each .✦ Write and for the cell words of and . For , the idle word of an acquired prefix is , and the idle word of a cell region is .
Given a cell region of parameters with cells and a schedule , set and . A full tour state satisfies the region side condition for and if implies .✦ The tour plan of , written , is the head-tour plan of clauses on positions with zero-task flag whose -th payload () has deltas for (vanishing at ) and gate predicate .✦ For a full tour state , the head position is if with one of , , , or , and otherwise; the clause index is if and if ; and the head phase is the computation phase obtained by dropping any position argument on when and equal to when . For such , , and , the realized cell at position is given by (5), and the realized word is : (5)
On a finite index set , two indices satisfy connectivity without cuts with respect to a predicate if fails for every satisfying .✦ For a cell sequence , the cell cut predicate holds when is right-external, and the same-region relation is connectivity without cuts with respect to . At any index , the component member set is , with left endpoint , right boundary , component size , and component word . Given a schedule , data size , a cell sequence , and such that satisfies , if then the component region is the cell region of size , task , and cells for (having word ); if then the component partial region is the acquired prefix of size and cells for (having word ).
The Claim
Theorem 1. Let and , and let be a verification clause schedule of bound .
For any head-tour plan of clauses on positions and any full tour state , plan reachability satisfies (6): (6)✦
Given a cell region of parameters and a full tour state satisfying the region side condition for and , the realized word satisfies (7): (7)✦ and under the same hypotheses the realized word satisfies (8): (8)✦
For a cell region of parameters whose cells all satisfy , suppose an index has , for all , and for all . Writing , the region word satisfies (9): (9)✦
Let satisfy , fix , and put . If , the component region satisfies (10): (10)✦ If , the component partial region satisfies (11): (11)✦
For any sequence satisfying and and any index such that carries an active head marker, the component word satisfies (12): (12)✦
What Is Checked
The claims above are stated over head-tour plans and their full states, cell regions and their realized words, formatted cell regions, acquired prefixes, cell words satisfying cell word syntax and survival, and cut-free connected components of finite cell sequences. For these constructions, the library also proves that for every finite cell sequence and every index in it, the component member set is nonempty✦ and the component size is positive.✦