OctoInformBeta

OpenAI preprint, September 2026 · §2. A hierarchy defined by finite local rules

Lemma 2.7: At height hh above the threshold with multiplier DD, the embedding EhE_h simulates height-DhDh rules and preserves survival, alongside clean-word finite-table criteria

Block embeddings simulate hierarchy rules above the threshold.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

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 hh. For a dilation factor D≥2D \ge 2, a block embedding EhE_h sends words at height DhDh to blocks of words at height hh. The question is how to specify the finite-table verification rules and self-simulating machine hierarchy so that, for every height hh above a threshold, EhE_h simulates height-DhDh 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 Γ\Gamma and state set QQ, a tape head motion is left, stay, or right, and a Turing machine command in Cmd⁡(Γ,Q)\operatorname{Cmd}(\Gamma, Q) specifies a symbol in Γ\Gamma to write, a next state in QQ, and a head motion. A tape cell label in Label⁡(Γ,Q)\operatorname{Label}(\Gamma, Q) records a symbol in Γ\Gamma, a Boolean origin mark, and either an active head state in QQ or no head.✦ Given a transition table δ:Q→Γ→Cmd⁡(Γ,Q)\delta : Q \to \Gamma \to \operatorname{Cmd}(\Gamma, Q), the local tape cell transition sends a three-cell neighborhood (cL,c,cR)(c_L, c, c_R) of tape cell labels to an updated center label: if cc carries a head qq and symbol σ\sigma, then δ(q,σ)\delta(q, \sigma) writes its symbol, keeps the origin mark, and keeps the next state when the motion is stay (clearing the head otherwise); if cc has no head, it keeps its symbol and origin mark and takes the next state from cLc_L if cLc_L carries a head moving right, or else from cRc_R if cRc_R carries a head moving left. For a tape alphabet Γ\Gamma and state set QQ, a binary tape label coding KcodK_{\mathrm{cod}} of bit width β>0\beta > 0 specifies an encoding Label⁡(Γ,Q)→{false,true}β\operatorname{Label}(\Gamma, Q) \to \{\mathrm{false}, \mathrm{true}\}^\beta and a decoding {false,true}β→Label⁡(Γ,Q)\{\mathrm{false}, \mathrm{true}\}^\beta \to \operatorname{Label}(\Gamma, Q) that left-inverts the encoding.✦ When Γ\Gamma and QQ are finite and blank∈Γ\mathrm{blank} \in \Gamma is chosen, the one-hot tape label coding sets β=|Label⁡(Γ,Q)|\beta = |\operatorname{Label}(\Gamma, Q)|, maps each label to its indicator vector under a canonical enumeration, and decodes vectors outside the image to (blank,false,no head)(\mathrm{blank}, \mathrm{false}, \text{no head}). For a binary tape label coding of bit width β\beta and a transition table δ:Q→Γ→Cmd⁡(Γ,Q)\delta : Q \to \Gamma \to \operatorname{Cmd}(\Gamma, Q), the encoded Boolean transition function τδ:{false,true}3β→{false,true}β\tau_\delta : \{\mathrm{false}, \mathrm{true}\}^{3\beta} \to \{\mathrm{false}, \mathrm{true}\}^\beta is the function that decodes three β\beta-bit slices, applies the local transition δ\delta, and re-encodes.

Given a wire bound nn, a circuit wire is either a constant Boolean bit or a wire index below nn, evaluated under a Boolean assignment on the nn wires by returning the constant bit or the assigned value. A combinational not-and (NAND) circuit with II inputs and gg gates is an ordered sequence of gg two-input NAND gates built inductively from the empty circuit, where each appended gate draws its two input wires from the II inputs and earlier gate outputs✦; recursive evaluation extends any input vector in {false,true}I\{\mathrm{false}, \mathrm{true}\}^I to all I+gI + g wires. A three-wire circuit clause on nn wires pairs three circuit wires with a Boolean truth function on {false,true}3\{\mathrm{false}, \mathrm{true}\}^3✦, 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 β\beta and a transition table δ\delta, a circuit realization of τδ\tau_\delta consists of a gate count gg, a NAND circuit on 3β3\beta inputs with gg gates, and β\beta output wires evaluating to τδ\tau_\delta on every vector in {false,true}3β\{\mathrm{false}, \mathrm{true}\}^{3\beta}; every finite Boolean function admits such a realization.

