OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

§1 (setting): simulators, space, the accessor and the access condition: An accessor given xx, TT, a tag hh and a position |l|≤T|l|\le T must halt with σh(x,l)\sigma_h(x,l) within p(LogT)qp(\mathrm{Log}\,T)^q work bits

Simulators, space in work bits and polylogarithmic tape access.

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 MM with one writable tape runs for TT steps on a public word xx, and a simulator is to reproduce the run in two-fifths-power space, a power of TT with exponent γ=2/5.\gamma=2/5.(1)✦

Simulators are deterministic multitape machines with read-only input tapes, and their space is counted in work bits, cells times bits per symbol, the read-only tapes never counted. The tapes of MM reach them through an accessor, a second machine that computes from xx the symbol at a given position of a given tape of MM. The access condition holds the accessor to space polylogarithmic in TT, the logarithm of every bound being LogT=log⁡2(T+2).\mathrm{Log}\,T=\log_2(T+2).(2)✦

Machines and Their Space

A machine DD of the model has a public alphabet XX, a set JJ of argument tapes and a set YY of output labels. It has a finite set QQ of states with a start state q0q_0 and a finite set II of work tapes, tape ii infinite in both directions over a finite alphabet WiW_i with a blank symbol. It reads a public word over XX and a binary word on each argument tape, each framed by a left endmarker ⊢\vdash and a right endmarker ⊣\dashv. A move of a head is left, stay or right✦, a displacement of −1-1, 00 or 11✦. The transition function reads the state, the marks under the read-only heads and the symbols under the work heads; it either halts with a label in YY or gives a new state, a move for each read-only head, and for each work tape a symbol to write and a move: δ:Q×Xˆ×BˆJ×∏i∈IWi→Y⊔(Q×{−1,0,1}×{−1,0,1}J×∏i∈I(Wi×{−1,0,1})),\begin{split} \delta\colon Q\times\hat X\times\hat B^{J}\times\prod_{i\in I}W_i &\longrightarrow Y\sqcup\Bigl(Q\times\{-1,0,1\}\times\{-1,0,1\}^{J}\\ &\qquad\qquad\times\prod_{i\in I}\bigl(W_i\times\{-1,0,1\}\bigr)\Bigr), \end{split}(3)✦ where Xˆ=X⊔{⊢,⊣}\hat X=X\sqcup\{\vdash,\dashv\} and Bˆ={0,1,⊢,⊣}\hat B=\{0,1,\vdash,\dashv\} are the marks a read-only head can see. We write TM(X,J,Y)\mathrm{TM}(X,J,Y) for the set of these machines.

An input ι=(x,(uj)j∈J)\iota=(x,(u_j)_{j\in J}) is a public word x∈X*x\in X^* with a binary word uju_j for each argument tape.✦ A read-only word w1⋯wnw_1\cdots w_n lies at positions 1,…,n1,\dots,n, with ⊢\vdash at 00 and ⊣\dashv at n+1n+1✦, and a move left from ⊢\vdash or right from ⊣\dashv leaves its head in place✦. For numbers f(j)∈ℕf(j)\in\mathbb{N}, the input ⟨x;f⟩\langle x;f\rangle writes each f(j)f(j) in binary, least significant bit first, as the word binf(j)\mathrm{bin}\,f(j), ⟨x;f⟩=(x,(binf(j))j∈J),\langle x;f\rangle=\bigl(x,(\mathrm{bin}\,f(j))_{j\in J}\bigr),(4)✦ and a machine without argument tapes runs on its public word alone, ⟨x⟩=(x,⌀).\langle x\rangle=(x,\varnothing).(5)✦

A work tape is a content ℤ→Wi\mathbb{Z}\to W_i with a head position✦, starting blank with the head at cell 00✦; a step writes the chosen symbol in the head’s cell and then moves the head✦. A configuration CC of DD is a tuple consisting of a state, the positions of the read-only heads and the work tapes; the initial configuration C0C_0 has state q0q_0 and every read-only head on its left endmarker, the work tapes as they start. On an input ι\iota, a step from CC applies δ\delta to what the heads see, written δ(C)\delta(C): it halts when δ(C)∈Y\delta(C)\in Y and otherwise performs the action, giving the next configuration C→C′C\to C'.✦

