OctoInformBeta

OpenAI preprint, September 2026 · §3. Block visits and epoch transcripts · §3.3

Theorem 1, proof (§3.3): assembly: For runnable tours with E⋅perE\cdot\mathrm{per} linear in S+1S+1; when T≤k5T \le k^5 some offset completes, and its readout is the outcome at time TT

Computing the final controller and reading off the outcome.

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

How much work space does a deterministic machine need to reproduce TT steps of a machine with one work tape and read-only input heads? The simulation of this item cuts the work tape positions [−T,T][-T, T], as the addresses 00 to 2T2T, into blocks of k2k^2 cells, for a positive integer parameter kk, and follows the run as a sequence of block visits, in each of which a controller word enters one block, runs there and leaves. The visits are grouped into epochs, and a circuit over the epochs is evaluated recursively. The item assembles the simulation from tours of block visits with their epoch circuit, the machine tried at every shift of the blocks, and a space allowance with its bound in terms of TT.

Uniform Computation in Space

Space is counted in work bits, uniformly over an index set. A stack machine has finitely many states, a read-only head on the public input, which reads each symbol framed by a left and a right endmarker, and finitely many stacks of bits; in each step, from its state, the symbol under its head and the top bit of each stack, it either halts with a label or moves its head, keeps, pushes a bit onto or pops each stack, and changes state, and its work space is the greatest length a stack reaches.✦ For families xix_i of words over an alphabet XX and SiS_i, aia_i, fif_i of natural numbers, indexed by ii in a set II, the family ff is computable from aa in space SS on xx, written a→Sfa \xrightarrow{S} f, when one fixed stack machine, at every index ii, reads xix_i as its public input and turns aia_i, written in binary on a stack, into fif_i within C(Si+1)C(S_i + 1) work bits, for a constant CC independent of ii.✦ A family vv of values in a finite set FF is computable from aa in space SS on xx when the family of the positions of the viv_i in a fixed enumeration of FF is.✦

For a map φ\varphi from an index set UU to II, computation reindexed by φ\varphi is computation over UU in which the index uu has public input xφ(u)x_{\varphi(u)} and space bound Sφ(u)S_{\varphi(u)}.✦ A quantity vi(z)v_i(z), depending on the index ii and on arguments zz, is computable along every reindexing when, for every such φ\varphi and every family yy on UU, the values vφ(u)(zu)v_{\varphi(u)}(z_u) are computable from yy reindexed by φ\varphi whenever aφ(u)a_{\varphi(u)} and the arguments zuz_u are.

A family ff of natural numbers indexed by II is linear in S+1S + 1 when the first inequality below holds for a constant CC and every index ii✦, and fits in space SS when the second does, |fi||f_i| being the bit length of fif_i: fi≤C(Si+1),|fi|≤C(Si+1).f_i \le C\,(S_i + 1), \qquad |f_i| \le C\,(S_i + 1).(1)✦

Tours and Their Epoch Circuit

A reference tour DD consists of a positive integer kk, a controller width cc, a positive number NN of blocks, an initial controller q0q_0, an initial word Bj0B^0_j for each block jj, a selection σ\sigma that names for each controller qq the block σ(q)<N\sigma(q) < N it reads and rewrites, and a visit map δ\delta that sends a controller and the word of its block to the next controller and the block’s new word.✦ The story of a reference tour DD is the sequence of scenes (qt,Bt)(q_t, B^t), each a controller and a word for every block, that starts at (q0,B0)(q_0, B^0) and makes one visit per step.✦ With b=k2b = k^2, m=2cm = 2^c and E=k+1E = k + 1 epochs, the final controller of DD is qEbq_{Eb}, the controller after all EbEb visits. Controllers and words are natural numbers, and words and controller histories are read as digit strings in base mm, least significant digit first. The tour has finite word bounds when q0<mq_0 < m, every Bj0<mbB^0_j < m^b, and a visit by a controller below mm to a word below mbm^b yields a controller below mm and a word below mbm^b.✦ Replaying block ii of a reference tour DD under a transcript ZZ, a controller history, from a word aa gives a sequence of pairs of a word and a verdict: the first pair is (amod⁡mb,true)(a \bmod m^b, \text{true}), and the pair after n+1n+1 steps comes from the pair after nn steps by one replay step at digit nn of ZZ.✦

