OctoInformBeta

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

§3.2 (setting): epochs, histories and checkpoints: E=k+1E = k + 1 epochs of b=k2b = k^2 visits; array vertices hold the blocks entering an epoch, history vertices its controllers in rounds of kk

The epoch circuit of a tour of block visits.

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

Cut the tape of a one-tape machine into blocks and follow its run block by block, as a sequence of visits: each visit rewrites one block and hands a controller, the part of the configuration kept outside the blocks, to the next. To simulate a long run in little space, one lays the run out as a circuit of short words, each determined from a few others by local rules, and evaluates it. The question is the layout: which moments of the run become vertices, what each vertex holds, and which vertex is the target. The library answers it for any run of block visits, which it calls a tour, with the epoch circuit of the tour.

Tours and Their Stories

Controllers and words are natural numbers, read as digit strings with the least significant digit first. A reference tour DD on NN blocks consists of a positive integer kk, a controller width cc in bits, an initial controller q0q_0, an initial word Bi0B^0_i for each block ii, a selection σ\sigma naming for each controller the one block it reads and rewrites, and a visit map δ\delta sending a controller and the word of that block to the next controller and the block’s new word; the number NN is positive, and every selected block has index below NN: D=(k,c,N,q0,B0,σ,δ),k≥1,N≥1,σ:ℕ→{0,…,N−1},δ:ℕ×ℕ→ℕ×ℕ.D = (k, c, N, q_0, B^0, \sigma, \delta), \qquad k \ge 1, \quad N \ge 1, \quad \sigma\colon \mathbb{N} \to \{0, \dots, N - 1\}, \quad \delta\colon \mathbb{N} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N}.(1)✦

Blocks are written in the radix m=2cm = 2^c, the number of controllers of cc bits.✦ A tour has bb digits per block, EE epochs of bb visits, and circuit width dd, the number of bits in b+1b + 1 controllers: b=k2,b = k^2,(2)✦ E=k+1,E = k + 1,(3)✦ d=c(b+1).d = c(b + 1).(4)✦

In the simulation of a run of TT steps, kk is the scale factor K(T)K(T), two to the power p(T)p(T)✦, where p(T)p(T) is the bit length size(T)\mathrm{size}(T) of TT divided by five and rounded up: K(T)=2p(T),p(T)=⌈size(T)/5⌉.K(T) = 2^{p(T)}, \qquad p(T) = \lceil \mathrm{size}(T)/5 \rceil.(5)✦ It satisfies T≤K(T)5≤32TT \le K(T)^5 \le 32T for every T≥1T \ge 1.

A scene is a pair s=(q,B)s = (q, B) of a controller qq and a sequence B=(Bi)i∈ℕB = (B_i)_{i \in \mathbb{N}} of words, BiB_i being the word held by block ii: s=(q,B),q∈ℕ,B∈ℕℕ.s = (q, B), \qquad q \in \mathbb{N}, \quad B \in \mathbb{N}^{\mathbb{N}}.(6)✦

One step τ\tau of DD is a visit. On a scene s=(q,B)s = (q, B) the controller selects the block i=σ(q)i = \sigma(q), the visit map returns the next controller q′q' and the block’s new word uu, and the new scene has controller q′q' and the words B[i↦u]B[i \mapsto u], those of BB with the word of block ii replaced by uu: τ(q,B)=(q′,B[i↦u]),i=σ(q),(q′,u)=δ(q,Bi).\tau(q, B) = \bigl(q', B[i \mapsto u]\bigr), \qquad i = \sigma(q), \quad (q', u) = \delta(q, B_i).(7)✦

The story of DD is the sequence of scenes sn=(qn,Bn)s_n = (q_n, B^n) that starts from the initial controller and words and makes one visit per term, qnq_n being the controller and BinB^n_i the word of block ii after nn visits: s0=(q0,B0),sn+1=τ(sn).s_0 = (q_0, B^0), \qquad s_{n+1} = \tau(s_n).(8)✦

