The Setting
Write for the Boolean truth values and 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 . The control set for a single-clause sweep on positions consists of (acquisition), and (left and right read at ), (before-gate), (after-gate), and (left and right undo at ), and (finish).โฆ A clause tour payload on positions specifies a delta map with and a gate predicate on three-bit registers ; its total delta is . A clause tour state is a triple .
Directed tour transitions on advance as follows: ; for ; ; for ; ; when holds; ; for ; ; for ; and . A clause tour state is a payload semantic zero for if either and , or and fails.โฆ
A head-tour plan pairs clause tour payloads on positions with a zero-task flag ; clause holds in , written , when holds. A full control state is either a clause control with and or the terminal control ; write for the set of full tour states pairing a full control state with a register in and a side in , and write โฆ. Directed plan transitions apply a -transition inside clause , move for , move , and flip when . The symmetric step relation holds when or , and tour reachability is the reflexive transitive closure of . A full tour state of is bad for if either and is a payload semantic zero for , or and ; a full tour state is semantically zero for , written , if is bad for or both and .
Cells, Regions, and Local Rewriting
A verification task consists of an arity and a zero-task flag . For a capacity bound , a data bit address in specifies a side, a block index, and a position below , and the set of cell memory addresses consists of data addresses for and certificate addresses for . A verification clause of bound pairs three addresses with a truth function . A verification clause schedule of bound assigns to each task a positive clause count and a family of verification clauses for .โฆ
Over a color set , a palette checker state is , , or for ; two adjacent checker states form a compatible checker pair when they are , , , or for some , and a checker state satisfies the terminal checker condition when it is or . For bound , a block position is (), (), or , and a cell marker is one of , , , , or . For an arity bound , a block metadata record has arity , zero-task flag , and block index ; when , its task projection is . A cell skeleton joins a position, marker, and metadata record; marking with replaces only by โฆ. A skeleton is initial when and , terminal when and , active-head when , and admissible when implies is not initial and implies is not terminal; a skeleton is left-external when or ( and is initial), and right-external when or ( and is terminal).
Two skeletons are structurally adjacent precisely in the position pairs , , , , and ; two skeletons are internally consistent when they share arity and zero-task flag, if and otherwise, is not initial, and is not terminal. A skeleton accepts marker on the left if when and otherwise, and accepts on the right if when and otherwise. Two skeletons form a compatible skeleton pair when they are structurally adjacent and either is right-external and is left-external, or neither is external, accepts on the right, accepts on the left, and are internally consistent.โฆ A finite sequence of skeletons is closed if every is admissible, every adjacent pair is a compatible skeleton pair, and whenever , is left-external and is right-external.โฆ
The nine head computation phases are , , , , , , , , and ; among them, , , , , and are endpoint phases. A reading head state specifies a side , clause , phase , and register ; the default metadata and default head are and . A finite-table cell of bound consists of a skeleton with arity bound (determining , , , and ), a palette checker over , data bits , a certificate bit , and a head state . A finite-table cell of bound is in the core when , in the palette when , and head-free when is not active-head and for all . Cell constructors act on as follows: keeps , sets marker , default metadata, default head, , , and ; marks and sets head ; marks and sets default head; and marks and sets head . Write for replacing by , and for replacing by .
A finite-table cell of bound is payload-formatted for data size if non-palette cells have , core cells at positions have , and non-core cells have and . A finite-table cell of bound is formatted for if is admissible, is payload-formatted for , and the following conditions hold: forces default metadata, default head, , and ; forces default head; forces , , and ; an active-head skeleton with forces ; and forces when , when , and terminal whenever is an endpoint phase. Two cells satisfy checker compatibility when both being in the palette implies is a compatible checker pair and in the palette with implies satisfies the terminal checker condition; two cells form a compatible cell pair when both their skeletons and checkers are compatible. A cell word of bound satisfies word syntax for , written , if its skeletons form a closed sequence, every adjacent pair in satisfies checker compatibility, and every cell in is formatted for .โฆ For a finite-table cell of bound and an address , the reading is if , , and ; if , , and ; and otherwise. For a verification clause and a cell of bound , the register delta has -th entry .
Under schedule , the unary cell transitions relate single cells as follows: when is initial; when is terminal; at terminal , , , when , , , (), when , and when ; and at initial , and . The binary cell transitions relate adjacent cell pairs in eight ways: when marked form a compatible skeleton pair; four sweep moves when marked form a compatible skeleton pair, sending , , , and ; creating a checker head when and is in the palette; advancing when with and is in the palette; and swapping when are head-free palette cells at positions satisfying . Two cell words satisfy replacement for if every cell in and is formatted for and either are related in either direction by a unary transition or are related in either direction by a binary transition. For any cell words and , a rewriting step sends to whenever is a replacement, and cell-word reachability is the reflexive transitive closure of rewriting steps.
A cell region of bound and data size consists of a positive size , a task , and cells of bound such that every satisfies and payload formatting for , the skeleton of is initial if and only if and terminal if and only if , and every adjacent pair has structurally adjacent and internally consistent skeletons. For a schedule , the induced head-tour plan has clauses on positions and zero-task flag , where the -th payload () has delta and gate . Given a full tour state , write for the clause, phase, and position induced by : when , , is the phase corresponding to , and is the sweep index for read or undo sweeps and otherwise; when , , , and . The realized word has length and -th cell for , for , and for .
A cell is semantically zero for , written , if and either with , with , or with . A finite-table cell of bound is a unary zero for if fails formatting for , holds, or with for some . A pair of cells is a binary zero if it is not a compatible cell pair, if for some , or if , for , and .
Good Words and Pivots
Given a finite sequence of cells of bound , a cut occurs at if is right-external; two indices lie in the same region, written , when no cut occurs at any with . For a schedule , indices and , and bound , define the partial sum over all satisfying , together with the total sum and left sum . Clause holds for head in , written , if . A phase has passed the gate when , and the register potential is given by (1) A finite sequence of cells of bound has a good head at under , written , if by (1) and either with for all , or with for all and whenever has passed the gate. A finite sequence of cells of bound is all-good under , written , if holds for every with ; a cell word of length is good under , written , if is all-good under .
Two cell sequences of length satisfy the pivot relation at index , written , if there exist a cell and a side such that , , for all , the skeleton is terminal, and .
Circuits, Tableaux, and Addressable Clauses
For a wire bound , a circuit wire is an element of ; under an assignment , a constant bit evaluates to and a wire index evaluates to . A combinational not-and (NAND) circuit with inputs and gates is an ordered sequence of two-input NAND gates built recursively from the empty circuit by appending gates whose two input wires lie in at step .โฆ On an input vector , circuit evaluation extends to by assigning to each successive gate the NAND of its two input-wire evaluations.โฆ A three-wire circuit clause over wires pairs three circuit wires with a truth function ; the defining clauses of form the list of three-wire circuit clauses over wires obtained recursively by embedding earlier clauses and appending the three NAND constraint clauses for each new gate.
With bound , an addressable wire reading is an element of , evaluating under to on constant and to on address . A three-wire addressable clause consists of three addressable wire readings and a truth function ; an assignment satisfies , written , if applying to the evaluations of under yields . Writing for the conversion sending to and to , compiling produces a verification clause whose -th address is if and if is constant, and whose truth function evaluates on the tuple taking constant wires to their fixed bits and addressed wires to for register .โฆ Special addressable clauses include: the unit clause on wires requiring ; the equality clause () on wires requiring for and for ; and the circuit lift along of a circuit clause , mapping wire indices via and fixing constants. An addressable input bit is either a fixed bit or a data reference ; for reading and direction , the initial-value constraint clause is when is fixed , and on is the three-wire clause on enforcing for and for , where .
For integers with , , , total certificate variable count , and total tableau clause count , a tableau layout specifies an origin column . Enumerating the tape variables () and gate variables () injectively into defines certificate addresses and ; for and , the local circuit address map sends input index () to and gate index () to . Given a NAND circuit with inputs and gates, output wires (), an initial row , and vectors , the indexed layout clause for enumerates four blocks of addressable clauses: the initial constraints (); the boundary constraints at columns ; the local transition clauses, comprising for each the defining clauses of lifted by and the equality constraints where relabels via ; and the acceptance constraints . For a task-indexed family , the tableau schedule has clause count for every task and assigns to the compiled indexed layout clause for and the compiled clause otherwise. Given and , the assembled assignment sends to and to .
The Source Machine and the Raw Codec
A one-tape Turing machine over alphabet and state set has head motions , commands , tape labels , and a local transition updating each center label from its left, center, and right neighbors according to : an active center head writes , keeps , and retains head only on , 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 of width encodes labels into with left-inverse decoding, lifting the neighborhood rule to a Boolean transition ; for finite , 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 and absent head). A NAND-circuit realization of under consists of a gate count , a NAND circuit with inputs and gates, and output wires computing the lifted Boolean transition.โฆ Given stack indices , tokens , and states , a stack machine program assigns to each state either a push , a pop , or halt; it compiles to a one-tape transition table on multi-track symbols and five simulation modes (ready, push-find, pop-find, pop-read, and back) scanning right to the first empty slot on track to push or pop and returning left to the origin-marked cell.
Take stack register indices with source and destination . Operating over stacks (), , , and , with instruction token set consisting of , , , , , , and , interpreter modes (, , for target phase ), and nine control states (, , , , , , , , ), the universal stack interpreter transfers tokens between and , pops unary counts from to skip to an instruction, executes simulated pushes and pops on entering target mode at (on false), (on true), or (on empty), records ticks onto during the target phase, and halts at . For finite , input packets belong to of cardinality , with one-hot bit representation and left-inverse packet decoding; the universal input decoder reverses bits from to , skips a unary header, collects fixed-width packets onto starting from the all-false initial collection state, and delegates to the universal interpreter. For , write for when and the binary bit length of otherwise, for the binary digits of (most to least significant), and for its prefix encoding. The program specialization encoding is , and the wrapped input machine peels off unary-prefixed header blocks (repeating on marker and entering universal packet collection on ). Instantiating this wrapped machine at and compiling yields the timed tape alphabet , states , and transition table , with blank symbol (origin , empty tracks), origin symbol (origin , empty tracks), bit symbol for (origin , on track ), initial state (ready at reverse), halting state for , and output label (origin symbol, , halting state).
For with , arity , and flag , the input data sequence has length when and when , placing at index the unnegated data reference , where is if and otherwise; for Boolean list and (), the source input sequence prepends the fixed bits to the input data sequence. Given , transforming an input bit sends fixed to fixed and sends to fixed if and to otherwise; for vectors , encoding , origin , and input list , the initial row places fixed at column , transforms by when and , and places fixed elsewhere. Let be the bit width of the one-hot coding of the timed tape machine, let with gates and output wires be a NAND-circuit realization of , and write , , , and for the one-hot encodings of the blank, initial, accepting-output, and bit labels. For parameters , setting and , the layout parameter bounds require: (2) Whenever (2) holds for with , the source layout takes capacity , time , width , and origin ; the source initial row applies the initial-row rule at origin with , , , and the source input sequence for , , , and ; and the source schedule is the tableau schedule of for , , , , and . Write for the addressable indexed layout clause ().
For a height , a raw bitstring is a vector in .โฆ Cell encoding maps a cell of capacity to a raw bitstring by packing natural-number slots in -bit little-endian binary at indices (slots through storing position tag and coordinate, marker tag, arity, block, checker tag and sought color, head clause, and head phase tag, and remaining slots ) followed at indices by Boolean flags (indices through storing , , , , , and the three bits of , and remaining flags ) and thereafter. When all tags and bounded indices lie in range, cell decoding parses these slots and flags into a cell and accepts only if encoding recovers the raw bitstring; word decoding decodes a finite word of raw bitstrings letterwise, failing if any letter fails to decode. Given , , , and , the candidate word list consists of the raw bitstrings at height whose -th word () has -th bit (). For , schedule of bound , and data size , a raw bitstring satisfies raw unary zero if it fails to decode or decodes to a unary zero for ; two raw bitstrings satisfy raw binary zero if both decode to a binary zero pair; a raw word satisfies raw zero if with a raw unary zero or with a raw binary zero; and two raw words satisfy raw replacement if they decode to cell words related by replacement for . For , the raw table entry is if and only if either , is empty, and satisfies raw zero, or and satisfies raw replacement.
The Claim
Theorem 1. Let be a head-tour plan of clauses on positions, and let . Then -reachability of the success state satisfies (3): (3)โฆ
If a full tour state satisfies and , then (4) holds: (4)โฆ
Let be a verification clause schedule of bound , let , and let be a cell region of bound and data size with task . If satisfies whenever , and for every , then the realized cell words satisfy (5): (5)โฆ
If and are cell words of bound such that and , then (6) holds: (6)โฆ
For any sequence of cells of bound and any index , if and hold, then (7) holds: (7)โฆ
If and are sequences of cells of bound such that and hold for some , then (8) holds: (8)โฆ
Fix an integer . There exist a finite Boolean word and an integer such that, for every integer with , the layout parameter bounds (2) hold for and , and for every task and data assignment , setting and letting be empty when and otherwise, (9) holds: (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 in the paper, standing for for a side ) 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 of clauses on positions, Boolean side , and reachable full tour state ; claim (5) is stated over a verification clause schedule of bound , data size , cell region , and side ; claims (6), (7), and (8) are stated over a schedule , data size , cell words with , and finite cell sequences ; and claim (9) is stated over any dilation , tasks , data assignments on , and the source-machine tableau layouts, schedules, and raw codec bounded by (2). For those constructions, the packet width of any finite register index set , the one-hot tape-label bit width , and the clause count of any tableau layout of time and width are positive; the one-hot coding is left-invertible on every label; and every one-tape transition table admits a combinational NAND-circuit realization.