An evaluation circuit of width ww with ℓ\ell children per node is a set of nn nodes, each vv with a base mark, a head child h(v)h(v), children ch(v,i)\mathrm{ch}(v,i), a number g(v)g(v) of guessed bits, a first value f(v)f(v) used at base nodes and a value val(v)\mathrm{val}(v), together with two local rules: a proposal π(v,z,y,x)\pi(v,z,y,x), a number for each node, coordinate zz, guess yy and head value xx, and an admissibility test α(v,z,y,i,x,a)\alpha(v,z,y,i,x,a), a number for each node, coordinate, guess, child index ii, head value and child value aa.✦ The modulus PP of an evaluation circuit of width ww with ℓ\ell children per node is the largest prime with Δ+1<P≤2Δ+2\Delta + 1 < P \le 2\Delta + 2, where Δ=(ℓ+1)w\Delta = (\ell + 1)w is its outer degree, and its register count is Pw+1P^{w+1}, the number of register contents.✦ A call on an evaluation circuit that guesses gg bits has the frame price π(g)=100(|n|+|w|+|ℓ|+|P|+g+2)\pi(g) = 100\,(|n| + |w| + |\ell| + |P| + g + 2), with nn, ww, ℓ\ell and PP the node count, width, children per node and modulus of the circuit.✦

The augmented bit at coordinate zz of a word uu of width ww is the binary digit of uu at place zz when z<wz < w, the bit 11 when z=wz = w, and 00 when z>wz > w.✦

The epoch circuit 𝒞D\mathcal{C}_D of DD is the evaluation circuit of width w=c(b+1)w = c(b + 1) with NN children per node on the n=E(N+k+1)n = E(N + k + 1) vertices ve,jv_{e,j} of epoch e<Ee < E and column j<N+k+1j < N + k + 1: NN block columns, a start column and kk history columns.✦ Its base nodes are the vertices of epoch 00 with j≤Nj \le N✦, and its first value is Bj0B^0_j for j<Nj < N and q0q_0 otherwise.✦ The head child of ve,jv_{e,j} is ve−1,N+kv_{e-1,N+k} for j≤Nj \le N and ve,j−1v_{e,j-1} for j>Nj > N✦; its child of index ii is ve−1,jv_{e-1,j} for j<Nj < N, its head child for j=Nj = N, and ve,iv_{e,i} for j>Nj > N.✦ A vertex guesses no bits for j≤Nj \le N and ckck bits for j>Nj > N.✦ At a history vertex the round is r=j−Nr = j - N.✦ The proposal is 11 at a block vertex; at the start vertex it is the augmented bit zz of the digit of xx at place bb in base mm; at a history vertex it is the augmented bit zz of xmod⁡mn′+mn′yx \bmod m^{n'} + m^{n'} y with n′=(r−1)k+1n' = (r-1)k + 1.✦ The admissibility test is 11 at the start vertex and, at a block vertex, for every child index other than 00; for child 00 of the block vertex of block jj it is the augmented bit zz of the word reached by replaying block jj under xx from aa for bb steps; at a history vertex it is the verdict of replaying block ii under the proposed history from aa for rkrk steps.✦ The value of 𝒞D\mathcal{C}_D at ve,jv_{e,j} is read from the story after ebeb visits, as the word of block jj or as the history of the controllers from there on: val(ve,j)=Bjeb(j<N),val(ve,j)=∑i=0(j−N)kqeb+imi(j≥N).\mathrm{val}(v_{e,j}) = B^{eb}_j \quad (j < N), \qquad \mathrm{val}(v_{e,j}) = \sum_{i=0}^{(j-N)k} q_{eb+i}\, m^{i} \quad (j \ge N).(2)✦ The target of 𝒞D\mathcal{C}_D is v*=vE−1,N+kv^{*} = v_{E-1,\,N+k}, the last history vertex of the last epoch✦, and the coins per epoch of DD, written per\mathrm{per}, are, with the frame prices of 𝒞D\mathcal{C}_D, per=π(ck)+(k+2)π(0).\mathrm{per} = \pi(ck) + (k + 2)\,\pi(0).(3)✦

