OctoInformBeta

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

§3.1 (setting): controllers, blocks and represented blocks: Addresses 00 to 2T2T cut into N=2T+b+2N = 2T + b + 2 blocks of width b=k2b = k^2, controllers packed into r+3r + 3 digits and parsed back exactly

A configuration as a packed controller and its blocks.

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

A deterministic machine with one writable tape and rr read-only heads runs on an input word xx for at most TT steps, the cap. Its heads start at position 00, and in TT steps none of them leaves the positions −T-T to TT. To evaluate such a run in less space, the writable tape is cut into blocks of bb consecutive cells, and the machine at time nn is described by a controller, a short record of its finite control and its heads, together with one number for each block. The item fixes these blocks and numbers, which together form the view of the run at time nn.

Machines and Runs

A multihead machine with sensor MM over an input alphabet XX has a finite set QQ of states with a start state and a set of halting states, a finite tape alphabet AA, a number rr of read-only heads besides its writable tape, and a program.✦ A direction is one of left, stay and right✦, whose displacements δ\delta are −1-1, 00 and +1+1✦. An action consists of a next state, a symbol of AA to write with a direction for the writable head, and a direction for each read-only head; the program gives an action for every state, symbol under the writable head and choice of symbols under the read-only heads.✦ The sensor presents an input word xx over XX: for the writable tape or a read-only head and an integer position, it gives the symbol of AA found there.

A configuration CC of MM consists of a state qCq_C, the writable tape, given by its content λC:ℤ→A\lambda_C \colon \mathbb{Z} \to A and the position hC∈ℤh_C \in \mathbb{Z} of its head, and the positions hC,0,…,hC,r−1∈ℤh_{C,0}, \dots, h_{C,r-1} \in \mathbb{Z} of the read-only heads.✦ On xx, the initial configuration IxI_x is in the start state, with every head at position 00 and the writable tape holding the content the sensor gives for it.✦ The next configuration next⁡x(C)\operatorname{next}_x(C) applies the program’s action for the state qCq_C, the symbol λC(hC)\lambda_C(h_C) under the writable head and the symbols the sensor gives on xx under the read-only heads, except that in a halting state the machine keeps its state, rewrites λC(hC)\lambda_C(h_C) and moves no head. The new configuration has the action’s state, the action’s symbol written at hCh_C with the writable head shifted by the displacement of its direction, and each read-only head shifted by the displacement of its own.✦ The configurations of the run of MM on xx are C0(x)=Ix,Cn+1(x)=next⁡x(Cn(x)),C_0(x) = I_x, \qquad C_{n+1}(x) = \operatorname{next}_x\bigl(C_n(x)\bigr),(1)✦ and λn\lambda_n denotes the content of the writable tape of Cn(x)C_n(x).

Digits and Widths

A natural number is read as a digit string, least significant digit first. In base BB, the digit of uu at place jj and the packing of the first nn terms of a digit sequence dd are get⁡B(u,j)=⌊u/Bj⌋mod⁡B,pack⁡B(d,n)=∑j<ndjBj.\operatorname{get}_B(u, j) = \lfloor u / B^j \rfloor \bmod B, \qquad \operatorname{pack}_B(d, n) = \sum_{j<n} d_j\, B^j.(2) The index code #a\#a of an element aa of a finite set AA is its position in a fixed enumeration of AA by 0,…,|A|−10, \dots, |A| - 1✦, and dec⁡A(u)\operatorname{dec}_A(u), the element decoded from a natural number uu, is the one whose index code is umod⁡|A|u \bmod |A|✦.

For a cap TT, the field width w(T)w(T) is the number of binary digits of 2T+|Q|+|A|+12T + |Q| + |A| + 1✦ and the field base is 2w(T)2^{w(T)}✦. A controller is packed into r+3r + 3 fields of w(T)w(T) binary digits each; the controller width and the block radix are c(T)=(r+3)w(T),m=2c(T).c(T) = (r + 3)\, w(T), \qquad m = 2^{c(T)}.(3)

The Claim

Definition 1. Let MM be a multihead machine with sensor over XX, with states QQ, tape alphabet AA and rr read-only heads. The squares of a cap TT are the addresses ST={0,1,…,2T},S_T = \{0, 1, \dots, 2T\},(4)✦ the square ss stands for the displacement disp⁡(s)=s−T,\operatorname{disp}(s) = s - T,(5)✦ and an integer pp is placed at the square sq⁡T(p)=min⁡(2T,max⁡(0,p+T)).\operatorname{sq}_T(p) = \min\bigl(2T, \max(0, p + T)\bigr).(6)✦

A site WW is a cap TT with a positive integer kk and an offset ℓ\ell below k2k^2, W=(T,k,ℓ),k≥1,0≤ℓ<k2.W = (T, k, \ell), \qquad k \ge 1, \quad 0 \le \ell < k^2.(7)✦ A site W=(T,k,ℓ)W = (T, k, \ell) has a block width bb and a number of blocks NN, given by b=k2,b = k^2,(8)✦ N=2T+b+2,N = 2T + b + 2,(9)✦ and a square s∈STs \in S_T lies in the home block home⁡(s)=⌊(ℓ+s)/b⌋\operatorname{home}(s) = \lfloor (\ell + s) / b \rfloor(10)✦ at the slot slot⁡(s)=(ℓ+s)mod⁡b.\operatorname{slot}(s) = (\ell + s) \bmod b.(11)✦

