The Setting
Take an infinite finitely presented periodic group constructed from a hierarchy of finite local rewriting systems on words of raw bitstrings indexed by height parameters . For a dilation factor , a block embedding sends words at height to blocks of words at height . The question is how to specify the finite-table verification rules and self-simulating machine hierarchy so that, for every height above a threshold, simulates height- tasks and local rules while preserving surviving words, alongside clean-word zero decoding and survival criteria for finite tables.
Machine Compilation and Tape Coding
For a tape alphabet and state set , a tape head motion is left, stay, or right, and a Turing machine command in specifies a symbol in to write, a next state in , and a head motion. A tape cell label in records a symbol in , a Boolean origin mark, and either an active head state in or no head.✦ Given a transition table , the local tape cell transition sends a three-cell neighborhood of tape cell labels to an updated center label: if carries a head and symbol , then writes its symbol, keeps the origin mark, and keeps the next state when the motion is stay (clearing the head otherwise); if has no head, it keeps its symbol and origin mark and takes the next state from if carries a head moving right, or else from if carries a head moving left. For a tape alphabet and state set , a binary tape label coding of bit width specifies an encoding and a decoding that left-inverts the encoding.✦ When and are finite and is chosen, the one-hot tape label coding sets , maps each label to its indicator vector under a canonical enumeration, and decodes vectors outside the image to . For a binary tape label coding of bit width and a transition table , the encoded Boolean transition function is the function that decodes three -bit slices, applies the local transition , and re-encodes.
Given a wire bound , a circuit wire is either a constant Boolean bit or a wire index below , evaluated under a Boolean assignment on the wires by returning the constant bit or the assigned value. A combinational not-and (NAND) circuit with inputs and gates is an ordered sequence of two-input NAND gates built inductively from the empty circuit, where each appended gate draws its two input wires from the inputs and earlier gate outputs✦; recursive evaluation extends any input vector in to all wires. A three-wire circuit clause on wires pairs three circuit wires with a Boolean truth function on ✦, and the defining clauses of a circuit collect three NAND constraint clauses per gate relating its embedded inputs to its output wire. For a binary tape label coding of bit width and a transition table , a circuit realization of consists of a gate count , a NAND circuit on inputs with gates, and output wires evaluating to on every vector in ; every finite Boolean function admits such a realization.
For a stack index set , token alphabet , and state set , a stack machine instruction pushes a token in onto stack and moves to a next state in , pops from stack and branches on the absent or present popped token to a next state, or halts.✦ A multi-track stack symbol consists of a Boolean origin flag and a track map assigning either nothing or a token in to each ✦, while a stack simulation state is ready at , seeking to push or pop on stack , reading after stepping back on stack , or returning to the origin.✦ The stack machine tape compiler converts any stack program into a one-tape transition table on multi-track symbols and simulation states: from a ready state it stays on halt or moves right in push-find or pop-find mode, scans right past occupied entries of track , then either writes the pushed token and returns left or steps left in pop-read mode to read and clear the top entry (yielding empty at an origin cell) before returning left to the origin.✦
Taking the three-element register index set with source register and destination register , the universal stack register type over any index set comprises simulated registers together with front, back, and program counter stacks, and the universal stack instruction token type consists of push-bit, pop, halt-with-result, data bit, unary tick, branch separator, and end-of-program stop tokens. The universal stack machine interpreter acts on nine control states (reset, restore, pick, read, remember, push on , pop on , save-target, and stopped) and three scan modes (skip, opcode, and target in phases two-before, one-before, during, and after) via its token transition function: it moves tokens from back to front, pops the program counter to skip instructions or read opcodes, executes push, pop, or halt tokens, and counts separators across the target phases while recording ticks in the during phase onto the program counter to locate branch targets, halting with false on malformed input or unexpected end of tape.
For , the binary length is when and the bit-length of otherwise, and the prefix encoding concatenates true bits, one false delimiter bit, and the most-significant-first binary digits of . Given two finite Boolean sequences and , the program specialization bit encoding prepends to . For a finite register type , an input token packet is either empty or a universal stack instruction token, encoded by a one-hot Boolean vector of positive width with a left-inverse decoder. Starting from an all-false packet buffer and collecting bits one by one until decoding a token or entering universal reset, the universal input decoding machine reverses bits from to , counts leading true bits of a unary header onto the program counter to skip that many bits, decodes -bit packets into tokens pushed onto the back stack, and delegates to the universal interpreter. Wrapping this decoder, the wrapped input machine reverses bits from to , repeatedly skips unary-prefixed wrapper blocks while a marker bit is true, and enters initial packet collection on false.
Instantiating the wrapped input machine on defines the timed tape stack type, token alphabet, inner state type, multi-track alphabet , simulation state set , and compiled one-tape transition function , together with the blank symbol (origin false and empty tracks), origin symbol (origin true and empty tracks), bit symbol (placing a bit token on the track), initial ready-reverse state , halting stopped states, and output labels for (combining the origin symbol, origin mark true, and the halting state for ). The source machine tape coding is the one-hot tape label coding of and centered at the blank symbol, of positive bit width . Its local transition circuit realization chooses a NAND circuit on inputs with gates and output wires realizing , and encoding the blank label , the accepting output label for , the initial label , and the bit labels under yields the -bit vectors , , , and for .
Tableau Layouts and Verification Schedules
For a capacity bound , a cell memory address is either a data address with side , block index , and position , or a certificate address at position .✦ A three-bit register state is a vector in ✦, and a verification clause consists of three cell memory addresses and a Boolean truth function on .✦ A verification task is a pair of an arity and a Boolean zero-task flag , and a verification clause schedule of capacity assigns to each task a positive clause count and a family of verification clauses indexed below .✦
An addressable wire reading is either a fixed Boolean bit or a cell memory address, evaluated under a Boolean assignment on addresses of capacity . An addressable input bit is either a fixed Boolean bit or a data address paired with a Boolean negation flag.✦ A three-wire addressable clause consists of three wire readings and a Boolean truth function on ; it holds under an address assignment when its truth function returns true on the three wire evaluations, and it compiles to a verification clause by mapping constant wires to certificate address while fixing their bits in the truth function and converting remaining register bits to Booleans via . Addressable clauses are of four kinds: unit constraints fixing a reading to a Boolean , equality constraints enforcing or according to a direction bit, lifted circuit clauses mapped along a wire-to-address map, and initial value constraints equating a reading either to a fixed bit or, according to a direction bit, to an optionally negated data bit.
For bit width , gate count , time bound , tape width , and capacity , a tableau layout specifies an origin column subject to and ✦, where the total certificate variable count (1) and the total tableau clause count (2) are given by (1)✦ and (2)✦ Here certificate addresses below index the tape cell bits at time , column , and bit together with the gate bits at step , interior column (), and gate . Given a NAND circuit on inputs with gates and output wires, a task-indexed initial row of addressable input bits, and vectors , the tableau schedule gives every task the clause count and compiles clauses enforcing four requirements: at time , each column and bit matches the initial row; at times on columns and , every cell matches ; at each step and interior column , the defining clauses of and equality constraints link the tape bits of columns at time and the gate bits to the tape bits of column at time ; and at time and column , the tape bits match (padding indices at or above the clause count with a trivial true constraint). Assembling a data assignment on data addresses with a certificate assignment on indices below produces a full assignment on all cell memory addresses.✦
For integers and and a flag , the input data bit sequence lists unnegated references to data addresses of blocks and positions on side false when , and on both false and true sides when .✦ Given a program bit list and word length with , the source machine input sequence concatenates fixed bits for with the input data bit sequence for . Given vectors , a bit-encoding map , an origin column , and an input list, the initial row configuration places at column (when ), transforms each entry at column with through (collapsing constant coordinates to fixed bits and toggling the negation flag when ), and places elsewhere; the predicate initial row sets and on the source machine input sequence for task .
Finite Tables and Checked Regions
A cell marker is idle, left wing, boundary, full active head, or right wing.✦ A block metadata record with arity bound specifies an arity , a zero-task flag , and a block index , projecting to a verification task . For a capacity , a block cell position is a core position , a palette position carrying a color , or the stop position.✦ A cell syntactic skeleton is a triple consisting of a block cell position, a cell marker, and block metadata; it is initial when and the position is core , terminal when and the position is stop, carries an active head when its marker is boundary or full, and is admissible if it is never right at an initial skeleton and never left at a terminal skeleton. Two adjacent cell syntactic skeletons satisfy structural position adjacency when core precedes core , core precedes any palette position, any palette position precedes any palette or stop position, and stop precedes core ; two adjacent skeletons satisfy internal consistency when they agree on arity and zero-task flag, their block index increments by after stop and remains unchanged otherwise, the second is not initial, and the first is not terminal. Two adjacent cell syntactic skeletons form a compatible adjacent skeleton pair if they are structurally adjacent and either the left is right-external (idle marker, boundary marker, or non-left marker at a terminal skeleton) while the right is left-external (idle marker, or non-right marker at an initial skeleton), or the left is not right-external, the right is not left-external, the left accepts the right’s marker (left accepts left, boundary, or full; all other markers accept right), the right accepts the left’s marker (right accepts full or right; all other markers accept left), and internal consistency holds.
Over colors below , a palette checker state is idle, passed seeking , or head seeking ; adjacent palette checker states are compatible for , , , and , while the terminal palette condition allows idle or head and forbids passed. A reading head state carries a Boolean side, a clause index below , a head computation phase (acquisition, read-left, read-right, before-gate, after-gate, undo-left, undo-right, finish, or success, among which acquisition, before-gate, after-gate, finish, and success are endpoint phases), and a register in . A finite table cell of capacity consists of a skeleton, a palette checker state, a pair of side-indexed data bits in , a certificate bit in , and a head state.✦ Two cells form a compatible adjacent pair when their skeletons form a compatible pair, any two adjacent palette cells have compatible checker states, and any palette cell followed by a stop cell satisfies the terminal palette condition✦; a cell is head-free if its skeleton has no active head marker and its checker is not a head.✦ Reading an address from a cell returns unless lies at core matching the address position: for a data address with equal to the cell’s block index it returns the side- data bit, and for a certificate address when the cell’s block index is it returns the certificate bit✦; the clause register delta reads the three addresses of a verification clause from .✦ For data bound , cell payload formatting requires the checker to be idle outside palette positions, the data bits to vanish at core positions , and both data and certificate bits to vanish outside core positions.✦ A cell satisfies full formatting relative to a schedule and data bound if it satisfies cell payload formatting for , its skeleton is admissible, and its marker satisfies the required invariants: idle forces default metadata , default head , true-side data zero, and certificate zero; left or right forces the default head; boundary forces clause , phase acquisition, and register ; active heads force side false when ; and full forces clause in success, clause below otherwise, and a terminal skeleton at every endpoint phase.✦
Relative to a schedule and data bound , a unary cell transition acts on a single initial or terminal cell: at an initial skeleton it turns the idle cell of at side (keeping the position, placing the side- data bit on side false, and clearing side true, certificate, metadata, and head) into the boundary cell of with head side ; at a terminal cell it moves boundary to full at clause , phase acquisition, and register ; across initial and terminal cells it advances a full head through acquisition, read-left, read-right, before-gate, gate passage at before-gate when the scheduled clause truth function accepts the register, after-gate, undo-left, undo-right, and finish; at a terminal cell with zero register in finish it steps to the next clause or to success at clause when all clauses have run; and at a terminal cell in success with it flips the head side.✦ A binary cell transition acts on two adjacent cells across eight rules: acquiring an idle neighbor to create a left wing and move the boundary head right across a compatible skeleton pair; reading or undoing the scheduled clause across a compatible full-right skeleton pair on the left or right (adding the left cell’s clause register delta to the head register on read-left and undo-right, and passing without modifying the register on read-right and undo-left); creating a palette checker head seeking on an idle palette cell adjacent to core ; advancing a checker head past a palette cell of a distinct color ; and swapping two head-free palette cells whose non-color fields agree.✦ Two cell lists and satisfy the replacement relation when every cell in and satisfies full formatting for and and either are singletons related in either direction by a unary transition or pairs related in either direction by a binary transition; replacing a subword under gives the cell word rewriting step and its reflexive-transitive closure .
A cell satisfies the semantic zero condition for if its marker is full and either its phase is acquisition, finish, or success with nonzero register, its phase is after-gate while the scheduled clause truth function rejects the register, or its phase is success with zero-task flag true.✦ A cell satisfies the unary zero condition for and if it fails full formatting, satisfies semantic zero, or sits at palette position with checker passed seeking ✦; two cells satisfy the binary zero condition if they are not a compatible adjacent pair, share the same palette position, or the first sits at palette position with checker head seeking while the second sits at stop.✦ A cell word satisfies the zero predicate if satisfies unary zero or satisfies binary zero, and a cell word satisfies the surviving predicate if no cell word with factors as with . Given a vector and capacity , the canonical cell at a block cell position has idle marker and checker, default metadata and head, certificate , and data except on side false at core , where it equals ; concatenating canonical cells over core , palette , and stop forms the canonical block of length , and concatenating canonical blocks over a list of vectors in defines the encoded cell word .
For positive integers and , a clause tour payload specifies a register increment map with and a gate predicate on , with total sum ; a head tour plan specifies payloads and a zero-task flag, and clause holds in the plan when its gate predicate holds on its total sum. A cell region with capacity and data bound is a sequence of cells for a task , each having metadata task and payload formatting for , such that the initial condition holds precisely at index , the terminal condition holds precisely at index , and consecutive cells satisfy structural position adjacency and internal consistency.✦ Defining position rank as at core , at palette, and at stop, the progress coordinate locates the unique cell in at block and core , whose side- data bit is the region slot; for , collecting the vectors in from these slots forms the region data word , while the region’s tour plan applies the scheduled clauses of for via cell deltas and truth functions. For , a checked swap replaces by inside a word over using a region with in which every clause holds in the region’s plan, checked reachability is its reflexive-transitive closure, and a word satisfies the checked zero predicate if it contains as a subword for a region with in which every clause holds.
Raw Bitstrings and the Machine Hierarchy
A raw bitstring of height is a Boolean vector of length .✦ Cell encoding packs a cell of capacity into a raw bitstring by writing integer slots of little-endian bits (storing position, marker, metadata, checker, head clause, and head phase tags and indices) in the first positions and flag bits (storing zero-task flag, head side, data bits, certificate bit, and head register bits) in the next positions, padding remaining entries with false; cell decoding parses those integer and flag slots into a candidate cell and returns precisely when recovers the input bitstring, lifting entrywise to word decoding. Relative to a schedule of capacity and data size , two words and of raw bitstrings satisfy raw replacement when and decode to cell lists satisfying ; raw unary zero holds when a raw bitstring fails to decode or decodes to a cell satisfying unary zero, raw binary zero holds when two raw bitstrings decode to cells satisfying binary zero, and a word of raw bitstrings satisfies when it is a singleton satisfying raw unary zero or a pair satisfying raw binary zero. Rewriting subwords under gives the raw step relation and its reflexive-transitive closure , a word of raw bitstrings satisfies raw survival when no word reachable from under contains a subword satisfying , and the codec entry predicate evaluates to true when either , is empty, and holds, or and holds.
Given bit width , gate count , dilation , height , and code length , let and ; the layout parameter bounds predicate holds when the seven inequalities (3) are satisfied: (3) Whenever holds for a Boolean list , the source machine tableau layout takes capacity , time , width , and origin , and the source machine schedule builds the tableau schedule of from , the predicate initial row for and word length , , and .
For a dilation factor , a self-simulating machine hierarchy consists of a Boolean program with self-referential code and a threshold such that every integer satisfies (giving the hierarchy clause schedule ) and self-certification: for every task of arity and zero-task flag and every data assignment on data addresses of capacity , there exists a certificate assignment on making all clauses of for hold under the assembled assignment if and only if , where is the -tuple of length- candidate words extracted from on side and is empty when and otherwise. For any length , the scalar conversion maps to and to . For a word of raw bitstrings of height , the block embedding is defined by (4): (4)✦
The Claim
Theorem 1. Let be a self-simulating machine hierarchy with dilation factor and threshold , let be an integer, and let and denote its hierarchy clause schedules at heights and . For any verification task of arity and zero-task flag and any -letter words of raw bitstrings of height , if , where is the empty word when and when , then (5) holds: (5)✦ For any words of raw bitstrings of height satisfying , (6) holds: (6)✦ For any word of raw bitstrings of height satisfying , (7) holds: (7)✦ For any word of raw bitstrings of height satisfying , (8) holds: (8)✦ Independently, let be any verification clause schedule of capacity and let . For any word of length over and any cell words of capacity satisfying and , (9) holds: (9)✦ For any finite word over such that no word over with satisfies , (10) holds: (10)✦
In the paper, the result reads: the substitution simulates every elementary next-parameter replacement and zero declaration; moreover, if is a nonzero word at parameter , no sequence of lower-parameter replacements starting from can reach a zero declaration. In the library’s statement, elementary replacements, zero declarations, and verification tasks at parameter are represented by the raw replacement, zero, and entry predicates at height with data size , lower-parameter replacement sequences by raw reachability at height with data size , and nonvanishing words (in the contrapositive direction of faithfulness) by the raw survival predicate, alongside the clean-word zero decoding and survival statements for finite-table schedules.
What Is Checked
The simulation and faithfulness statements (5) through (8) are stated over a self-simulating machine hierarchy with dilation factor and threshold at any integer height , built from the one-hot tape coding and circuit realization of the compiled wrapped universal stack machine, the tableau layout and verification schedule, the raw bitstring encoding and decoding, and the block embedding , while the clean-word statements (9) and (10) are stated over an arbitrary verification clause schedule of capacity , data bound , finite-table cell rewriting, canonical word encoding, and checked regions. Beyond the main claim, the library proves for these constructions that for any integer , both and the data size are positive and also meets , and proves positivity of the tape coding bit width , the packet bit representation width, and the total tableau clause count of any tableau layout.