A family of evaluation circuits 𝒞i\mathcal{C}_i is ready on xx in space SS from aa when its widths wiw_i and child counts ℓi\ell_i are computable from aa in space SS, when its node counts nin_i and register counts Piwi+1P_i^{w_i+1} fit in space SS, and when its local structure is computable along every reindexing from a node and arguments in range: the base mark, number of guessed bits, head child, first value and children of the node, and the proposal and admissibility test at it.✦ A family of reference tours DiD_i is runnable on xx in space SS from aa when kk, cc, NN and q0q_0 are computable from aa in space SS, when the register counts Piwi+1P_i^{w_i+1} of their epoch circuits fit in space SS, and when the initial word of a block, the block σ(z)\sigma(z) selected by a controller z<mz < m and the visit δ(z,B)\delta(z, B) of a controller z<mz < m to a word B<mbB < m^b are computable along every reindexing from the block, the controller and the word.✦

The Machine and Its Trial Sites

A multihead machine with sensor MM over an input alphabet XX has a finite set QQ of states with a start state and a halting flag on each state, a finite tape alphabet AA, one work tape, rr read-only heads, and a program that maps the state, the symbol under the work head and the symbols under the read-only heads to a new state, a write and move on the work tape and a move of each read-only head.✦ The sensor of MM presents an input word xx by giving the initial content of the work tape and, at each integer position, the symbol each read-only head reads. The configuration of MM on xx at time tt is the state, work tape content and head positions reached from the start state, with every head at 00, after tt moves of the program, a machine in a halting state staying where it is.✦ The outcome ωM(x,t)\omega_M(x, t) is the state at time tt with its halting flag, and MM has halted at time tt when the flag is set.✦

An offset trial site W=(T,k,θ)W = (T, k, \theta) is a cap TT, a positive parameter kk and an offset θ<k2\theta < k^2.✦ With b=k2b = k^2, it cuts the addresses 00 to 2T2T, shifted by θ\theta, into N=2T+b+2N = 2T + b + 2 blocks of bb cells, the address ss lying in the home block ⌊(θ+s)/b⌋\lfloor (\theta + s)/b \rfloor. A controller of MM at cap TT is a word of c(T)c(T) bits, made of r+3r + 3 fields of |2T+#Q+#A+1||2T + \#Q + \#A + 1| bits each, which hold the tick (a time from 00 to TT), the state, the square of the work head and the squares of the read-only heads. The block tour DM(x,W)D_M(x, W) of MM on xx at WW is the reference tour with parameter kk, controller width c(T)c(T) and NN blocks whose initial controller and block words are those of the configuration at time 00, whose selection sends a controller to the home block of its work head square, and whose visit runs TT local steps of MM on the selected block.✦ The final controller of the block tour DM(x,W)D_M(x, W) is denoted λM(x,W)\lambda_M(x, W).✦ The site WW is complete for MM on xx when the tick of λM(x,W)\lambda_M(x, W) equals TT✦, and the readout ρM(x,W)\rho_M(x, W) is the state of λM(x,W)\lambda_M(x, W) with its halting flag.✦ For a site WW and a content of the work tape, the word of block ii is the base mm packing, least significant digit first, of the codes of the symbols in its bb cells✦: cell jj of block ii has the address ib+j−θib + j - \theta and holds the symbol at tape position that address minus TT when the address lies in 00 to 2T2T, and has code 00 otherwise.✦ The scene of MM on xx at WW at time nn is the pair of a controller and block words read off the configuration at time nn: the controller records the tick nn capped at TT, the state, and the squares of the work head and of the read-only heads, a head position qq giving the address q+Tq + T clamped to 00 to 2T2T, and is the base 2w2^{w} packing of these fields, least significant first, where ww is the field width; the word of each block is its stored word under the work tape content.✦

