OctoInformBeta

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

Lemma 2.9: Surviving words reach idle markers, and tokens under capacity bounds rewrite to one to ten canonical blocks

Internal normalization of surviving tokens and cut intervals.

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

Consider words over finite-state cells of capacity qq, 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 k=10k = 10. 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 hh encoding cells of capacity 2h2^h and for tokens of a self-simulating machine hierarchy with multiplier DD, 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 4≤h4 \le h and 10000Dh≤2h10000 D h \le 2^h?

Local Syntax, Rewriting, and Survival

For a predicate PP on an alphabet α\alpha, a word ww over α\alpha is cut-free for PP if no letter of ww satisfies PP.✦ A word ww over α\alpha is a cut interval for PP if w=atw = a t for a letter aa satisfying PP and a cut-free word tt for PP.✦

A cell marker is one of five tags: idle, left wing, boundary, full, or right wing.✦ Given a natural number arity bound kk, a block metadata tuple (r,z,b)(r, z, b) consists of an arity r∈{0,…,k−1}r \in \{0, \dots, k - 1\}, a zero-task Boolean flag zz, and a block index b∈{0,…,r}b \in \{0, \dots, r\}.✦ For a capacity bound qq, a block cell position is a core position core(p)\mathrm{core}(p) with 0≤p<q0 \le p < q, a palette position pal(a)\mathrm{pal}(a) with 0≤a<q0 \le a < q, or the terminal position stop\mathrm{stop}.✦ A cell syntactic skeleton ss of position bound qq and arity bound kk consists of a position pos(s)\mathrm{pos}(s), a marker mk(s)\mathrm{mk}(s), and a block metadata tuple meta(s)\mathrm{meta}(s) of bound kk✦; updating the marker of ss to mm, written s[mk←m]s[\mathrm{mk} \leftarrow m], replaces mk(s)\mathrm{mk}(s) with mm while preserving position and metadata.✦

A cell syntactic skeleton ss is initial if its block index is 00 and pos(s)=core(0)\mathrm{pos}(s) = \mathrm{core}(0), and terminal if its block index equals its arity and pos(s)=stop\mathrm{pos}(s) = \mathrm{stop}. A skeleton ss carries an active head marker if mk(s)\mathrm{mk}(s) is boundary or full.✦ A skeleton ss is admissible if mk(s)\mathrm{mk}(s) is not right wing when ss is initial and not left wing when ss is terminal.✦