A controller cc of cap TT consists of a tick t∈{0,…,T}t \in \{0, \dots, T\}, a state q∈Qq \in Q, the square h∈STh \in S_T of the writable head and the squares h0,…,hr−1∈STh_0, \dots, h_{r-1} \in S_T of the read-only heads.✦ The controller of a configuration CC at time nn is ctrl⁡T(n,C)=(min⁡(T,n),qC,sq⁡T(hC),sq⁡T(hC,0),…,sq⁡T(hC,r−1)).\operatorname{ctrl}_T(n, C) = \bigl(\min(T, n),\ q_C,\ \operatorname{sq}_T(h_C),\ \operatorname{sq}_T(h_{C,0}), \dots, \operatorname{sq}_T(h_{C,r-1})\bigr).(12)✦ The packing ⟨c⟩\langle c \rangle of a controller c=(t,q,h,h0,…,hr−1)c = (t, q, h, h_0, \dots, h_{r-1}) of cap TT is the natural number whose r+3r + 3 digits in the field base, with w=w(T)w = w(T), are tt, #q\#q, hh and h0,…,hr−1h_0, \dots, h_{r-1}, ⟨c⟩=t+#q2w+h22w+∑j<rhj2(j+3)w,\langle c \rangle = t + \#q\, 2^{w} + h\, 2^{2w} + \sum_{j<r} h_j\, 2^{(j+3)w},(13) The parsing parse⁡T(z)\operatorname{parse}_T(z) of a natural number zz, with digits zi=get⁡2w(z,i)z_i = \operatorname{get}_{2^{w}}(z, i), is the controller of cap TT whose fields are read from the digits of zz: parse⁡T(z)=(min⁡(T,z0),dec⁡Q(z1),min⁡(2T,z2),min⁡(2T,z3),…,min⁡(2T,zr+2)).\operatorname{parse}_T(z) = \bigl(\min(T, z_0),\ \operatorname{dec}_Q(z_1),\ \min(2T, z_2),\ \min(2T, z_3), \dots, \min(2T, z_{r+2})\bigr).(14)

For a tape content λ:ℤ→A\lambda \colon \mathbb{Z} \to A, the glimpse of cell jj of block ii is the index code of the symbol at the cell’s position when the cell is within reach, and that of the filler dec⁡A(0)\operatorname{dec}_A(0), the symbol of index code 00, otherwise: gi(j)={#λ(ib+j−ℓ−T)if ℓ≤ib+j≤ℓ+2T,#dec⁡A(0)otherwise.g_i(j) = \begin{cases} \#\lambda(ib + j - \ell - T) & \text{if } \ell \le ib + j \le \ell + 2T,\\ \#\operatorname{dec}_A(0) & \text{otherwise}. \end{cases}(15)✦ The represented block βi(λ)\beta_i(\lambda) of block ii of λ\lambda is the natural number whose digits in the radix m=2c(T)m = 2^{c(T)} are the glimpses of its bb cells: βi(λ)=∑j<bgi(j)mj.\beta_i(\lambda) = \sum_{j<b} g_i(j)\, m^j.(16)✦

A scene is a pair of a natural number and a sequence of natural numbers.✦ The view at time nn of MM on an input word xx over the site WW is the scene of the packed controller of Cn(x)C_n(x) and every represented block of its tape content λn\lambda_n: Vn(x)=(⟨ctrl⁡T(n,Cn(x))⟩,(βi(λn))i∈ℕ).V_n(x) = \bigl(\langle \operatorname{ctrl}_T(n, C_n(x)) \rangle,\ (\beta_i(\lambda_n))_{i \in \mathbb{N}}\bigr).(17)✦

In the paper, the result reads: raw controllers of c=O(log⁡(T+2))c = O(\log(T + 2)) bits hold the state, flags, the elapsed time and the head displacements; for a width bb and an offset aa, the physical blocks are [a+vb,a+(v+1)b−1][a + vb, a + (v + 1)b - 1] for integers vv; the NN blocks are those meeting IT=[−T,T]I_T = [-T, T]; and the represented block rep⁡T,i(Γ)\operatorname{rep}_{T,i}(\Gamma) of the configuration Γ\Gamma carries a filler outside ITI_T.

What Is Checked

The definition is stated over a multihead machine with sensor MM over XX, its run Cn(x)C_n(x) on an input word xx and a site W=(T,k,ℓ)W = (T, k, \ell). Of these constructions the library proves that parsing inverts packing: every controller cc of cap TT satisfies parse⁡T(⟨c⟩)=c.\operatorname{parse}_T(\langle c \rangle) = c.(18)✦