Tape ii stores wi=max⁡(1,⌈log⁡2|Wi|⌉)w_i=\max\bigl(1,\lceil\log_2|W_i|\rceil\bigr)(6)✦ bits per cell. A window ω\omega gives each work tape ii an interval of cells [−ℓi,ℓi′][-\ell_i,\ell'_i] with ℓi,ℓi′≥0\ell_i,\ell'_i\ge0✦; a configuration lies in ω\omega when every work head is in its interval✦, and the size of ω\omega in bits is ∥ω∥=∑i∈I(ℓi+ℓi′+1)wi.\|\omega\|=\sum_{i\in I}(\ell_i+\ell'_i+1)\,w_i.(7)✦

A machine DD outputs y∈Yy\in Y on an input ι\iota within SS bits, written D(ι)⇓SyD(\iota)\Downarrow_S y, when the following holds: D(ι)⇓Sy⇔∃ω(∥ω∥≤S,C0→C1→⋯→Ct on ι,C0,…,Ct∈ω,δ(Ct)=y).D(\iota)\Downarrow_S y\iff\exists\,\omega\ \bigl(\|\omega\|\le S,\ C_0\to C_1\to\cdots\to C_t \text{ on }\iota,\ C_0,\dots,C_t\in\omega,\ \delta(C_t)=y\bigr).(8)✦

The Simulated Machine and Its Accessor

The simulated machine MM has a finite set of states with a begin state and a set of halting states, a finite alphabet Γ\Gamma, one writable tape and rr further heads that only read. Its program maps the state, the symbol under the writable head and the symbols under the other heads to a new state, a symbol to write and a move for the writable head, and a move for each other head. A tag hh is the writable tape or one of the rr read-only heads✦; the r+1r+1 tags are numbered 0,…,r0,\dots,r in a fixed order, code(h)\mathrm{code}(h) being the number of hh✦. The tapes of MM on a public word xx are given by its sensor: for a tag hh and a position l∈ℤl\in\mathbb{Z}, σh(x,l)∈Γ\sigma_h(x,l)\in\Gamma is the symbol at ll on the tape tagged hh.

An accessor of MM has four argument tapes, Jacc={𝖼𝖺𝗉,𝗍𝖺𝗀,𝗌𝗂𝗀𝗇,𝗆𝖺𝗀},J_{\mathrm{acc}}=\{\mathsf{cap},\mathsf{tag},\mathsf{sign},\mathsf{mag}\},(9)✦ and is a machine with public alphabet XX and output labels Γ\Gamma, A∈TM(X,Jacc,Γ).A\in\mathrm{TM}(X,J_{\mathrm{acc}},\Gamma).(10)✦

For a natural number TT, called the cap and bounding the positions asked for, a tag hh and a position ll, let aT,h,la_{T,h,l} be the assignment of numbers to the four argument tapes given by (11); the accessor is run on ⟨x;aT,h,l⟩\langle x;a_{T,h,l}\rangle. aT,h,l(𝖼𝖺𝗉)=T,aT,h,l(𝗍𝖺𝗀)=code(h),aT,h,l(𝗌𝗂𝗀𝗇)=[l<0],aT,h,l(𝗆𝖺𝗀)=|l|,a_{T,h,l}(\mathsf{cap})=T,\quad a_{T,h,l}(\mathsf{tag})=\mathrm{code}(h),\quad a_{T,h,l}(\mathsf{sign})=[\,l<0\,],\quad a_{T,h,l}(\mathsf{mag})=|l|,(11)✦ where [l<0][\,l<0\,] is 11 when l<0l<0 and 00 otherwise.

Let xx be a public word and TT and ss natural numbers. An accessor AA of MM gives the tapes of MM on xx up to the cap TT within ss bits if every tag hh and every position ll with |l|≤T|l|\le T satisfy A(⟨x;aT,h,l⟩)⇓sσh(x,l).A(\langle x;a_{T,h,l}\rangle)\Downarrow_s\sigma_h(x,l).(12)✦

The Definition

Definition 1 (Access condition). Let MM be a machine with one writable tape, rr read-only heads and sensor σ\sigma, AA an accessor of MM, pp and qq real numbers, xx a public word and TT a natural number. The accessor AA meets the access condition with constants pp and qq on xx at the cap TT when every tag hh and every position ll with |l|≤T|l|\le T satisfy A(⟨x;aT,h,l⟩)⇓sσh(x,l)for some s∈ℕ with s≤p(LogT)q.A(\langle x;a_{T,h,l}\rangle)\Downarrow_s\sigma_h(x,l)\quad\text{for some }s\in\mathbb{N} \text{ with }s\le p\,(\mathrm{Log}\,T)^q.(13)✦

In the paper, the result reads: space counts work bits, the read-only input excluded; the simulator gets xx and a binary cap TT; and the access condition for (x,T)(x,T) asks that for every tag hh and every ll with |l|≤T|l|\le T the accessor, run on (x,h,T,l)(x,h,T,l), halt with σh(x,l)\sigma_h(x,l) using at most C0log⁡C1(T+2)C_0\log^{C_1}(T+2) bits, the constants C0C_0 and C1C_1 in the place of pp and qq.

What Is Checked

The access condition (13) is stated over a machine MM with one writable tape, rr read-only heads and a sensor, an accessor AA of the model (3) with the four argument tapes (9), real constants pp and qq, a public word xx and a cap TT, with space measured in bits by windows (7) and bounds in LogT\mathrm{Log}\,T (2).