Two skeletons ss and s′s' of position bound qq and arity bound kk satisfy structural position adjacency if (pos(s),pos(s′))(\mathrm{pos}(s), \mathrm{pos}(s')) is (core(p),core(r))(\mathrm{core}(p), \mathrm{core}(r)) with r=p+1r = p + 1, (core(p),pal(a))(\mathrm{core}(p), \mathrm{pal}(a)) with p+1=qp + 1 = q, (pal(a),pal(a′))(\mathrm{pal}(a), \mathrm{pal}(a')), (pal(a),stop)(\mathrm{pal}(a), \mathrm{stop}), or (stop,core(0))(\mathrm{stop}, \mathrm{core}(0)).✦ Two skeletons ss and s′s' of position bound qq and arity bound kk satisfy internal consistency if they share the same arity and zero-task flag, their block indices satisfy b(s′)=b(s)+1b(s') = b(s) + 1 when pos(s)=stop\mathrm{pos}(s) = \mathrm{stop} and b(s′)=b(s)b(s') = b(s) otherwise, s′s' is not initial, and ss is not terminal.✦ A skeleton ss accepts a marker mm on the left if mm is full or right wing when mk(s)\mathrm{mk}(s) is right wing, and left wing otherwise✦; a skeleton ss accepts mm on the right if mm is left wing, boundary, or full when mk(s)\mathrm{mk}(s) is left wing, and right wing otherwise.✦ A skeleton ss is left-external if mk(s)\mathrm{mk}(s) is idle or both mk(s)\mathrm{mk}(s) is not right wing and ss is initial, and right-external if mk(s)\mathrm{mk}(s) is idle or boundary or both mk(s)\mathrm{mk}(s) is not left wing and ss is terminal.

A pair of skeletons (s,s′)(s, s') forms a compatible adjacent skeleton pair if they satisfy structural position adjacency and either ss is right-external and s′s' is left-external, or neither is external, ss accepts mk(s′)\mathrm{mk}(s') on the right, s′s' accepts mk(s)\mathrm{mk}(s) on the left, and (s,s′)(s, s') is internally consistent.✦ The skeleton link relation relates two optional skeletons by holding on two absent entries, relating an absent left entry to s′s' when s′s' is left-external, relating ss to an absent right entry when ss is right-external, and relating (s,s′)(s, s') when they form a compatible adjacent skeleton pair.✦ A word ww of skeletons is a closed skeleton sequence if every skeleton in ww is admissible and every adjacent pair in ww padded by an absent entry at each end stands in the skeleton link relation.✦

Over a color set CC, a palette checker state is idle, passed(x)\mathrm{passed}(x) for some x∈Cx \in C, or an active checker head head(x)\mathrm{head}(x) seeking x∈Cx \in C.✦ Two adjacent palette checker states form a compatible pair if they are (idle,idle)(\mathrm{idle}, \mathrm{idle}), (passed(x),passed(x))(\mathrm{passed}(x), \mathrm{passed}(x)), (passed(x),head(x))(\mathrm{passed}(x), \mathrm{head}(x)), or (head(x),idle)(\mathrm{head}(x), \mathrm{idle}) for some x∈Cx \in C.✦ A palette checker state satisfies the terminal palette checker condition if it is idle or head(x)\mathrm{head}(x) for some x∈Cx \in C, and fails if it is passed(x)\mathrm{passed}(x).✦

For a 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 0≤p<q0 \le p < q, or a certificate address (p)(p) with 0≤p<q0 \le p < q.✦ A three-bit register state is a vector in 𝔽23\mathbb{F}_2^3.✦ A verification task specification t=(r,z)t = (r, z) consists of an arity r∈{0,…,9}r \in \{0, \dots, 9\} and a zero-task Boolean flag zz.✦ A verification clause CC of bound qq consists of three cell memory addresses a0,a1,a2a_0, a_1, a_2 of bound qq and a Boolean truth function τC:𝔽23→{false,true}\tau_C : \mathbb{F}_2^3 \to \{\mathrm{false}, \mathrm{true}\}.✦ A verification clause schedule SS of bound qq assigns to each task tt a clause count 1≤κS(t)≤q1 \le \kappa_S(t) \le q and a family of qq verification clauses St(0),…,St(q−1)S_t(0), \dots, S_t(q - 1).✦

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 (s,j,ϕ,r)(s, j, \phi, r) of bound qq consists of a Boolean side ss, a clause index 0≤j<q0 \le j < q, a computation phase ϕ\phi, and a three-bit register r∈𝔽23r \in \mathbb{F}_2^3.✦ Cell arity metadata mm is a block metadata tuple with arity bound k=10k = 10, and its task projection task(m)\mathrm{task}(m) is the verification task specification retaining the arity and zero-task flag of mm. The default cell metadata is (0,false,0)(0, \mathrm{false}, 0)✦, and the default head state is (false,0,acquisition,0)(\mathrm{false}, 0, \mathrm{acquisition}, 0).✦ A finite table cell of capacity qq consists of a skeleton of position bound qq and arity bound 1010, a palette checker state over {0,…,q−1}\{0, \dots, q - 1\}, a data bit pair {false,true}→𝔽2\{\mathrm{false}, \mathrm{true}\} \to \mathbb{F}_2, a certificate bit in 𝔽2\mathbb{F}_2, and a reading head state of bound qq. A finite table cell cc 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 head(x)\mathrm{head}(x) for any color xx.

Reading a finite table cell cc at an address aa yields a bit in 𝔽2\mathbb{F}_2: it returns cc’s data bit on side ss when aa is a data address (s,b,p)(s, b, p), cc lies at core(r)\mathrm{core}(r) with r=pr = p, and the block index of cc equals bb; it returns cc’s certificate bit when aa is a certificate address (p)(p), cc lies at core(r)\mathrm{core}(r) with r=pr = p, and the block index of cc is 00; and it returns 00 otherwise.✦ Given a verification clause CC and a cell cc, the clause register delta Δ(C,c)∈𝔽23\Delta(C, c) \in \mathbb{F}_2^3 has ii-th entry equal to the bit read from cc at the ii-th address of CC for i∈{0,1,2}i \in \{0, 1, 2\}.✦

Given a verification clause schedule SS of capacity qq and a data size dd, a cell cc satisfies the cell formatting condition if its skeleton is admissible, its checker is idle whenever cc is not in the palette, its data bits vanish at any core position p≥dp \ge d, and both its data bits and certificate bit vanish whenever cc is not in the core. The cell formatting condition for SS and dd also requires that an idle marker on cc forces default metadata, default head state, true-side data bit 00, and certificate bit 00; a left or right wing marker forces the default head state; a boundary marker forces head clause index 00, phase acquisition, and register 00; an active head marker with zero-task flag true forces head side false; and a full marker requires head clause index 00 in the success phase, head clause index strictly less than κS(task(c))\kappa_S(\mathrm{task}(c)) in every other phase, and a terminal skeleton whenever the head phase is an endpoint phase.

Two finite table cells aa and bb of capacity qq satisfy checker compatibility if their checkers form a compatible palette checker pair whenever both are in the palette, and aa’s checker satisfies the terminal palette checker condition whenever aa is in the palette and pos(b)=stop\mathrm{pos}(b) = \mathrm{stop}.✦ Cells aa and bb form a compatible adjacent cell pair if their skeletons form a compatible adjacent skeleton pair and (a,b)(a, b) satisfies checker compatibility.✦ Given a verification clause schedule SS of capacity qq and a data size dd, a word ww of cells of capacity qq satisfies cell word syntax for SS and dd if the skeletons of ww form a closed skeleton sequence, every adjacent pair in ww satisfies checker compatibility, and every cell in ww satisfies the cell formatting condition for SS and dd.✦

Given a cell cc and side ss, let cbd(s)c_{\mathrm{bd}}(s) update the skeleton marker of cc to boundary and set its head to the default head with side ss; let cfull(s,j,ϕ,r)c_{\mathrm{full}}(s, j, \phi, r) update the skeleton marker to full and set the head to (s,j,ϕ,r)(s, j, \phi, r); let cwing(m)c_{\mathrm{wing}}(m) update the skeleton marker to mm and set the head to the default head; let cidle(s)c_{\mathrm{idle}}(s) keep pos(c)\mathrm{pos}(c), reset marker to idle, metadata to default metadata, certificate to 00, and head to the default head, and set data to 00 on side true and cc’s data at ss on side false; let c[chk←χ]c[\mathrm{chk} \leftarrow \chi] replace the checker with χ\chi; and let c[col←a]c[\mathrm{col} \leftarrow a] set the skeleton position to pal(a)\mathrm{pal}(a). Under a schedule SS, a unary cell transition relates a single cell to another across twelve rules: creating cbd(s)c_{\mathrm{bd}}(s) from cidle(s)c_{\mathrm{idle}}(s) when cc is initial; finishing acquisition from cbd(s)c_{\mathrm{bd}}(s) to cfull(s,0,acquisition,0)c_{\mathrm{full}}(s, 0, \mathrm{acquisition}, 0) when cc 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 (s,j,r)(s, j, r) when cc is terminal; turning from read-left to read-right and from undo-left to undo-right while preserving (s,j,r)(s, j, r) when cc is initial; passing the gate from before-gate to after-gate when cc is terminal and τStask(c)(j)(r)=true\tau_{S_{\mathrm{task}(c)}(j)}(r) = \mathrm{true}; advancing from cfull(s,j,finish,0)c_{\mathrm{full}}(s, j, \mathrm{finish}, 0) to cfull(s,j′,acquisition,0)c_{\mathrm{full}}(s, j', \mathrm{acquisition}, 0) with j′=j+1<qj' = j + 1 < q when cc is terminal; entering success at cfull(s,0,success,0)c_{\mathrm{full}}(s, 0, \mathrm{success}, 0) from cfull(s,j,finish,0)c_{\mathrm{full}}(s, j, \mathrm{finish}, 0) when cc is terminal and j+1=κS(task(c))j + 1 = \kappa_S(\mathrm{task}(c)); and pivoting cfull(s,0,success,0)c_{\mathrm{full}}(s, 0, \mathrm{success}, 0) to cfull(¬s,0,success,0)c_{\mathrm{full}}(\neg s, 0, \mathrm{success}, 0) when cc is terminal and the zero-task flag of cc is false.✦

Under a schedule SS, a binary cell transition relates an adjacent pair of cells to another across eight rules: acquiring (awing(left),bbd(s))(a_{\mathrm{wing}}(\mathrm{left}), b_{\mathrm{bd}}(s)) from (abd(s),bidle(s))(a_{\mathrm{bd}}(s), b_{\mathrm{idle}}(s)) when the skeletons of aa and bb updated with markers left wing and boundary form a compatible skeleton pair; stepping left in read-left from (awing(left),bfull(s,j,read-left,r))(a_{\mathrm{wing}}(\mathrm{left}), b_{\mathrm{full}}(s, j, \text{read-left}, r)) to (afull(s,j,read-left,r+Δ(Stask(a)(j),a)),bwing(right))(a_{\mathrm{full}}(s, j, \text{read-left}, r + \Delta(S_{\mathrm{task}(a)}(j), a)), b_{\mathrm{wing}}(\mathrm{right})), stepping right in read-right from (afull(s,j,read-right,r),bwing(right))(a_{\mathrm{full}}(s, j, \text{read-right}, r), b_{\mathrm{wing}}(\mathrm{right})) to (awing(left),bfull(s,j,read-right,r))(a_{\mathrm{wing}}(\mathrm{left}), b_{\mathrm{full}}(s, j, \text{read-right}, r)), stepping left in undo-left from (awing(left),bfull(s,j,undo-left,r))(a_{\mathrm{wing}}(\mathrm{left}), b_{\mathrm{full}}(s, j, \text{undo-left}, r)) to (afull(s,j,undo-left,r),bwing(right))(a_{\mathrm{full}}(s, j, \text{undo-left}, r), b_{\mathrm{wing}}(\mathrm{right})), and stepping right in undo-right from (afull(s,j,undo-right,r),bwing(right))(a_{\mathrm{full}}(s, j, \text{undo-right}, r), b_{\mathrm{wing}}(\mathrm{right})) to (awing(left),bfull(s,j,undo-right,r+Δ(Stask(a)(j),a)))(a_{\mathrm{wing}}(\mathrm{left}), b_{\mathrm{full}}(s, j, \text{undo-right}, r + \Delta(S_{\mathrm{task}(a)}(j), a))), each when the skeletons of aa and bb updated with markers full and right wing form a compatible skeleton pair; creating a checker head from (a,b[chk←idle])(a, b[\mathrm{chk} \leftarrow \mathrm{idle}]) to (a,b[chk←head(x)])(a, b[\mathrm{chk} \leftarrow \mathrm{head}(x)]) when pos(a)=core(p)\mathrm{pos}(a) = \mathrm{core}(p) with p+1=qp + 1 = q and bb is in the palette; advancing a checker head from (a[chk←head(x)],b[chk←idle])(a[\mathrm{chk} \leftarrow \mathrm{head}(x)], b[\mathrm{chk} \leftarrow \mathrm{idle}]) to (a[chk←passed(x)],b[chk←head(x)])(a[\mathrm{chk} \leftarrow \mathrm{passed}(x)], b[\mathrm{chk} \leftarrow \mathrm{head}(x)]) when pos(a)=pal(v)\mathrm{pos}(a) = \mathrm{pal}(v) with v≠xv \neq x and bb is in the palette; and swapping (a,b)(a, b) to (b,a)(b, a) when pos(a)=pal(x)\mathrm{pos}(a) = \mathrm{pal}(x), pos(b)=pal(y)\mathrm{pos}(b) = \mathrm{pal}(y), a[col←y]=ba[\mathrm{col} \leftarrow y] = b, and both aa and bb are head-free.

For a schedule SS and data size dd, two words vv and ww of cells satisfy the cell list replacement relation if every cell in vv or ww satisfies the cell formatting condition for SS and dd, and either v=[a]v = [a] and w=[b]w = [b] are related in either direction by a unary cell transition, or v=[a,b]v = [a, b] and w=[a′,b′]w = [a', b'] are related in either direction by a binary cell transition.✦ A cell word vv rewrites in one step to ww, written v→S,dwv \to_{S, d} w, if v=pxsv = p x s and w=pysw = p y s for words p,s,x,yp, s, x, y such that (x,y)(x, y) satisfies the cell list replacement relation for SS and dd✦; cell word reachability v→S,d*wv \to_{S, d}^* w is the reflexive and transitive closure of →S,d\to_{S, d}.✦

Under a schedule SS, a cell cc 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 τStask(c)(j)(r)=false\tau_{S_{\mathrm{task}(c)}(j)}(r) = \mathrm{false} for head clause jj and register rr, or its head phase is success while its zero-task flag is true.✦ For SS and data size dd, a cell cc satisfies the unary zero cell condition if it fails the cell formatting condition for SS and dd, satisfies the semantic zero cell condition for SS, or lies at a palette position pal(x)\mathrm{pal}(x) with checker passed(x)\mathrm{passed}(x).✦ Two cells aa and bb satisfy the binary zero cell condition if they do not form a compatible adjacent cell pair, if both lie at the same palette position pal(x)\mathrm{pal}(x), or if aa lies at pal(x)\mathrm{pal}(x) with checker head(y)\mathrm{head}(y) for x≠yx \neq y while pos(b)=stop\mathrm{pos}(b) = \mathrm{stop}.✦ A word vv satisfies the zero cell word predicate for SS and dd if vv is a one-cell word satisfying the unary zero condition or a two-cell word satisfying the binary zero condition✦; a word ww survives under SS and dd if no word uu with w→S,d*uw \to_{S, d}^* u contains a contiguous factor satisfying the zero cell word predicate.✦

A finite table cell cc is a cut cell if pos(c)=core(0)\mathrm{pos}(c) = \mathrm{core}(0) and either its marker is idle or its block index is 00.✦ Given a verification clause schedule SS and a data size dd, a word tt of cells is a cell token for SS and dd if tt is a cut interval for the cut cell predicate and there exists a cut cell bb such that tbt b survives under SS and dd.✦ Given a vector u∈𝔽2du \in \mathbb{F}_2^d and a position pp of capacity qq, the canonical cell at pp for uu has position pp, idle marker, default metadata, idle checker, default head, certificate 00, data 00 on side true, and data uru_r on side false if p=core(r)p = \mathrm{core}(r) with r<dr < d and 00 otherwise.✦ The canonical block Block⁡q(u)\operatorname{Block}_q(u) concatenates the canonical cells for uu across core(0),…,core(q−1)\mathrm{core}(0), \dots, \mathrm{core}(q - 1), pal(0),…,pal(q−1)\mathrm{pal}(0), \dots, \mathrm{pal}(q - 1), and stop\mathrm{stop}✦; for a word u=(u1,…,um)u = (u_1, \dots, u_m) in (𝔽2d)*(\mathbb{F}_2^d)^*, the encoded word Enc⁡q(u)\operatorname{Enc}_q(u) is the concatenation Block⁡q(u1)⋯Block⁡q(um)\operatorname{Block}_q(u_1) \cdots \operatorname{Block}_q(u_m).✦

The Raw Codec and Machine Hierarchy

For a height hh, set qh=2hq_h = 2^h and Lh=2qh+1L_h = 2 q_h + 1; a raw bitstring of height hh is a Boolean vector of length 10000h10000 h.✦ Cell encoding maps each cell cc of capacity qhq_h to a raw bitstring ench(c)\mathrm{enc}_h(c) of length 10000h10000 h 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 2h2h-bit little-endian binary slots in the first 64h64 h 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 64h64 h, setting unused bits to false. For h>0h > 0, cell decoding extracts a candidate cell cc from those integer and flag slots whenever each decoded tag and index lies in bounds and returns cc if ench(c)\mathrm{enc}_h(c) 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 h>0h > 0, a schedule SS of capacity qhq_h, and data size dd, two words of raw bitstrings satisfy raw word replacement if they decode to cell words satisfying the cell list replacement relation for SS and dd, 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 ⇒h,S,d*\Rightarrow_{h, S, d}^*. A raw word tt is a raw token for hh, SS, and dd if tt is obtained by applying ench\mathrm{enc}_h letterwise to a cell token for SS and dd.✦ A raw bitstring aa satisfies raw unary zero if decoding aa fails or yields a cell satisfying the unary zero condition for SS and dd✦; two raw bitstrings aa and bb 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 h>0h > 0, a schedule SS of capacity qhq_h, data size dd, a Boolean selector zz, and raw words vv and ww, the codec table entry returns true if and only if either z=truez = \mathrm{true}, ww is empty, and vv satisfies the zero raw word predicate, or z=falsez = \mathrm{false} and (v,w)(v, w) satisfies raw word replacement.✦

Given a multiplier DD and a height hh, converting false↦0\mathrm{false} \mapsto 0 and true↦1\mathrm{true} \mapsto 1 in 𝔽2\mathbb{F}_2 maps each raw bitstring vv of height DhD h to a scalar vector σ(v)∈𝔽210000Dh\sigma(v) \in \mathbb{F}_2^{10000 D h}. For a word u=(u1,…,um)u = (u_1, \dots, u_m) of raw bitstrings of height DhD h, the raw word embedding Emb⁡h,D(u)\operatorname{Emb}_{h, D}(u) applies ench\mathrm{enc}_h to each cell of Enc⁡qh(σ(u1),…,σ(um))\operatorname{Enc}_{q_h}(\sigma(u_1), \dots, \sigma(u_m)).✦

For a tape alphabet Γ\Gamma and state set QQ, a Turing machine command specifies a written symbol in Γ\Gamma, a next state in QQ, and a head motion (left, stay, or right), and a tape cell label records a symbol in Γ\Gamma, an origin Boolean flag, and an optional active head in QQ. A transition table δ:Q×Γ→Γ×Q×{left,stay,right}\delta : Q \times \Gamma \to \Gamma \times Q \times \{\text{left}, \text{stay}, \text{right}\} 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 KK of bit width β>0\beta > 0 consists of encoding and decoding maps between labels and Boolean vectors of length β\beta satisfying left invertibility✦; for finite Γ\Gamma and QQ with a blank symbol, the one-hot coding takes β\beta to be the number of labels and encodes each label by its indicator vector, and any coding KK turns the local three-cell update into a Boolean map on 3β3\beta bits. A circuit wire on nn indices is a constant Boolean or an index below nn✦, and a combinational not-AND (NAND) circuit with II inputs and gg gates appends gg two-input NAND gates drawing from the II inputs and earlier gates, evaluating all I+gI + g wires recursively and generating the list of three-wire circuit clauses constraining its gates over all I+gI + g wires. A circuit realization of δ\delta under KK supplies a gate count gg, a NAND circuit on 3β3\beta inputs, and β\beta output wires computing the 3β3\beta-bit encoded local transition; such a realization exists for any finite coding and transition table.

Given a stack index type KK, token alphabet Γ\Gamma, and state set QQ, 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 KK interprets programs of push, pop, halt, bit, tick, separator, and stop tokens across simulated registers in KK, 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 nn, let binSize⁡(n)\operatorname{binSize}(n) be 11 if n=0n = 0 and the binary bit-length of nn otherwise, and let the prefix encoding enc⁡(n)\operatorname{enc}(n) concatenate binSize⁡(n)\operatorname{binSize}(n) true bits, false, and the binary digits of nn from most to least significant; the specialization of two Boolean lists tt and vv prepends true to enc⁡(|t|)tenc⁡(|v|)v\operatorname{enc}(|t|) t \operatorname{enc}(|v|) v✦, 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 δ\delta, its one-hot coding of positive bit width β\beta, its circuit realization of gate count gg, and the β\beta-bit encodings of the blank, bit, initial, and accepting halting-head tape labels.

At bound qq, 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 (s,b,p)(s, b, p) 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 00 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 qq, a Boolean program aa, a word-length parameter HH with 0<10000H≤q0 < 10000 H \le q, an arity 1≤l≤101 \le l \le 10, and a Boolean flag ZZ, the source machine input sequence concatenates the fixed bits enc⁡(|a|)aenc⁡(H)enc⁡(l)\operatorname{enc}(|a|) a \operatorname{enc}(H) \operatorname{enc}(l) and [Z][Z] with unnegated data-address references for ll blocks of length 10000H10000 H on one side when Z=trueZ = \mathrm{true} and both sides when Z=falseZ = \mathrm{false}. With bit vectors 𝑏𝑙𝑎𝑛𝑘,𝑜𝑟𝑖𝑔𝑖𝑛∈{false,true}β\mathit{blank}, \mathit{origin} \in \{\mathrm{false}, \mathrm{true}\}^\beta, a bit-encoding map 𝑠𝑦𝑚𝑏𝑜𝑙:{false,true}→{false,true}β\mathit{symbol} : \{\mathrm{false}, \mathrm{true}\} \to \{\mathrm{false}, \mathrm{true}\}^\beta, and an origin column oo, the initial row configuration places fixed 𝑜𝑟𝑖𝑔𝑖𝑛(r)\mathit{origin}(r) at column oo for each bit r<βr < \beta, transforms the (j−o−1)(j - o - 1)-th entry of the input sequence at column j>oj > o via the map b↦𝑠𝑦𝑚𝑏𝑜𝑙(b,r)b \mapsto \mathit{symbol}(b, r) (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 𝑏𝑙𝑎𝑛𝑘(r)\mathit{blank}(r) elsewhere.

Given positive bit width β\beta, positive time TT, tape width W≥3W \ge 3, gate count gg, and an origin column below WW, a tableau layout requires the certificate variable count Ccert(β,g,T,W)=βWT+g(W−2)(T−1)C_{\mathrm{cert}}(\beta, g, T, W) = \beta W T + g(W - 2)(T - 1) and the total tableau clause count Ccl(β,g,T,W)=2βW+2β(T−1)+(3g+2β)(W−2)(T−1)+βC_{\mathrm{cl}}(\beta, g, T, W) = 2\beta W + 2\beta(T - 1) + (3g + 2\beta)(W - 2)(T - 1) + \beta to be at most qq. Mapping tape cell variables across (T,W,β)(T, W, \beta) and gate variables across (T−1,W−2,g)(T - 1, W - 2, g) into certificate addresses below qq, and pairing them with a combinational NAND circuit on 3β3\beta inputs with gg gates, β\beta 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 l=arity(task)+1l = \mathrm{arity}(\mathrm{task}) + 1 and zero-task flag Z=zZ = z 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 β\beta, gate count gg, multiplier DD, height hh, and program length nn, set T=2⌊h/5⌋T = 2^{\lfloor h/5 \rfloor} and W=4TW = 4T; the layout parameter bounds predicate holds if 64h+512≤10000h,10≤22h,2h≤22h,10000Dh≤2h,Ccert(β,g,T,W)≤2h,Ccl(β,g,T,W)≤2h,n+2binSize⁡(n)+2binSize⁡(Dh)+12+20(10000Dh)<⌊T/4⌋.\begin{aligned} 64 h + 512 &\le 10000 h, & 10 &\le 2^{2h}, & 2^h &\le 2^{2h}, \\ 10000 D h &\le 2^h, & C_{\mathrm{cert}}(\beta, g, T, W) &\le 2^h, & C_{\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}(1)✦ When (1) holds for a Boolean program aa of length nn, the source machine layout of capacity qhq_h, time TT, width WW, and origin 2T2T yields the source machine initial inputs and clause schedule of capacity qhq_h on data of size 10000Dh10000 D h.

Given a multiplier D≥2D \ge 2, a self-simulating machine hierarchy AA consists of a Boolean program PP and a natural number threshold h0≥4h_0 \ge 4 such that for every height h≥h0h \ge h_0, the self-referential machine code aa obtained by specializing PP to itself satisfies (1), and for every verification task (r,z)(r, z) and data assignment on capacity qhq_h, there exists a certificate vector on {0,…,qh−1}\{0, \dots, q_h - 1\} satisfying all tableau clauses of the source machine layout for aa and (r,z)(r, z) at height hh under the assembled assignment if and only if the codec table entry at height DhD h for the source machine schedule of aa at height DhD h, data size 10000D2h10000 D^2 h, and selector zz evaluates to true on the tuple of r+1r + 1 candidate words of height DhD h from the false side together with either the empty list when z=truez = \mathrm{true} or the r+1r + 1 candidate words from the true side when z=falsez = \mathrm{false}.✦ At each height h≥h0h \ge h_0, AA determines the hierarchy clause schedule Sh(A)S_h(A) of capacity qhq_h given by the source machine schedule for aa✦, and a hierarchy token of AA at height hh is a raw token for hh, Sh(A)S_h(A), and data size 10000Dh10000 D h.✦

The Claim

Theorem 1. Let qq and dd be natural numbers with d≤qd \le q, and let SS be a verification clause schedule of capacity qq. If aa and bb are cut cells of capacity qq, ww is a cut-free word of cells of capacity qq, and awba w b survives under SS and dd, then there exists a word uu of vectors in 𝔽2d\mathbb{F}_2^d such that 1≤|u|≤10,|aw|=(2q+1)|u|,aw→S,d*Enc⁡q(u).1 \le |u| \le 10, \qquad |a w| = (2q + 1)|u|, \qquad a w \to_{S, d}^* \operatorname{Enc}_q(u).(2)✦

Let qq and dd be natural numbers with d≤qd \le q, and let SS be a verification clause schedule of capacity qq. If aa and bb are cut cells of capacity qq and ww is a word of cells of capacity qq such that awba w b survives under SS and dd, then there exists a word uu of vectors in 𝔽2d\mathbb{F}_2^d such that aw→S,d*Enc⁡q(u).a w \to_{S, d}^* \operatorname{Enc}_q(u).(3)✦

Let qq and dd be natural numbers, and let SS be a verification clause schedule of capacity qq. If ww is a word of cells of capacity qq that satisfies cell word syntax and survives under SS and dd, then there exists a word vv of cells such that w→S,d*vand every cell of v has the idle marker.w \to_{S, d}^* v \quad \text{and every cell of $v$ has the idle marker}.(4)✦

Let h≥4h \ge 4 and DD be natural numbers satisfying 10000Dh≤qh10000 D h \le q_h, and let SS be a verification clause schedule of capacity qhq_h. If tt is a raw token for hh, SS, and data size 10000Dh10000 D h, then there exists a word uu of raw bitstrings of height DhD h such that 1≤|u|≤10,|t|=Lh|u|,t⇒h,S,10000Dh*Emb⁡h,D(u).1 \le |u| \le 10, \qquad |t| = L_h |u|, \qquad t \Rightarrow_{h, S, 10000 D h}^* \operatorname{Emb}_{h, D}(u).(5)✦

Given a self-simulating machine hierarchy AA with multiplier D≥2D \ge 2 and threshold h0≥4h_0 \ge 4, let h≥h0h \ge h_0, and let tt be a hierarchy token of AA at height hh. Defining the token normal form νA(t)\nu_A(t) to be a word of raw bitstrings of height DhD h selected from (5) for Sh(A)S_h(A), this word νA(t)\nu_A(t) satisfies 1≤|νA(t)|≤10,|t|=Lh|νA(t)|,t⇒h,Sh(A),10000Dh*Emb⁡h,D(νA(t)).1 \le |\nu_A(t)| \le 10, \qquad |t| = L_h |\nu_A(t)|, \qquad t \Rightarrow_{h, S_h(A), 10000 D h}^* \operatorname{Emb}_{h, D}(\nu_A(t)).(6)✦

In the paper, the result reads: an interval between consecutive cuts in a nonzero word consists of between one and kk complete structural blocks and can be changed, using only replacements inside that interval, to a concatenation of canonical blocks. The library sets k=10k = 10, renders nonzeroness as survival, cut intervals as tokens or words bounded by cut cells, complete structural blocks as length-(2q+1)(2q + 1) or length-LhL_h factors, and internal replacements as reachability, casting the statement in (2) through (6) across cell words, raw bitstrings with 4≤h4 \le h and 10000Dh≤2h10000 D h \le 2^h, and machine hierarchy tokens.

What Is Checked

The normalization statements (2), (3), and (4) are stated over finite table cells of capacity qq, verification clause schedules SS of capacity qq, data sizes dd (with d≤qd \le q 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 h≥4h \ge 4, raw tokens for a schedule SS of capacity qh=2hq_h = 2^h and data size 10000Dh≤qh10000 D h \le q_h, raw word reachability, and raw word embeddings; and (6) is stated over a self-simulating machine hierarchy AA with multiplier D≥2D \ge 2 and threshold h0≥4h_0 \ge 4, hierarchy heights h≥h0h \ge h_0, hierarchy clause schedules Sh(A)S_h(A), hierarchy tokens, and token normal forms. The positivity claims also hold for the bit width β\beta of the source machine tape coding, the packet bit representation width, the total clause count of any tableau layout, and, for any height h≥h0h \ge h_0 in a self-simulating machine hierarchy with multiplier DD, both hh and the data size 10000Dh10000 D h.