For a stack index set KK, token alphabet Γ0\Gamma_0, and state set Q0Q_0, a stack machine instruction pushes a token in Γ0\Gamma_0 onto stack k∈Kk \in K and moves to a next state in Q0Q_0, pops from stack kk 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 Γ0\Gamma_0 to each k∈Kk \in K✦, while a stack simulation state is ready at q∈Q0q \in Q_0, seeking to push or pop on stack kk, reading after stepping back on stack kk, or returning to the origin.✦ The stack machine tape compiler converts any stack program PP 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 kk, 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 K0={⊥,0,1}K_0 = \{\bot, 0, 1\} with source register src=1\mathrm{src} = 1 and destination register dst=0\mathrm{dst} = 0, the universal stack register type over any index set KK comprises simulated registers k∈Kk \in K 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 k∈Kk \in K, pop on k∈Kk \in K, 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 n∈ℕn \in \mathbb{N}, the binary length binSize⁡(n)\operatorname{binSize}(n) is 11 when n=0n = 0 and the bit-length of nn otherwise, and the prefix encoding enc⁡(n)\operatorname{enc}(n) concatenates binSize⁡(n)\operatorname{binSize}(n) true bits, one false delimiter bit, and the most-significant-first binary digits bin⁡(n)\operatorname{bin}(n) of nn. Given two finite Boolean sequences tt and vv, the program specialization bit encoding spec⁡(t,v)\operatorname{spec}(t, v) prepends true\mathrm{true} to enc⁡(|t|)⋅t⋅enc⁡(|v|)⋅v\operatorname{enc}(|t|) \cdot t \cdot \operatorname{enc}(|v|) \cdot v. For a finite register type KK, an input token packet is either empty or a universal stack instruction token, encoded by a one-hot Boolean vector of positive width wKw_K 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 src\mathrm{src} to dst\mathrm{dst}, counts leading true bits of a unary header onto the program counter to skip that many bits, decodes wKw_K-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 src\mathrm{src} to dst\mathrm{dst}, 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 K0K_0 defines the timed tape stack type, token alphabet, inner state type, multi-track alphabet Γ\Gamma, simulation state set QQ, and compiled one-tape transition function δ\delta, 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 src\mathrm{src} track), initial ready-reverse state qinitq_{\mathrm{init}}, halting stopped states, and output labels for b∈{false,true}b \in \{\mathrm{false}, \mathrm{true}\} (combining the origin symbol, origin mark true, and the halting state for bb). The source machine tape coding KsrcK_{\mathrm{src}} is the one-hot tape label coding of Γ\Gamma and QQ centered at the blank symbol, of positive bit width β\beta. Its local transition circuit realization chooses a NAND circuit clocc_{\mathrm{loc}} on 3β3\beta inputs with gg gates and β\beta output wires realizing τδ\tau_\delta, and encoding the blank label (blank,false,no head)(\mathrm{blank}, \mathrm{false}, \text{no head}), the accepting output label for true\mathrm{true}, the initial label (origin,true,qinit)(\mathrm{origin}, \mathrm{true}, q_{\mathrm{init}}), and the bit labels (bit⁡(b),false,no head)(\operatorname{bit}(b), \mathrm{false}, \text{no head}) under KsrcK_{\mathrm{src}} yields the β\beta-bit vectors bblankb_{\mathrm{blank}}, baccb_{\mathrm{acc}}, binitb_{\mathrm{init}}, and bbit(b)b_{\mathrm{bit}}(b) for b∈{false,true}b \in \{\mathrm{false}, \mathrm{true}\}.

Tableau Layouts and Verification Schedules

For a capacity bound qq, a cell memory address is either a data address (s,b,p)(s, b, p) with side s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, block index b∈{0,…,9}b \in \{0, \dots, 9\}, and position p<qp < q, or a certificate address at position p<qp < q.✦ A three-bit register state is a vector in 𝔽23\mathbb{F}_2^3✦, and a verification clause consists of three cell memory addresses and a Boolean truth function on 𝔽23\mathbb{F}_2^3.✦ A verification task tt is a pair (at,Zt)(a_t, Z_t) of an arity at∈{0,…,9}a_t \in \{0, \dots, 9\} and a Boolean zero-task flag ZtZ_t, and a verification clause schedule SS of capacity qq assigns to each task tt a positive clause count mS(t)≤qm_S(t) \le q and a family of verification clauses indexed below qq.✦

