OctoInformBeta

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

Lemma 6 [A visit accesses one block]: A visit crosses a block boundary or reaches time TT, and when T≤k5T \le k^5 some offset reaches TT after (k+1)k2(k+1)k^2 visits

Each visit runs the machine inside a single block.

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 a machine MM with one work tape and rr read-only heads, run for TT steps on an input word xx. In that time its work head stays among the positions in [−T,T][-T, T], written as the addresses 00 to 2T2T. Shift the addresses by an offset aa and cut them into blocks of b=k2b = k^2 cells, for a block parameter kk. A visit runs MM while its work head stays in one block, with the rest of the configuration kept in a controller of some number cc of bits, and the run becomes a sequence of visits, each to the block that holds the work head. The question is whether these visits reproduce the run, and how many of them it takes to reach time TT for some offset. Selecting the block and making a visit are to be computable in small space.

The machine MM is a multihead machine with sensor over an input alphabet XX: it has a finite set of states QQ with a start state and halting states, a finite tape alphabet Γ\Gamma, rr read-only heads, and a program that maps the state and the symbols under all heads to a new state, a symbol to write and a move for the work head, and a move for each read-only head.✦ Its sensor presents the input word xx, giving for the work tape or a read-only head and an integer position the symbol of Γ\Gamma found there: the initial content of the work tape, or what that head reads. The configuration of MM on xx at time tt is its state, its work tape with the head position, and its read-only head positions after tt steps from the start state with all heads at 00; a step in a halting state changes nothing.✦

A block site W=(T,k,a)W = (T, k, a) consists of a time bound TT, a block parameter k>0k > 0 and an offset a<k2a < k^2; its blocks have b=k2b = k^2 slots, and there are N=2T+b+2N = 2T + b + 2 of them.✦ The home block of an address ss in [0,2T][0, 2T] at WW is the block ⌊(a+s)/b⌋\lfloor (a + s)/b \rfloor, in which ss sits at slot (a+s)mod⁡b(a + s) \bmod b; slot jj of block ii holds the address ib+j−aib + j - a when this lies in [0,2T][0, 2T].

Scenes, Visits and Tours

Fix enumerations of QQ and Γ\Gamma, whose positions are the codes of states and symbols, and let ww be the bit length of 2T+|Q|+|Γ|+12T + |Q| + |\Gamma| + 1.✦ The controller ztz_t of MM on xx at time tt is the number whose r+3r + 3 fields of ww bits, least significant first, hold the tick min⁡(t,T)\min(t, T), the code of the state, the address of the work head and the addresses of the read-only heads, a position qq having the address q+Tq + T clamped to [0,2T][0, 2T]. A controller has c=(r+3)wc = (r + 3)w bits, and m=2cm = 2^c is the block radix. The block word Bi(t)B_i(t) of block ii at time tt is the bb-digit number in base mm whose digit jj is the code of the symbol in the cell at address ib+j−aib + j - a, and 00 when slot jj holds no address.✦ The scene Σt\Sigma_t at time tt is the pair of ztz_t and the sequence B(t)=(Bi(t))iB(t) = (B_i(t))_i of block words.✦

The block βW(t)\beta_W(t) of the head at time tt is the home block of the work head’s address at time tt.✦ The crossing count χW(t)\chi_W(t) is the number of steps before tt that change the block of the head: χW(t)=#{s<t:βW(s)≠βW(s+1)}.\chi_W(t) = \#\{\, s < t : \beta_W(s) \neq \beta_W(s + 1) \,\}.(1)✦

A controller zz records, in its fields, a tick τ(z)≤T\tau(z) \le T, a state, a work head address s(z)s(z) and read-only head addresses.✦ The selected block selW(z)\mathrm{sel}_W(z) of a controller zz is the home block of s(z)s(z) at WW.✦ The local step λi\lambda_i on block ii is the map on pairs of a controller zz and a block word BB that leaves the pair unchanged unless τ(z)<T\tau(z) < T and selW(z)=i\mathrm{sel}_W(z) = i, and acts as follows when both hold.✦ It makes one move of MM in the recorded state, reading under the work head the symbol coded by digit (a+s(z))mod⁡b(a + s(z)) \bmod b of BB, and under each read-only head the symbol the sensor gives at its address.✦ It returns the controller with the tick raised by one, the new state and each head address moved one cell in its direction within [0,2T][0, 2T], together with BB with that digit replaced by the code of the written symbol. The sweep sweepn(z,B)\mathrm{sweep}^n(z, B) of nn steps from a controller zz and a block word BB is the nn-fold iterate of the local step on the block that zz selects, and the visit VisitW(z,B)\mathrm{Visit}_W(z, B) is the sweep of TT steps: sweepn(z,B)=λselW(z)n(z,B),VisitW(z,B)=sweepT(z,B).\mathrm{sweep}^n(z, B) = \lambda_{\mathrm{sel}_W(z)}^{\,n}(z, B), \qquad \mathrm{Visit}_W(z, B) = \mathrm{sweep}^T(z, B).(2)✦