In base mm, the digit of a number uu at place jj is ⌊u/mj⌋mod⁡m\lfloor u/m^j \rfloor \bmod m✦, and digits u0,…,un−1u_0, \dots, u_{n-1} pack into the number ∑j<nujmj\sum_{j<n} u_j m^j✦. The controller history of DD from visit tt over nn steps packs the n+1n + 1 controllers of the story at visits tt through t+nt + n: L(t,n)=∑i=0nqt+imi.L(t, n) = \sum_{i=0}^{n} q_{t+i}\, m^{i}.(9)✦

Evaluation Circuits

An evaluation circuit 𝒞\mathcal{C} of width dd with ℓ\ell children per node consists of the nodes 0,…,n−10, \dots, n - 1, some of them marked as base nodes, together with the following data. Each node vv has a head child h(v)h(v), children ch(v,i)\mathrm{ch}(v, i) for i<ℓi < \ell, a number g(v)g(v) of guessed bits, a first value f(v)f(v), the value prescribed at a base node, and a semantic value val(v)\mathrm{val}(v), the value the node is meant to carry. Its two local rules are a proposal π(v,z,y,x)\pi(v, z, y, x), a number for each node vv, 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.

A word uu of width dd is augmented to the sequence of its augmented bits uˆz\hat{u}_z: the binary digit of uu at place zz for z<dz < d, the bit 11 for z=dz = d, and 00 for z>dz > d.✦

The Definition

Definition 1. Let DD be a reference tour. The vertices of its epoch circuit are the numbers below E(N+k+1)E(N + k + 1): VD={0,1,…,E(N+k+1)−1}.V_D = \{0, 1, \dots, E(N + k + 1) - 1\}.(10)✦ They are laid out in EE epochs of N+k+1N + k + 1 columns: vertex vv lies in epoch ⌊v/(N+k+1)⌋\lfloor v/(N + k + 1) \rfloor and column vmod⁡(N+k+1)v \bmod (N + k + 1)✦, and ve,jv_{e,j} denotes the vertex e(N+k+1)+je(N + k + 1) + j, taken modulo E(N+k+1)E(N + k + 1)✦. In each epoch, column j<Nj < N holds the array vertex of block jj, column NN the start vertex, and column N+rN + r, for 1≤r≤k1 \le r \le k, the history vertex of round rr; the round index of ve,jv_{e,j} is r=max⁡(j−N,0)r = \max(j - N, 0).