An accessor for MM is a multitape Turing machine with public input alphabet XX, outputs in AA and four argument tapes, for a cap, a head tag, a sign and a magnitude.✦ An accessor for MM gives access within ss bits on xx with cap TT when, for every head tag hh, naming the work tape or a read-only head, and every position pp in [−T,T][-T, T], run on xx with TT, hh, the sign of pp and the magnitude of pp in binary on its argument tapes, it outputs within ss work bits the symbol that the sensor of MM gives on xx at hh and pp.✦ Input words xix_i, numbers aia_i, sites Wi=(Ti,ki,θi)W_i = (T_i, k_i, \theta_i) and a space bound SS form a resources and access kit for an accessor of MM when TT, kk and θ\theta are computable from aa in space SS, when the register counts Piwi+1P_i^{w_i+1} of the epoch circuits of the tours DM(xi,Wi)D_M(x_i, W_i) fit in space SS, and when, for a constant CC, the accessor gives access within C(Si+1)C(S_i + 1) bits on xix_i with cap TiT_i at every index ii.✦ A multitape Turing machine computes the output yy within ss bits on given inputs when its run from the start state, with the input heads at the left endmarker and every work tape blank with its head at 00, halts with output yy while the head of each work tape stays inside an interval of cells whose total size, each cell counted with the bits needed for a symbol of its tape, is at most ss.✦

The Space Allowance

For a natural number TT, the scale factor K(T)K(T), the integer lg⁡T\lg T, the binary logarithm Log⁡T\operatorname{Log} T and the space allowance Bd(T)B_d(T) of degree dd are K(T)=2⌈|T|/5⌉,lg⁡T=|T|+1,Log⁡T=log⁡2(T+2),Bd(T)=K(T)2(lg⁡T)d+2.K(T) = 2^{\lceil |T|/5 \rceil}, \qquad \lg T = |T| + 1, \qquad \operatorname{Log} T = \log_2(T + 2), \qquad B_d(T) = K(T)^2 (\lg T)^{d+2}.(4)

The Claim

Theorem 1. For a reference tour DD with finite word bounds, the final controller is the digit at place bb, in base mm, of the value at the target: ⌊val(v*)/mb⌋mod⁡m=qEb.\bigl\lfloor \mathrm{val}(v^{*}) / m^{b} \bigr\rfloor \bmod m = q_{Eb}.(5)✦ Let DiD_i, i∈Ii \in I, be reference tours with finite word bounds, runnable on xx in space SS from aa. Then the epoch circuits (𝒞Di)i∈I are ready on x in space S from a.\text{the epoch circuits } (\mathcal{C}_{D_i})_{i \in I} \text{ are ready on } x \text{ in space } S \text{ from } a.(6)✦ If, besides, the family (Eiperi)(E_i\,\mathrm{per}_i) is linear in S+1S + 1, then the final controllers are computable: a→S(qEibi(Di))i∈I.a \xrightarrow{S} \bigl(q_{E_i b_i}(D_i)\bigr)_{i \in I}.(7)✦