A block tour with parameters k>0k > 0, cc and N>0N > 0 consists of an initial controller, an initial block word for each index, a selector sel\mathrm{sel} mapping controllers to block indices below NN, and a visit map Visit\mathrm{Visit} mapping a controller and a block word to a controller and a block word; its radix is m=2cm = 2^c and its blocks have b=k2b = k^2 digits.✦ A scene of the tour is a controller zz together with a block word BiB_i for each index ii.✦ The step step\mathrm{step} of the tour sends a scene to the scene obtained by visiting the selected block and writing it back: step(z,B)=(z′,B[i←B′]),i=sel(z),(z′,B′)=Visit(z,Bi).\mathrm{step}(z, B) = \bigl(z', B[i \leftarrow B']\bigr), \qquad i = \mathrm{sel}(z), \quad (z', B') = \mathrm{Visit}(z, B_i).(3)✦ The story of a block tour is the sequence of scenes S0,S1,…S_0, S_1, \dots of the tour in which S0S_0 is the initial controller with the initial block words and Sn+1=step(Sn)S_{n+1} = \mathrm{step}(S_n).✦ The tour of MM on xx at WW is the block tour with the parameters kk, cc and NN of WW, initial scene Σ0\Sigma_0, selector selW\mathrm{sel}_W and visit map VisitW\mathrm{Visit}_W; ζnW\zeta^W_n denotes the controller of its scene SnS_n.✦ In a block tour with parameter kk, an epoch is a group of bb visits, and the first (k+1)k2(k+1)k^2 visits make up its E=k+1E = k + 1 epochs.

Computing in Small Space

For families indexed by ι∈I\iota \in I of words xιx_\iota and numbers SιS_\iota, uιu_\iota and vιv_\iota, the family vv is computable from uu in space SS, written u⇝Svu \rightsquigarrow_S v, when one fixed stack machine, at every index ι\iota, reads xιx_\iota as its public input and turns a stack holding the bits of uιu_\iota into one holding the bits of vιv_\iota, least significant first, within C(Sι+1)C(S_\iota + 1) work bits, for a constant CC independent of ι\iota.✦ The pair ⟨u,v⟩\langle u, v \rangle of two numbers is the number whose binary digits, least significant first, are those of uu, each preceded by a 00, then a 11, then those of vv.✦

A multitape Turing machine AA gives access within ss bits on xιx_\iota when, for the work tape or a read-only head and every position q∈[−Tι,Tι]q \in [-T_\iota, T_\iota], it computes within ss work bits, from public input xιx_\iota and, in binary on its argument tapes, TιT_\iota, the head and the sign and magnitude of qq, the symbol the sensor of MM gives for that head at qq.✦

Let pιp_\iota be the largest prime pp with D+1<p≤2D+2D + 1 < p \le 2D + 2 for D=(Nι+1)cι(bι+1)D = (N_\iota + 1)c_\iota(b_\iota + 1), the prime modulus of the circuit of width cι(bι+1)c_\iota(b_\iota + 1) that evaluates the story of the tour of MM on xιx_\iota at WιW_\iota over the field of pιp_\iota elements.✦ Families xιx_\iota, SιS_\iota, uιu_\iota and block sites Wι=(Tι,kι,aι)W_\iota = (T_\iota, k_\iota, a_\iota) form a kit for MM with an accessor machine AA when TT, kk and aa are computable from uu in space SS, the bit length of pιcι(bι+1)+1p_\iota^{\,c_\iota(b_\iota + 1) + 1} is at most a constant times Sι+1S_\iota + 1, and AA gives access to the sensor within d(Sι+1)d(S_\iota + 1) bits for a constant dd.✦

The Claim