The value of an array vertex is the word of its block after ebeb visits, and the value of a vertex in a column j≥Nj \ge N, of round index rr, packs the epoch’s incoming controller and the first rkrk outgoing ones: val(ve,j)={Bjeb,j<N,L(eb,rk),j≥N.\mathrm{val}(v_{e,j}) = \begin{cases} B^{eb}_j, & j < N,\\ L(eb, rk), & j \ge N. \end{cases}(11)✦

The head of an array vertex or of a start vertex is the history vertex of round kk in the previous epoch, and the head of the history vertex of round rr is the vertex of round index r−1r - 1 in its own epoch: h(ve,j)={ve−1,N+k,j≤N,ve,N+r−1,j>N.h(v_{e,j}) = \begin{cases} v_{e-1,\,N+k}, & j \le N,\\ v_{e,\,N+r-1}, & j > N. \end{cases}(12)✦

Each child of an array vertex is the vertex of the same block in the previous epoch, each child of a start vertex is its head, and child ii of a history vertex is the vertex in column ii of its epoch: ch(ve,j,i)={ve−1,j,j<N,h(ve,j),j=N,ve,i,j>N.\mathrm{ch}(v_{e,j}, i) = \begin{cases} v_{e-1,\,j}, & j < N,\\ h(v_{e,j}), & j = N,\\ v_{e,\,i}, & j > N. \end{cases}(13)✦

The set VDbaseV^{\mathrm{base}}_D of base vertices consists of the array vertices and the start vertex of epoch 00, the vertices v0,jv_{0,j} with j≤Nj \le N.✦ The first value f(ve,j)f(v_{e,j}) is the initial word Bj0B^0_j for j<Nj < N and the initial controller q0q_0 otherwise.✦ A vertex in a column up to NN has g(v)=0g(v) = 0 guessed bits, and a history vertex has g(v)=ckg(v) = ck guessed bits, the length of kk controllers.✦

A transcript is a number ZZ whose digits in base mm are read as successive controllers. A replay step of block ii is a map taking a word, a verdict (a truth value) and a digit of a transcript ZZ to a new word and a new verdict. Replaying block ii under a transcript ZZ from a word aa gives a sequence of pairs of a word and a verdict: it starts from amod⁡mba \bmod m^b with the verdict true, and its term n+1n + 1 is one replay step, at digit nn of ZZ, from its term nn; write ρn(i,Z,a)\rho_n(i, Z, a) and εn(i,Z,a)\varepsilon_n(i, Z, a) for the word and the verdict of term nn.✦

The round proposal Pv(x,y)P_v(x, y) at the history vertex vv of round rr, from a head value xx and a guess yy, is the number whose lowest (r−1)k+1(r - 1)k + 1 digits are those of xx and whose higher digits are those of yy.✦

The proposal π(v,z,y,x)\pi(v, z, y, x) is 11 at an array vertex; at a start vertex it is the augmented bit zz of the digit of xx at place bb, and at a history vertex the augmented bit zz of Pv(x,y)P_v(x, y).✦ The admissibility test α(v,z,y,i,x,a)\alpha(v, z, y, i, x, a) is 11 at a start vertex, and at an array vertex for every child i≠0i \ne 0. For child 00 of the array vertex of block jj it is the augmented bit zz of ρb(j,x,a)\rho_b(j, x, a), and at the history vertex of round rr it is the verdict εrk(i,Pv(x,y),a)\varepsilon_{rk}(i, P_v(x, y), a), read as 00 or 11.

The epoch circuit 𝒞D\mathcal{C}_D of DD is the evaluation circuit of width dd with NN children per node on the vertices VDV_D, with these base vertices, first values, guessed bits and rules, head hh, children ch\mathrm{ch} and semantic value val\mathrm{val}: 𝒞D=(d,N,VD;VDbase,h,ch,g,f,π,α,val).\mathcal{C}_D = \bigl(d,\ N,\ V_D;\ V^{\mathrm{base}}_D,\ h,\ \mathrm{ch},\ g,\ f,\ \pi,\ \alpha,\ \mathrm{val}\bigr).(14)✦ The target v*v^{*} of 𝒞D\mathcal{C}_D is the history vertex of round kk in the last epoch: v*=vE−1,N+k.v^{*} = v_{E-1,\,N+k}.(15)✦

In the paper, the result reads: k=⌈T1/5⌉k = \lceil T^{1/5} \rceil, b=k2b = k^2 and E=⌈⌈1+T/b⌉/b⌉E = \lceil \lceil 1 + T/b \rceil / b \rceil epochs of bb visits in kk rounds of kk; words of width d=max⁡{1,bℓΣ,(b+1)c}d = \max\{1, b\ell_\Sigma, (b + 1)c\}, with ℓΣ\ell_\Sigma bits per tape symbol; array words Ae,iA_{e,i}, the represented block ii after ebeb visits, and history words He,jH_{e,j}, the epoch’s incoming controller and the first jkjk outgoing ones; base, checkpoint and extraction rules; and the target HE−1,kH_{E-1,k}.

What Is Checked

The definition is stated over a reference tour (1) with its story of scenes (8) and its controller histories (9), and over evaluation circuits, of which the epoch circuit (14) is one.