An addressable wire reading is either a fixed Boolean bit or a cell memory address, evaluated under a Boolean assignment on addresses of capacity qq. 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 {false,true}3\{\mathrm{false}, \mathrm{true}\}^3; 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 00 while fixing their bits in the truth function and converting remaining 𝔽2\mathbb{F}_2 register bits to Booleans via z↦(z=1)z \mapsto (z = 1). Addressable clauses are of four kinds: unit constraints fixing a reading to a Boolean bb, equality constraints enforcing v0⟹v1v_0 \implies v_1 or v1⟹v0v_1 \implies v_0 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 β>0\beta > 0, gate count gg, time bound T>0T > 0, tape width W≥3W \ge 3, and capacity qq, a tableau layout LL specifies an origin column oL<Wo_L < W subject to Ncert(β,g,T,W)≤qN_{\mathrm{cert}}(\beta, g, T, W) \le q and Ncl(β,g,T,W)≤qN_{\mathrm{cl}}(\beta, g, T, W) \le q✦, where the total certificate variable count (1) and the total tableau clause count (2) are given by Ncert(β,g,T,W)=βWT+g(W−2)(T−1),N_{\mathrm{cert}}(\beta, g, T, W) = \beta W T + g(W - 2)(T - 1),(1)✦ and Ncl(β,g,T,W)=2βW+2β(T−1)+(3g+2β)(W−2)(T−1)+β.N_{\mathrm{cl}}(\beta, g, T, W) = 2\beta W + 2\beta(T - 1) + (3g + 2\beta)(W - 2)(T - 1) + \beta.(2)✦ Here certificate addresses below Ncert(β,g,T,W)N_{\mathrm{cert}}(\beta, g, T, W) index the βWT\beta W T tape cell bits at time t<Tt < T, column j<Wj < W, and bit r<βr < \beta together with the g(W−2)(T−1)g(W - 2)(T - 1) gate bits at step t<T−1t < T - 1, interior column j+1j + 1 (0≤j<W−20 \le j < W - 2), and gate u<gu < g. Given a NAND circuit cc on 3β3\beta inputs with gg gates and β\beta output wires, a task-indexed initial row of addressable input bits, and vectors blank,accept∈{false,true}β\mathrm{blank}, \mathrm{accept} \in \{\mathrm{false}, \mathrm{true}\}^\beta, the tableau schedule gives every task the clause count Ncl(β,g,T,W)N_{\mathrm{cl}}(\beta, g, T, W) and compiles clauses enforcing four requirements: at time 00, each column and bit matches the initial row; at times 1,…,T−11, \dots, T - 1 on columns 00 and W−1W - 1, every cell matches blank\mathrm{blank}; at each step t<T−1t < T - 1 and interior column j+1j + 1, the defining clauses of cc and 2β2\beta equality constraints link the 3β3\beta tape bits of columns j,j+1,j+2j, j + 1, j + 2 at time tt and the gg gate bits to the β\beta tape bits of column j+1j + 1 at time t+1t + 1; and at time T−1T - 1 and column oLo_L, the tape bits match accept\mathrm{accept} (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 qq produces a full assignment on all cell memory addresses.✦

For integers 0<d≤q0 < d \le q and 0<l≤100 < l \le 10 and a flag ZZ, the input data bit sequence lists unnegated references to data addresses of blocks 0,…,l−10, \dots, l - 1 and positions 0,…,d−10, \dots, d - 1 on side false when Z=trueZ = \mathrm{true}, and on both false and true sides when Z=falseZ = \mathrm{false}.✦ Given a program bit list aa and word length HH with 0<10000H≤q0 < 10000 H \le q, the source machine input sequence concatenates fixed bits for enc⁡(|a|)⋅a⋅enc⁡(H)⋅enc⁡(l)⋅[Z]\operatorname{enc}(|a|) \cdot a \cdot \operatorname{enc}(H) \cdot \operatorname{enc}(l) \cdot [Z] with the input data bit sequence for d=10000Hd = 10000 H. Given vectors blank,origin∈{false,true}β\mathrm{blank}, \mathrm{origin} \in \{\mathrm{false}, \mathrm{true}\}^\beta, a bit-encoding map sym:{false,true}→{false,true}β\mathrm{sym} : \{\mathrm{false}, \mathrm{true}\} \to \{\mathrm{false}, \mathrm{true}\}^\beta, an origin column oo, and an input list, the initial row configuration places origin\mathrm{origin} at column oo (when o<Wo < W), transforms each entry at column j>oj > o with j−(o+1)<|input|j - (o + 1) < |\mathrm{input}| through sym\mathrm{sym} (collapsing constant coordinates to fixed bits and toggling the negation flag when sym(false)r=true\mathrm{sym}(\mathrm{false})_r = \mathrm{true}), and places blank\mathrm{blank} elsewhere; the predicate initial row sets o=oLo = o_L and l=at+1l = a_t + 1 on the source machine input sequence for task tt.

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 1010 specifies an arity a<10a < 10, a zero-task flag ZZ, and a block index b≤ab \le a, projecting to a verification task (a,Z)(a, Z). For a capacity qq, a block cell position is a core position p<qp < q, a palette position carrying a color γ<q\gamma < q, 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 b=0b = 0 and the position is core 00, terminal when b=ab = a 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 pp precedes core p+1p + 1, core q−1q - 1 precedes any palette position, any palette position precedes any palette or stop position, and stop precedes core 00; two adjacent skeletons satisfy internal consistency when they agree on arity and zero-task flag, their block index increments by 11 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 qq, a palette checker state is idle, passed seeking xx, or head seeking xx; adjacent palette checker states are compatible for (idle,idle)(\mathrm{idle}, \mathrm{idle}), (passedx,passedx)(\mathrm{passed}\, x, \mathrm{passed}\, x), (passedx,headx)(\mathrm{passed}\, x, \mathrm{head}\, x), and (headx,idle)(\mathrm{head}\, x, \mathrm{idle}), while the terminal palette condition allows idle or head and forbids passed. A reading head state carries a Boolean side, a clause index below qq, 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 𝔽23\mathbb{F}_2^3. A finite table cell cc of capacity qq consists of a skeleton, a palette checker state, a pair of side-indexed data bits in 𝔽2\mathbb{F}_2, a certificate bit in 𝔽2\mathbb{F}_2, 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 cc returns 00 unless cc lies at core rr matching the address position: for a data address (s,b′,p)(s, b', p) with b′b' equal to the cell’s block index bb it returns the side-ss data bit, and for a certificate address when the cell’s block index bb is 00 it returns the certificate bit✦; the clause register delta Δ(C,c)∈𝔽23\Delta(C, c) \in \mathbb{F}_2^3 reads the three addresses of a verification clause CC from cc.✦ For data bound dd, cell payload formatting requires the checker to be idle outside palette positions, the data bits to vanish at core positions p≥dp \ge d, and both data and certificate bits to vanish outside core positions.✦ A cell satisfies full formatting relative to a schedule SS and data bound dd if it satisfies cell payload formatting for dd, its skeleton is admissible, and its marker satisfies the required invariants: idle forces default metadata (0,false,0)(0, \mathrm{false}, 0), default head (false,0,acquisition,0)(\mathrm{false}, 0, \mathrm{acquisition}, 0), true-side data zero, and certificate zero; left or right forces the default head; boundary forces clause 00, phase acquisition, and register 00; active heads force side false when Z=trueZ = \mathrm{true}; and full forces clause 00 in success, clause below mS(t)m_S(t) otherwise, and a terminal skeleton at every endpoint phase.✦

Relative to a schedule SS and data bound dd, a unary cell transition acts on a single initial or terminal cell: at an initial skeleton cc it turns the idle cell of cc at side ss (keeping the position, placing the side-ss data bit on side false, and clearing side true, certificate, metadata, and head) into the boundary cell of cc with head side ss; at a terminal cell it moves boundary to full at clause 00, phase acquisition, and register 00; 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 00 when all mS(t)m_S(t) clauses have run; and at a terminal cell in success with Z=falseZ = \mathrm{false} 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 xx on an idle palette cell adjacent to core q−1q - 1; advancing a checker head past a palette cell of a distinct color v≠xv \ne x; and swapping two head-free palette cells whose non-color fields agree.✦ Two cell lists vv and ww satisfy the replacement relation Repl⁡S,d(v,w)\operatorname{Repl}_{S, d}(v, w) when every cell in vv and ww satisfies full formatting for SS and dd and either v,wv, w are singletons related in either direction by a unary transition or pairs related in either direction by a binary transition; replacing a subword under Repl⁡S,d\operatorname{Repl}_{S, d} gives the cell word rewriting step and its reflexive-transitive closure Reach⁡S,d\operatorname{Reach}_{S, d}.

A cell satisfies the semantic zero condition for SS 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 SS and dd if it fails full formatting, satisfies semantic zero, or sits at palette position xx with checker passed seeking xx✦; 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 xx with checker head seeking y≠xy \ne x while the second sits at stop.✦ A cell word vv satisfies the zero predicate Zero⁡S,d(v)\operatorname{Zero}_{S, d}(v) if v=[c]v = [c] satisfies unary zero or v=[a,b]v = [a, b] satisfies binary zero, and a cell word ww satisfies the surviving predicate Survives⁡S,d(w)\operatorname{Survives}_{S, d}(w) if no cell word uu with Reach⁡S,d(w,u)\operatorname{Reach}_{S, d}(w, u) factors as pzsp z s with Zero⁡S,d(z)\operatorname{Zero}_{S, d}(z). Given a vector v∈𝔽2dv \in \mathbb{F}_2^d and capacity qq, the canonical cell at a block cell position pp has idle marker and checker, default metadata and head, certificate 00, and data 00 except on side false at core r<dr < d, where it equals vrv_r; concatenating canonical cells over core 0,…,q−10, \dots, q - 1, palette 0,…,q−10, \dots, q - 1, and stop forms the canonical block of length 2q+12q + 1, and concatenating canonical blocks over a list uu of vectors in 𝔽2d\mathbb{F}_2^d defines the encoded cell word Enc⁡q(u)\operatorname{Enc}_q(u).

For positive integers mm and NN, a clause tour payload specifies a register increment map ι:{0,…,N−1}→𝔽23\iota : \{0, \dots, N - 1\} \to \mathbb{F}_2^3 with ι(N−1)=0\iota(N - 1) = 0 and a gate predicate on 𝔽23\mathbb{F}_2^3, with total sum ∑i=0N−1ι(i)\sum_{i=0}^{N-1} \iota(i); a head tour plan specifies mm payloads and a zero-task flag, and clause j<mj < m holds in the plan when its gate predicate holds on its total sum. A cell region RR with capacity qq and data bound dd is a sequence of N>0N > 0 cells for a task tt, each having metadata task tt and payload formatting for dd, such that the initial condition holds precisely at index 00, the terminal condition holds precisely at index N−1N - 1, and consecutive cells satisfy structural position adjacency and internal consistency.✦ Defining position rank as pp at core pp, qq at palette, and q+1q + 1 at stop, the progress coordinate b(q+2)+rank⁡(c)b(q + 2) + \operatorname{rank}(c) locates the unique cell in RR at block b≤atb \le a_t and core p<qp < q, whose side-ss data bit is the region slot; for d≤qd \le q, collecting the at+1a_t + 1 vectors in 𝔽2d\mathbb{F}_2^d from these slots forms the region data word WR(s)W_R(s), while the region’s tour plan applies the scheduled clauses of SS for tt via cell deltas and truth functions. For d≤qd \le q, a checked swap replaces WR(s)W_R(s) by WR(¬s)W_R(\neg s) inside a word over 𝔽2d\mathbb{F}_2^d using a region RR with Zt=falseZ_t = \mathrm{false} in which every clause holds in the region’s plan, checked reachability Reach⁡S,dchk\operatorname{Reach}^{\mathrm{chk}}_{S, d} is its reflexive-transitive closure, and a word satisfies the checked zero predicate Zero⁡S,dchk\operatorname{Zero}^{\mathrm{chk}}_{S, d} if it contains WR(false)W_R(\mathrm{false}) as a subword for a region RR with Zt=trueZ_t = \mathrm{true} in which every clause holds.

Raw Bitstrings and the Machine Hierarchy

A raw bitstring of height h>0h > 0 is a Boolean vector of length 10000h10000 h.✦ Cell encoding encode⁡h\operatorname{encode}_h packs a cell cc of capacity 2h2^h into a raw bitstring by writing 3232 integer slots of 2h2h little-endian bits (storing position, marker, metadata, checker, head clause, and head phase tags and indices) in the first 64h64 h positions and 512512 flag bits (storing zero-task flag, head side, data bits, certificate bit, and head register bits) in the next 512512 positions, padding remaining entries with false; cell decoding decode⁡h\operatorname{decode}_h parses those integer and flag slots into a candidate cell cc and returns cc precisely when encode⁡h(c)\operatorname{encode}_h(c) recovers the input bitstring, lifting entrywise to word decoding. Relative to a schedule SS of capacity 2h2^h and data size dd, two words vv and ww of raw bitstrings satisfy raw replacement Repl⁡h,S,draw(v,w)\operatorname{Repl}^{\mathrm{raw}}_{h, S, d}(v, w) when vv and ww decode to cell lists satisfying Repl⁡S,d\operatorname{Repl}_{S, d}; 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 vv of raw bitstrings satisfies Zero⁡h,S,draw(v)\operatorname{Zero}^{\mathrm{raw}}_{h, S, d}(v) when it is a singleton satisfying raw unary zero or a pair satisfying raw binary zero. Rewriting subwords under Repl⁡h,S,draw\operatorname{Repl}^{\mathrm{raw}}_{h, S, d} gives the raw step relation and its reflexive-transitive closure Reach⁡h,S,draw\operatorname{Reach}^{\mathrm{raw}}_{h, S, d}, a word ww of raw bitstrings satisfies raw survival Survives⁡h,S,draw(w)\operatorname{Survives}^{\mathrm{raw}}_{h, S, d}(w) when no word reachable from ww under Reach⁡h,S,draw\operatorname{Reach}^{\mathrm{raw}}_{h, S, d} contains a subword satisfying Zero⁡h,S,draw\operatorname{Zero}^{\mathrm{raw}}_{h, S, d}, and the codec entry predicate Entry⁡h,S,d(Z,v,w)\operatorname{Entry}_{h, S, d}(Z, v, w) evaluates to true when either Z=trueZ = \mathrm{true}, ww is empty, and Zero⁡h,S,draw(v)\operatorname{Zero}^{\mathrm{raw}}_{h, S, d}(v) holds, or Z=falseZ = \mathrm{false} and Repl⁡h,S,draw(v,w)\operatorname{Repl}^{\mathrm{raw}}_{h, S, d}(v, w) holds.

Given bit width β\beta, gate count gg, dilation DD, height hh, and code length nn, let T=2⌊h/5⌋T = 2^{\lfloor h/5 \rfloor} and W=4TW = 4 T; the layout parameter bounds predicate Fits⁡(β,g,D,h,n)\operatorname{Fits}(\beta, g, D, h, n) holds when the seven inequalities (3) are satisfied: 64h+512≤10000h,10≤22h,2h≤22h,10000Dh≤2h,Ncert(β,g,T,W)≤2h,Ncl(β,g,T,W)≤2h,n+2binSize⁡(n)+2binSize⁡(Dh)+12+20(10000Dh)<⌊T/4⌋.\begin{aligned} 64h + 512 &\le 10000h, & 10 &\le 2^{2h}, & 2^h &\le 2^{2h}, & 10000 D h &\le 2^h, \\ N_{\mathrm{cert}}(\beta, g, T, W) &\le 2^h, & N_{\mathrm{cl}}(\beta, g, T, W) &\le 2^h, \\ n + 2\operatorname{binSize}(n) + 2\operatorname{binSize}(D h) &+ 12 + 20(10000 D h) < \lfloor T/4 \rfloor. \end{aligned}(3) Whenever Fits⁡(β,g,D,h,|a|)\operatorname{Fits}(\beta, g, D, h, |a|) holds for a Boolean list aa, the source machine tableau layout LhL_h takes capacity 2h2^h, time TT, width WW, and origin 2T2T, and the source machine schedule builds the tableau schedule of LhL_h from clocc_{\mathrm{loc}}, the predicate initial row for aa and word length DhD h, bblankb_{\mathrm{blank}}, and baccb_{\mathrm{acc}}.

For a dilation factor D≥2D \ge 2, a self-simulating machine hierarchy AA consists of a Boolean program PP with self-referential code aA=spec⁡(P,P)a_A = \operatorname{spec}(P, P) and a threshold h0≥4h_0 \ge 4 such that every integer h≥h0h \ge h_0 satisfies Fits⁡(β,g,D,h,|aA|)\operatorname{Fits}(\beta, g, D, h, |a_A|) (giving the hierarchy clause schedule ShS_h) and self-certification: for every task tt of arity ata_t and zero-task flag ZtZ_t and every data assignment data\mathrm{data} on data addresses of capacity 2h2^h, there exists a certificate assignment on {0,…,2h−1}\{0, \dots, 2^h - 1\} making all clauses of ShS_h for tt hold under the assembled assignment if and only if Entry⁡Dh,SDh,10000D2h(Zt,cfalse,c̃true)=true\operatorname{Entry}_{D h, S_{D h}, 10000 D^2 h}(Z_t, c_{\mathrm{false}}, \tilde{c}_{\mathrm{true}}) = \mathrm{true}, where csc_s is the (at+1)(a_t + 1)-tuple of length-10000Dh10000 D h candidate words extracted from data\mathrm{data} on side ss and c̃true\tilde{c}_{\mathrm{true}} is empty when Zt=trueZ_t = \mathrm{true} and ctruec_{\mathrm{true}} otherwise. For any length nn, the scalar conversion σn:{false,true}n→𝔽2n\sigma_n : \{\mathrm{false}, \mathrm{true}\}^n \to \mathbb{F}_2^n maps false\mathrm{false} to 00 and true\mathrm{true} to 11. For a word w=(w1,…,wk)w = (w_1, \dots, w_k) of raw bitstrings of height DhD h, the block embedding EhE_h is defined by (4): Eh(w)=(encode⁡h(c1),…,encode⁡h(cm)),(c1,…,cm)=Enc⁡2h(σ10000Dh(w1),…,σ10000Dh(wk)).E_h(w) = \bigl(\operatorname{encode}_h(c_1), \dots, \operatorname{encode}_h(c_m)\bigr), \qquad (c_1, \dots, c_m) = \operatorname{Enc}_{2^h}\!\bigl(\sigma_{10000 D h}(w_1), \dots, \sigma_{10000 D h}(w_k)\bigr).(4)✦

The Claim

Theorem 1. Let AA be a self-simulating machine hierarchy with dilation factor D≥2D \ge 2 and threshold h0h_0, let h≥h0h \ge h_0 be an integer, and let ShS_h and SDhS_{D h} denote its hierarchy clause schedules at heights hh and DhD h. For any verification task tt of arity aa and zero-task flag ZZ and any (a+1)(a + 1)-letter words ufalse,utrueu_{\mathrm{false}}, u_{\mathrm{true}} of raw bitstrings of height DhD h, if Entry⁡Dh,SDh,10000D2h(Z,ufalse,w′)=true\operatorname{Entry}_{D h, S_{D h}, 10000 D^2 h}(Z, u_{\mathrm{false}}, w') = \mathrm{true}, where w′w' is the empty word when Z=trueZ = \mathrm{true} and utrueu_{\mathrm{true}} when Z=falseZ = \mathrm{false}, then (5) holds: Z=false⟹Reach⁡h,Sh,10000Dhraw(Eh(ufalse),Eh(utrue)),Z=true⟹∃p,z,r,Reach⁡h,Sh,10000Dhraw(Eh(ufalse),pzr)∧Zero⁡h,Sh,10000Dhraw(z).\begin{aligned} Z = \mathrm{false} &\implies \operatorname{Reach}^{\mathrm{raw}}_{h, S_h, 10000 D h}\!\bigl(E_h(u_{\mathrm{false}}), E_h(u_{\mathrm{true}})\bigr), \\ Z = \mathrm{true} &\implies \exists\, p, z, r,\; \operatorname{Reach}^{\mathrm{raw}}_{h, S_h, 10000 D h}\!\bigl(E_h(u_{\mathrm{false}}), p z r\bigr) \land \operatorname{Zero}^{\mathrm{raw}}_{h, S_h, 10000 D h}(z). \end{aligned}(5)✦ For any words v,wv, w of raw bitstrings of height DhD h satisfying Repl⁡Dh,SDh,10000D2hraw(v,w)\operatorname{Repl}^{\mathrm{raw}}_{D h, S_{D h}, 10000 D^2 h}(v, w), (6) holds: Reach⁡h,Sh,10000Dhraw(Eh(v),Eh(w)).\operatorname{Reach}^{\mathrm{raw}}_{h, S_h, 10000 D h}\!\bigl(E_h(v), E_h(w)\bigr).(6)✦ For any word vv of raw bitstrings of height DhD h satisfying Zero⁡Dh,SDh,10000D2hraw(v)\operatorname{Zero}^{\mathrm{raw}}_{D h, S_{D h}, 10000 D^2 h}(v), (7) holds: ∃p,z,s,Reach⁡h,Sh,10000Dhraw(Eh(v),pzs)∧Zero⁡h,Sh,10000Dhraw(z).\exists\, p, z, s,\; \operatorname{Reach}^{\mathrm{raw}}_{h, S_h, 10000 D h}\!\bigl(E_h(v), p z s\bigr) \land \operatorname{Zero}^{\mathrm{raw}}_{h, S_h, 10000 D h}(z).(7)✦ For any word ww of raw bitstrings of height DhD h satisfying Survives⁡Dh,SDh,10000D2hraw(w)\operatorname{Survives}^{\mathrm{raw}}_{D h, S_{D h}, 10000 D^2 h}(w), (8) holds: Survives⁡h,Sh,10000Dhraw(Eh(w)).\operatorname{Survives}^{\mathrm{raw}}_{h, S_h, 10000 D h}\!\bigl(E_h(w)\bigr).(8)✦ Independently, let SS be any verification clause schedule of capacity qq and let d≤qd \le q. For any word uu of length nn over 𝔽2d\mathbb{F}_2^d and any cell words p,z,r′p, z, r' of capacity qq satisfying Reach⁡S,d(Enc⁡q(u),pzr′)\operatorname{Reach}_{S, d}(\operatorname{Enc}_q(u), p z r') and Zero⁡S,d(z)\operatorname{Zero}_{S, d}(z), (9) holds: ∃v,Reach⁡S,dchk(u,v)∧Zero⁡S,dchk(v).\exists\, v,\; \operatorname{Reach}^{\mathrm{chk}}_{S, d}(u, v) \land \operatorname{Zero}^{\mathrm{chk}}_{S, d}(v).(9)✦ For any finite word uu over 𝔽2d\mathbb{F}_2^d such that no word vv over 𝔽2d\mathbb{F}_2^d with Reach⁡S,dchk(u,v)\operatorname{Reach}^{\mathrm{chk}}_{S, d}(u, v) satisfies Zero⁡S,dchk(v)\operatorname{Zero}^{\mathrm{chk}}_{S, d}(v), (10) holds: Survives⁡S,d(Enc⁡q(u)).\operatorname{Survives}_{S, d}\!\bigl(\operatorname{Enc}_q(u)\bigr).(10)✦

In the paper, the result reads: the substitution EhE_h simulates every elementary next-parameter replacement and zero declaration; moreover, if ww is a nonzero word at parameter DhDh, no sequence of lower-parameter replacements starting from Eh(w)E_h(w) can reach a zero declaration. In the library’s statement, elementary replacements, zero declarations, and verification tasks at parameter DhDh are represented by the raw replacement, zero, and entry predicates at height DhDh with data size 10000D2h10000 D^2 h, lower-parameter replacement sequences by raw reachability at height hh with data size 10000Dh10000 D h, 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 AA with dilation factor D≥2D \ge 2 and threshold h0≥4h_0 \ge 4 at any integer height h≥h0h \ge h_0, 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 EhE_h, while the clean-word statements (9) and (10) are stated over an arbitrary verification clause schedule SS of capacity qq, data bound d≤qd \le q, finite-table cell rewriting, canonical word encoding, and checked regions. Beyond the main claim, the library proves for these constructions that for any integer h≥h0h \ge h_0, both hh and the data size 10000Dh10000 D h are positive and DhD h also meets h0h_0, and proves positivity of the tape coding bit width β\beta, the packet bit representation width, and the total tableau clause count of any tableau layout.