Let MM be a multihead machine with sensor over XX. If input words xix_i, numbers aia_i, sites WiW_i and a space bound SS form a resources and access kit for an accessor of MM, then (DM(xi,Wi))i∈I is runnable on x in space S from a.\bigl(D_M(x_i, W_i)\bigr)_{i \in I} \text{ is runnable on } x \text{ in space } S \text{ from } a.(8)✦ If, besides, the family (Eiperi)(E_i\,\mathrm{per}_i) of these tours is linear in S+1S + 1, then the completion bits [Wi complete][W_i \text{ complete}], equal to 11 for a site complete for MM on xix_i and 00 otherwise, and the readouts are computable: a→S([Wi complete])i∈I,a→S(ρM(xi,Wi))i∈I.a \xrightarrow{S} \bigl([W_i \text{ complete}]\bigr)_{i \in I}, \qquad a \xrightarrow{S} \bigl(\rho_M(x_i, W_i)\bigr)_{i \in I}.(9)✦ For an input word xx, a cap TT and a positive kk with T≤k5T \le k^5, there is an offset θ<k2\theta < k^2 for which the site (T,k,θ)(T, k, \theta) is complete for MM on xx: tick⁡λM(x,(T,k,θ))=T.\operatorname{tick} \lambda_M\bigl(x, (T, k, \theta)\bigr) = T.(10)✦ For an input word xx and a site WW with cap TT that is complete for MM on xx, the readout is the outcome at time TT: ρM(x,W)=ωM(x,T).\rho_M(x, W) = \omega_M(x, T).(11)✦ If MM has halted on xx at time tt and at time uu, then ωM(x,t)=ωM(x,u).\omega_M(x, t) = \omega_M(x, u).(12)✦

For a natural number dd, input words xix_i and sites WiW_i whose parameter is the scale factor of the cap, ki=K(Ti)k_i = K(T_i), the tours DM(xi,Wi)D_M(x_i, W_i) satisfy, for a constant CC and every ii, |Piwi+1|≤C(Bd(Ti)+1),Eiperi≤C(Bd(Ti)+1).\bigl|P_i^{\,w_i+1}\bigr| \le C\,\bigl(B_d(T_i) + 1\bigr), \qquad E_i\,\mathrm{per}_i \le C\,\bigl(B_d(T_i) + 1\bigr).(13)✦ For every natural number TT, T≤K(T)5,T \le K(T)^5,(14)✦ and if T≥2T \ge 2, then K(T)5≤32TK(T)^5 \le 32\,T(15)✦ and, for every natural number dd, Bd(T)≤32⋅3d+2T2/5(Log⁡T)d+2.B_d(T) \le 32 \cdot 3^{d+2}\, T^{2/5} (\operatorname{Log} T)^{d+2}.(16)✦ For real numbers α≥1\alpha \ge 1 and β\beta there are natural numbers dd and CC such that, for every natural number TT, α(Log⁡T)β≤C(Bd(T)+1).\alpha\,(\operatorname{Log} T)^{\beta} \le C\,\bigl(B_d(T) + 1\bigr).(17)✦

In the paper, the result reads: Lemma 5, applied to the epoch word graph, the epoch circuit 𝒞D\mathcal{C}_D here, with Δ=(N+1)w\Delta = (N+1)w, yields the final history and its controller in space Õ(w+Ek)=Õ(T2/5)\tilde{O}(w + Ek) = \tilde{O}(T^{2/5}); the offsets are tried with reused storage; and for an unknown running time the caps T=2,4,8,…T = 2, 4, 8, \dots are tried until the machine halts.

What Is Checked

The claim is stated over reference tours with their story, final controller and finite word bounds; the epoch circuit with its vertex values, target, modulus, register count and coins per epoch; ready families of evaluation circuits and runnable families of tours, with computation in space uniform over an index set; the multihead machine with sensor and its outcomes; offset trial sites with the machine’s block tour, its completion and its readout; accessors and resources and access kits; and the space allowance Bd(T)B_d(T) with K(T)K(T), lg⁡T\lg T and Log⁡T\operatorname{Log} T. Beyond the claim, the library proves of these constructions that the modulus PP is prime and that the machine’s block tour meets the conditions of a reference tour, every controller selecting one of its NN blocks.