Theorem 1. Let MM be a multihead machine with sensor, xx an input word and W=(T,k,a)W = (T, k, a) a block site, with scenes Σt=(zt,B(t))\Sigma_t = (z_t, B(t)), block of the head βW\beta_W, crossing count χW\chi_W and block radix mm. The tour of MM on xx at WW has bounded words: z0<m,Bi(0)<mbfor every i,VisitW([0,m)×[0,mb))⊆[0,m)×[0,mb).z_0 < m, \qquad B_i(0) < m^b \ \text{for every } i, \qquad \mathrm{Visit}_W\bigl([0, m) \times [0, m^b)\bigr) \subseteq [0, m) \times [0, m^b).(4)✦ If n<Tn < T and βW(n)=i\beta_W(n) = i, then λi(zn,Bi(n))=(zn+1,Bi(n+1)),Bj(n+1)=Bj(n)for every j≠i.\lambda_i\bigl(z_n, B_i(n)\bigr) = \bigl(z_{n+1}, B_i(n+1)\bigr), \qquad B_j(n+1) = B_j(n) \ \text{for every } j \neq i.(5)✦ If t≤Tt \le T and i=βW(t)i = \beta_W(t), then for every nn there is a time jj with t≤j≤Tt \le j \le T and sweepn(zt,Bi(t))=(zj,Bi(j)).\mathrm{sweep}^n\bigl(z_t, B_i(t)\bigr) = \bigl(z_j, B_i(j)\bigr).(6)✦ If t≤Tt \le T, there is a time jj with t≤j≤Tt \le j \le T and step(Σt)=Σj,j=TorχW(j)>χW(t).\mathrm{step}(\Sigma_t) = \Sigma_j, \qquad j = T \ \text{or} \ \chi_W(j) > \chi_W(t).(7)✦ For every nn there is a time t≤Tt \le T with Sn=Σt,t=TorχW(t)≥n.S_n = \Sigma_t, \qquad t = T \ \text{or} \ \chi_W(t) \ge n.(8)✦ For every TT and every k>0k > 0, ∑a<k2χ(T,k,a)(T)≤T.\sum_{a < k^2} \chi_{(T, k, a)}(T) \le T.(9)✦ If T≤k5T \le k^5, there is an offset a<k2a < k^2 with τ(ζ(k+1)k2(T,k,a))=T.\tau\bigl(\zeta^{(T, k, a)}_{(k+1)k^2}\bigr) = T.(10)✦ Let finally families xιx_\iota, SιS_\iota, uιu_\iota and WιW_\iota form a kit for MM with an accessor machine AA, and let z=(zι)ι∈Iz = (z_\iota)_{\iota \in I} be a family of numbers with u⇝Szu \rightsquigarrow_S z. Then u⇝S(selWι(zι))ι∈I.u \rightsquigarrow_S \bigl(\mathrm{sel}_{W_\iota}(z_\iota)\bigr)_{\iota \in I}.(11)✦ If moreover y=(yι)ι∈Iy = (y_\iota)_{\iota \in I} is a family of numbers with u⇝Syu \rightsquigarrow_S y, zι<mιz_\iota < m_\iota and yι<mιbιy_\iota < m_\iota^{\,b_\iota}, with mιm_\iota the block radix and bιb_\iota the number of digits of a block at WιW_\iota, and (zι′,yι′)(z'_\iota, y'_\iota) is the visit VisitWι(zι,yι)\mathrm{Visit}_{W_\iota}(z_\iota, y_\iota) of MM on xιx_\iota, then u⇝S(⟨zι′,yι′⟩)ι∈I.u \rightsquigarrow_S \bigl(\langle z'_\iota, y'_\iota \rangle\bigr)_{\iota \in I}.(12)✦

In the paper, the result reads: some offset has at most T/bT/b block crossings in the capped computation, and for it at most R=⌈1+T/b⌉R = \lceil 1 + T/b \rceil visits reach the halt or timeout; for every offset aa there are total maps sela\mathrm{sel}_a and Visita\mathrm{Visit}_a on raw words, standing for selW\mathrm{sel}_W and VisitW\mathrm{Visit}_W, such that a visit changes only the selected block, agrees with the capped computation on represented actual data, and is computable in O((b+1)polylogT)O((b + 1)\,\mathrm{polylog}\,T) work bits.

What Is Checked

The claim is stated over the scenes Σt\Sigma_t of MM on xx at a block site WW, the crossing count (1), the local step and the visit (2), and the tour of MM on xx at WW with its step (3) and its story; (11) and (12) are stated over computability in space SS under a kit. The library also states, for the sweep started from the scene at time tt on the block ii that its controller selects, that each iteration advances the simulated run by exactly one tick as long as neither time TT nor a block crossing has been reached, that once the head leaves block ii the sweep rests at the scene just after that crossing, and that no block other than ii is changed.✦