The Setting
Consider words over finite-state cells of capacity , partitioned by designated cut cells into intervals between consecutive cuts and rewritten by local single-cell and two-cell moves that verify Boolean clauses across blocks of arity at most . When can a word free of forbidden local configurations clear all active verification heads to idle markers, or normalize an interval between cuts to a concatenation of canonical blocks? For raw bitstrings of height encoding cells of capacity and for tokens of a self-simulating machine hierarchy with multiplier , when does a token between consecutive cuts consist of between one and ten structural blocks and normalize internally to canonical blocks under explicit bit-width bounds and ?
Local Syntax, Rewriting, and Survival
For a predicate on an alphabet , a word over is cut-free for if no letter of satisfies .✦ A word over is a cut interval for if for a letter satisfying and a cut-free word for .✦
A cell marker is one of five tags: idle, left wing, boundary, full, or right wing.✦ Given a natural number arity bound , a block metadata tuple consists of an arity , a zero-task Boolean flag , and a block index .✦ For a capacity bound , a block cell position is a core position with , a palette position with , or the terminal position .✦ A cell syntactic skeleton of position bound and arity bound consists of a position , a marker , and a block metadata tuple of bound ✦; updating the marker of to , written , replaces with while preserving position and metadata.✦
A cell syntactic skeleton is initial if its block index is and , and terminal if its block index equals its arity and . A skeleton carries an active head marker if is boundary or full.✦ A skeleton is admissible if is not right wing when is initial and not left wing when is terminal.✦
Two skeletons and of position bound and arity bound satisfy structural position adjacency if is with , with , , , or .✦ Two skeletons and of position bound and arity bound satisfy internal consistency if they share the same arity and zero-task flag, their block indices satisfy when and otherwise, is not initial, and is not terminal.✦ A skeleton accepts a marker on the left if is full or right wing when is right wing, and left wing otherwise✦; a skeleton accepts on the right if is left wing, boundary, or full when is left wing, and right wing otherwise.✦ A skeleton is left-external if is idle or both is not right wing and is initial, and right-external if is idle or boundary or both is not left wing and is terminal.
A pair of skeletons forms a compatible adjacent skeleton pair if they satisfy structural position adjacency and either is right-external and is left-external, or neither is external, accepts on the right, accepts on the left, and is internally consistent.✦ The skeleton link relation relates two optional skeletons by holding on two absent entries, relating an absent left entry to when is left-external, relating to an absent right entry when is right-external, and relating when they form a compatible adjacent skeleton pair.✦ A word of skeletons is a closed skeleton sequence if every skeleton in is admissible and every adjacent pair in padded by an absent entry at each end stands in the skeleton link relation.✦
Over a color set , a palette checker state is idle, for some , or an active checker head seeking .✦ Two adjacent palette checker states form a compatible pair if they are , , , or for some .✦ A palette checker state satisfies the terminal palette checker condition if it is idle or for some , and fails if it is .✦
For a bound , a cell memory address is either a data address with side , block index , and position , or a certificate address with .✦ A three-bit register state is a vector in .✦ A verification task specification consists of an arity and a zero-task Boolean flag .✦ A verification clause of bound consists of three cell memory addresses of bound and a Boolean truth function .✦ A verification clause schedule of bound assigns to each task a clause count and a family of verification clauses .✦
A head computation phase is one of nine stages in order: acquisition, read-left, read-right, before-gate, after-gate, undo-left, undo-right, finish, or success.✦ A reading head state of bound consists of a Boolean side , a clause index , a computation phase , and a three-bit register .✦ Cell arity metadata is a block metadata tuple with arity bound , and its task projection is the verification task specification retaining the arity and zero-task flag of . The default cell metadata is ✦, and the default head state is .✦ A finite table cell of capacity consists of a skeleton of position bound and arity bound , a palette checker state over , a data bit pair , a certificate bit in , and a reading head state of bound . A finite table cell is in the core if its position is a core position, is in the palette if its position is a palette position, and is head-free if its skeleton does not carry an active head marker and its checker is not for any color .
Reading a finite table cell at an address yields a bit in : it returns ’s data bit on side when is a data address , lies at with , and the block index of equals ; it returns ’s certificate bit when is a certificate address , lies at with , and the block index of is ; and it returns otherwise.✦ Given a verification clause and a cell , the clause register delta has -th entry equal to the bit read from at the -th address of for .✦
Given a verification clause schedule of capacity and a data size , a cell satisfies the cell formatting condition if its skeleton is admissible, its checker is idle whenever is not in the palette, its data bits vanish at any core position , and both its data bits and certificate bit vanish whenever is not in the core. The cell formatting condition for and also requires that an idle marker on forces default metadata, default head state, true-side data bit , and certificate bit ; a left or right wing marker forces the default head state; a boundary marker forces head clause index , phase acquisition, and register ; an active head marker with zero-task flag true forces head side false; and a full marker requires head clause index in the success phase, head clause index strictly less than in every other phase, and a terminal skeleton whenever the head phase is an endpoint phase.
Two finite table cells and of capacity satisfy checker compatibility if their checkers form a compatible palette checker pair whenever both are in the palette, and ’s checker satisfies the terminal palette checker condition whenever is in the palette and .✦ Cells and form a compatible adjacent cell pair if their skeletons form a compatible adjacent skeleton pair and satisfies checker compatibility.✦ Given a verification clause schedule of capacity and a data size , a word of cells of capacity satisfies cell word syntax for and if the skeletons of form a closed skeleton sequence, every adjacent pair in satisfies checker compatibility, and every cell in satisfies the cell formatting condition for and .✦
Given a cell and side , let update the skeleton marker of to boundary and set its head to the default head with side ; let update the skeleton marker to full and set the head to ; let update the skeleton marker to and set the head to the default head; let keep , reset marker to idle, metadata to default metadata, certificate to , and head to the default head, and set data to on side true and ’s data at on side false; let replace the checker with ; and let set the skeleton position to . Under a schedule , a unary cell transition relates a single cell to another across twelve rules: creating from when is initial; finishing acquisition from to when is terminal; entering read-left from acquisition, exiting read-right to before-gate, entering undo-left from after-gate, and exiting undo-right to finish while preserving when is terminal; turning from read-left to read-right and from undo-left to undo-right while preserving when is initial; passing the gate from before-gate to after-gate when is terminal and ; advancing from to with when is terminal; entering success at from when is terminal and ; and pivoting to when is terminal and the zero-task flag of is false.✦
Under a schedule , a binary cell transition relates an adjacent pair of cells to another across eight rules: acquiring from when the skeletons of and updated with markers left wing and boundary form a compatible skeleton pair; stepping left in read-left from to , stepping right in read-right from to , stepping left in undo-left from to , and stepping right in undo-right from to , each when the skeletons of and updated with markers full and right wing form a compatible skeleton pair; creating a checker head from to when with and is in the palette; advancing a checker head from to when with and is in the palette; and swapping to when , , , and both and are head-free.
For a schedule and data size , two words and of cells satisfy the cell list replacement relation if every cell in or satisfies the cell formatting condition for and , and either and are related in either direction by a unary cell transition, or and are related in either direction by a binary cell transition.✦ A cell word rewrites in one step to , written , if and for words such that satisfies the cell list replacement relation for and ✦; cell word reachability is the reflexive and transitive closure of .✦
Under a schedule , a cell satisfies the semantic zero cell condition if its marker is full and either its head phase is acquisition, finish, or success with nonzero register, its head phase is after-gate while for head clause and register , or its head phase is success while its zero-task flag is true.✦ For and data size , a cell satisfies the unary zero cell condition if it fails the cell formatting condition for and , satisfies the semantic zero cell condition for , or lies at a palette position with checker .✦ Two cells and satisfy the binary zero cell condition if they do not form a compatible adjacent cell pair, if both lie at the same palette position , or if lies at with checker for while .✦ A word satisfies the zero cell word predicate for and if is a one-cell word satisfying the unary zero condition or a two-cell word satisfying the binary zero condition✦; a word survives under and if no word with contains a contiguous factor satisfying the zero cell word predicate.✦
A finite table cell is a cut cell if and either its marker is idle or its block index is .✦ Given a verification clause schedule and a data size , a word of cells is a cell token for and if is a cut interval for the cut cell predicate and there exists a cut cell such that survives under and .✦ Given a vector and a position of capacity , the canonical cell at for has position , idle marker, default metadata, idle checker, default head, certificate , data on side true, and data on side false if with and otherwise.✦ The canonical block concatenates the canonical cells for across , , and ✦; for a word in , the encoded word is the concatenation .✦
The Raw Codec and Machine Hierarchy
For a height , set and ; a raw bitstring of height is a Boolean vector of length .✦ Cell encoding maps each cell of capacity to a raw bitstring of length by packing nine natural-number fields (position tag and index, marker tag, arity, block index, checker tag and index, head clause, and head phase tag) into -bit little-endian binary slots in the first bits and eight Boolean fields (zero-task flag, head side, false-side and true-side data bits, certificate bit, and three head register bits) starting at bit , setting unused bits to false. For , cell decoding extracts a candidate cell from those integer and flag slots whenever each decoded tag and index lies in bounds and returns if equals the input bitstring, failing otherwise; word decoding decodes a word of raw bitstrings cell-by-cell and fails if any letter fails to decode.
Given , a schedule of capacity , and data size , two words of raw bitstrings satisfy raw word replacement if they decode to cell words satisfying the cell list replacement relation for and , and fail otherwise.✦ Replacing a contiguous factor by raw word replacement defines the raw rewriting step, whose reflexive and transitive closure is raw word reachability . A raw word is a raw token for , , and if is obtained by applying letterwise to a cell token for and .✦ A raw bitstring satisfies raw unary zero if decoding fails or yields a cell satisfying the unary zero condition for and ✦; two raw bitstrings and satisfy raw binary zero if both decode to cells satisfying the binary zero condition✦; and a raw word satisfies the zero raw word predicate if it is a singleton satisfying raw unary zero or a two-letter word satisfying raw binary zero.✦ For , a schedule of capacity , data size , a Boolean selector , and raw words and , the codec table entry returns true if and only if either , is empty, and satisfies the zero raw word predicate, or and satisfies raw word replacement.✦
Given a multiplier and a height , converting and in maps each raw bitstring of height to a scalar vector . For a word of raw bitstrings of height , the raw word embedding applies to each cell of .✦
For a tape alphabet and state set , a Turing machine command specifies a written symbol in , a next state in , and a head motion (left, stay, or right), and a tape cell label records a symbol in , an origin Boolean flag, and an optional active head in . A transition table induces a local three-cell update computing the new center label from a cell and its left and right neighbors. A binary tape label coding of bit width consists of encoding and decoding maps between labels and Boolean vectors of length satisfying left invertibility✦; for finite and with a blank symbol, the one-hot coding takes to be the number of labels and encodes each label by its indicator vector, and any coding turns the local three-cell update into a Boolean map on bits. A circuit wire on indices is a constant Boolean or an index below ✦, and a combinational not-AND (NAND) circuit with inputs and gates appends two-input NAND gates drawing from the inputs and earlier gates, evaluating all wires recursively and generating the list of three-wire circuit clauses constraining its gates over all wires. A circuit realization of under supplies a gate count , a NAND circuit on inputs, and output wires computing the -bit encoded local transition; such a realization exists for any finite coding and transition table.
Given a stack index type , token alphabet , and state set , a multi-track stack machine executes push, pop, and halt instructions on multi-track tape symbols via a compiler into one-tape transition commands that scan right to the top of each track and return to the origin. A universal stack machine over interprets programs of push, pop, halt, bit, tick, separator, and stop tokens across simulated registers in , front and back tape stacks, and a unary program counter stack; a universal input decoder reverses bit tokens between designated registers, skips a unary-prefixed header, decodes fixed-width one-hot packets of tokens (whose packet bit representation width is the cardinality of the optional universal token type), and passes control to the universal interpreter. For any natural number , let be if and the binary bit-length of otherwise, and let the prefix encoding concatenate true bits, false, and the binary digits of from most to least significant; the specialization of two Boolean lists and prepends true to ✦, and a wrapped input machine peels off such true-marked headers before invoking the universal input decoder. Instantiating this wrapped machine on three registers (including source and destination registers) yields the timed one-tape machine transition , its one-hot coding of positive bit width , its circuit realization of gate count , and the -bit encodings of the blank, bit, initial, and accepting halting-head tape labels.
At bound , an addressable wire reading is a constant Boolean or a cell memory address, and an addressable input bit is a fixed Boolean or a data bit address with a negation flag. An addressable three-wire clause pairs three wire readings with a Boolean truth function on three bits, holds under a Boolean memory assignment when its truth function evaluates to true on its wire readings, and compiles to a verification clause by routing constant wires to certificate address with their constant bits incorporated into the truth function; special constructions provide unit clauses, equality clauses, initial input-bit clauses, and circuit clauses lifted through an address map. Given a bound , a Boolean program , a word-length parameter with , an arity , and a Boolean flag , the source machine input sequence concatenates the fixed bits and with unnegated data-address references for blocks of length on one side when and both sides when . With bit vectors , a bit-encoding map , and an origin column , the initial row configuration places fixed at column for each bit , transforms the -th entry of the input sequence at column via the map (fixing a data-address reference to a constant when the map is constant and flipping its negation flag when the map sends false to true), and places fixed elsewhere.
Given positive bit width , positive time , tape width , gate count , and an origin column below , a tableau layout requires the certificate variable count and the total tableau clause count to be at most . Mapping tape cell variables across and gate variables across into certificate addresses below , and pairing them with a combinational NAND circuit on inputs with gates, output wires, a task-indexed initial row of addressable input bits (such as the predicate initial row built from the source machine input sequence with and zero-task flag at the layout origin), blank bits, and accepting bits, the layout produces a verification clause schedule enforcing initial row, left and right blank boundary, local circuit transition, and origin acceptance constraints under the assembled assignment of any data and certificate vectors.
For bit width , gate count , multiplier , height , and program length , set and ; the layout parameter bounds predicate holds if (1)✦ When (1) holds for a Boolean program of length , the source machine layout of capacity , time , width , and origin yields the source machine initial inputs and clause schedule of capacity on data of size .
Given a multiplier , a self-simulating machine hierarchy consists of a Boolean program and a natural number threshold such that for every height , the self-referential machine code obtained by specializing to itself satisfies (1), and for every verification task and data assignment on capacity , there exists a certificate vector on satisfying all tableau clauses of the source machine layout for and at height under the assembled assignment if and only if the codec table entry at height for the source machine schedule of at height , data size , and selector evaluates to true on the tuple of candidate words of height from the false side together with either the empty list when or the candidate words from the true side when .✦ At each height , determines the hierarchy clause schedule of capacity given by the source machine schedule for ✦, and a hierarchy token of at height is a raw token for , , and data size .✦
The Claim
Theorem 1. Let and be natural numbers with , and let be a verification clause schedule of capacity . If and are cut cells of capacity , is a cut-free word of cells of capacity , and survives under and , then there exists a word of vectors in such that (2)✦
Let and be natural numbers with , and let be a verification clause schedule of capacity . If and are cut cells of capacity and is a word of cells of capacity such that survives under and , then there exists a word of vectors in such that (3)✦
Let and be natural numbers, and let be a verification clause schedule of capacity . If is a word of cells of capacity that satisfies cell word syntax and survives under and , then there exists a word of cells such that (4)✦
Let and be natural numbers satisfying , and let be a verification clause schedule of capacity . If is a raw token for , , and data size , then there exists a word of raw bitstrings of height such that (5)✦
Given a self-simulating machine hierarchy with multiplier and threshold , let , and let be a hierarchy token of at height . Defining the token normal form to be a word of raw bitstrings of height selected from (5) for , this word satisfies (6)✦
In the paper, the result reads: an interval between consecutive cuts in a nonzero word consists of between one and complete structural blocks and can be changed, using only replacements inside that interval, to a concatenation of canonical blocks. The library sets , renders nonzeroness as survival, cut intervals as tokens or words bounded by cut cells, complete structural blocks as length- or length- factors, and internal replacements as reachability, casting the statement in (2) through (6) across cell words, raw bitstrings with and , and machine hierarchy tokens.
What Is Checked
The normalization statements (2), (3), and (4) are stated over finite table cells of capacity , verification clause schedules of capacity , data sizes (with for (2) and (3)), cell word reachability, survival, cell word syntax, cut cells, and canonical block encodings; (5) is stated over raw bitstrings of height , raw tokens for a schedule of capacity and data size , raw word reachability, and raw word embeddings; and (6) is stated over a self-simulating machine hierarchy with multiplier and threshold , hierarchy heights , hierarchy clause schedules , hierarchy tokens, and token normal forms. The positivity claims also hold for the bit width of the source machine tape coding, the packet bit representation width, the total clause count of any tableau layout, and, for any height in a self-simulating machine hierarchy with multiplier , both and the data size .