OctoInformBeta

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

Theorem 1 [One-tape simulation in two-fifths-power space]: One fixed simulator finds the state of the machine at time TT and whether it has halted, within cT2/5(Log⁡T)ecT^{2/5}(\operatorname{Log}T)^e work bits

Simulating one-tape machines with accessible symbols in space Õ(T2/5)\tilde O(T^{2/5})..

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 has a finite control, one writable tape and a fixed number of read-only heads. What its read-only heads see, and what its writable tape holds at the start, depend on a public input xx, and a second machine, the accessor, computes the symbol at each position from xx. Given xx and a cap TT in binary, the task is to find the state of MM at time TT and whether MM has halted by then, with as few bits of work space as possible. With no cap given, the question is the final state of MM on an input on which it halts.

Turing Machines and Work Bits

A Turing machine NN over an input alphabet XX consists of a finite set of states with a start state, a read-only public input tape, read-only argument tapes over {0,1}\{0, 1\}, finitely many work tapes, tape kk with a finite alphabet WkW_k containing a blank, and a transition table.✦ A read-only tape holds its word uu between a left endmarker at position 00 and a right endmarker at position |u|+1|u| + 1✦; its head starts at 00 and never moves past an endmarker. The work tapes are infinite in both directions and start blank with their heads at cell 00.✦ In one step, from its state, the marks under its read-only heads and the symbols under its work heads, NN either halts with an output yy or enters a new state, moves each read-only head by at most one cell, and on each work tape writes a symbol and moves by at most one cell.✦ Numbers on argument tapes are written in binary, least significant bit first, and for a machine NN with mm argument tapes, N(x;n1,…,nm)N(x; n_1, \dots, n_m) is NN on the public input x∈X*x \in X^* with njn_j on its jjth argument tape; N(x)N(x) has no argument tape.✦

A window for NN gives each work tape kk an interval [−λk,μk][-\lambda_k, \mu_k] of cells✦, and its size in bits is ∑k(λk+μk+1)βk,βk=max⁡(1,⌈log⁡2|Wk|⌉),\sum_k (\lambda_k + \mu_k + 1)\,\beta_k, \qquad \beta_k = \max\bigl(1, \lceil \log_2 |W_k| \rceil\bigr),(1)✦ where βk\beta_k is the number of bits per symbol of tape kk. The machine NN computes yy on (x;n1,…,nm)(x; n_1, \dots, n_m) within ss work bits, written N(x;n1,…,nm)⇓syN(x; n_1, \dots, n_m) \Downarrow_s y, if its run from the initial configuration halts with output yy and some window of at most ss bits holds every work head throughout the run.✦

The Simulated Machine

A one-tape machine MM with rr read-only heads over the input alphabet XX consists of a finite set of states QQ with a start state q0q_0 and a set of halting states, a finite tape alphabet Γ\Gamma, a transition function δ:Q×Γ×Γr→Q×(Γ×D)×Dr,D={−1,0,1},\delta : Q \times \Gamma \times \Gamma^r \to Q \times (\Gamma \times D) \times D^r, \qquad D = \{-1, 0, 1\},(2)✦ and a sensor σ\sigma, which gives a symbol σx(h,ℓ)∈Γ\sigma_x(h, \ell) \in \Gamma for every word x∈X*x \in X^*, every tag hh and every position ℓ∈ℤ\ell \in \mathbb{Z}, a tag being one of the read-only heads 1,…,r1, \dots, r or the writable tape w\mathrm{w}. On input xx, the writable tape starts with σx(w,ℓ)\sigma_x(\mathrm{w}, \ell) in cell ℓ\ell, and every head starts at position 00.✦ In a state qq that is not halting, with γ\gamma under the writable head and read-only head jj at position ℓj\ell_j, the value δ(q,γ,(σx(j,ℓj))j≤r)\delta(q, \gamma, (\sigma_x(j, \ell_j))_{j \le r}) gives the next state, the symbol written under the writable head with that head’s move, and the moves of the read-only heads; in a halting state nothing changes. If qnq_n is the state after nn steps, the outcome of MM on xx at time nn is outM(x,n)=(qn,ηn)∈Q×{0,1},\mathrm{out}_M(x, n) = (q_n, \eta_n) \in Q \times \{0, 1\},(3)✦ where the flag ηn\eta_n is 11 when qnq_n is halting and 00 when MM is still running at time nn. The machine MM has halted on xx by time tt when ηt=1\eta_t = 1.

The code ⌜v⌝\ulcorner v \urcorner of an element vv of a finite set is its index in a fixed enumeration of that set.✦ An accessor for MM is a Turing machine AA over XX with four argument tapes, whose outputs are symbols of Γ\Gamma✦; on the query for the tag hh and the position ℓ\ell under the cap TT, its argument tapes hold TT, ⌜h⌝\ulcorner h \urcorner, the sign bit [ℓ<0][\ell < 0] and |ℓ||\ell|.✦ The accessor AA serves xx at cap TT within ss work bits if A(x;T,⌜h⌝,[ℓ<0],|ℓ|)⇓sσx(h,ℓ)for every tag h and every ℓ∈[−T,T].A(x; T, \ulcorner h \urcorner, [\ell < 0], |\ell|) \Downarrow_s \sigma_x(h, \ell) \quad \text{for every tag $h$ and every $\ell \in [-T, T]$.}(4)✦ For reals pp and qq, the pair (x,T)(x, T) satisfies the access condition if AA serves xx at cap TT within p(Log⁡T)qp(\operatorname{Log} T)^q work bits, where Log⁡T=log⁡2(T+2)\operatorname{Log} T = \log_2(T + 2).✦

Allowances and Register Computations

Write |T||T| for the bit length of TT and lg⁡T=|T|+1\lg T = |T| + 1.✦ The scale K(T)K(T) and, for d∈ℕd \in \mathbb{N}, the space allowance Bd(T)B_d(T) are K(T)=2⌈|T|/5⌉,Bd(T)=K(T)2(lg⁡T)d+2.K(T) = 2^{\lceil |T|/5 \rceil}, \qquad B_d(T) = K(T)^2 (\lg T)^{d+2}.(5)

A stack machine over XX consists of a finite set of states with a start state, read-only heads on a public input and on argument tapes as above, finitely many binary stacks, one of them distinguished as the register, and a transition table.✦ In one step, from its state, the marks under its heads and the top bit of each stack, or the fact that it is empty, the machine either halts with an output or enters a new state, moves its heads by at most one cell, and keeps, pushes a bit onto or pops each stack.✦ A run of a stack machine is within a bound B∈ℕB \in \mathbb{N} if every stack holds at most BB bits in every configuration of the run.✦

Let xi∈X*x_i \in X^* and Si,ai,bi∈ℕS_i, a_i, b_i \in \mathbb{N} be families indexed by i∈Ii \in I. The family bb is computable from aa in space SS, written a⇝Sba \rightsquigarrow_S b with xx understood, if there are a single stack machine, with a register stack and finitely many auxiliary stacks, and a single constant cc such that, for every ii, the machine on the public input xix_i with no argument tape, started with aia_i in binary on the register, the auxiliary stacks empty and its input head at the left endmarker, halts with bib_i in binary on the register, the auxiliary stacks empty and its input head back at the left endmarker, in a run within c(Si+1)c(S_i + 1).✦ A family (vi)(v_i) of elements of a finite set is computable from aa in space SS if a⇝S(⌜vi⌝)a \rightsquigarrow_S (\ulcorner v_i \urcorner).✦ A family (fi)(f_i) is linear in S+1S + 1 if fi≤c(Si+1)f_i \le c(S_i + 1) for one constant cc and every ii.✦

The Claim

Theorem 1 (One-tape simulation in two-fifths-power space). Let MM be a one-tape machine with read-only heads over an input alphabet XX, and let AA be an accessor for MM.

(a) If XX is finite and p,q≥1p, q \ge 1 are reals, there are a Turing machine NN with one argument tape, a number e∈ℕe \in \mathbb{N} and a real c>0c > 0 such that, for every input x∈X*x \in X^* and every T≥2T \ge 2 for which (x,T)(x, T) satisfies the access condition, N(x;T)⇓soutM(x,T),s=cT2/5(Log⁡T)e.N(x; T) \Downarrow_s \mathrm{out}_M(x, T), \qquad s = c\,T^{2/5}(\operatorname{Log} T)^e.(6)✦

(b) If XX is finite and p,q≥1p, q \ge 1 are reals, there are a Turing machine NN with no argument tape, a number e∈ℕe \in \mathbb{N} and a real c>0c > 0 such that, for every input x∈X*x \in X^* for which (x,T)(x, T) satisfies the access condition at every T≥2T \ge 2, and every time tt by which MM has halted on xx, N(x)⇓soutM(x,t),s=c(t+2)2/5(Log⁡t)e.N(x) \Downarrow_s \mathrm{out}_M(x, t), \qquad s = c\,(t + 2)^{2/5}(\operatorname{Log} t)^e.(7)✦

(c) If p≥1p \ge 1 and qq are reals, there are d,c∈ℕd, c \in \mathbb{N} such that, for every input x∈X*x \in X^* and every TT for which (x,T)(x, T) satisfies the access condition, every tag hh and every ℓ∈[−T,T]\ell \in [-T, T], A(x;T,⌜h⌝,[ℓ<0],|ℓ|)⇓c(Bd(T)+1)σx(h,ℓ).A(x; T, \ulcorner h \urcorner, [\ell < 0], |\ell|) \Downarrow_{c(B_d(T) + 1)} \sigma_x(h, \ell).(8)✦

(d) Let d∈ℕd \in \mathbb{N}, and let xi∈X*x_i \in X^* and Si,ai,Ti∈ℕS_i, a_i, T_i \in \mathbb{N} be families indexed by i∈Ii \in I such that a⇝STa \rightsquigarrow_S T, the family (Bd(Ti))(B_d(T_i)) is linear in S+1S + 1, and, for one constant BB and every ii, the accessor AA serves xix_i at cap TiT_i within B(Si+1)B(S_i + 1) work bits. Then a⇝S(outM(xi,Ti))i.a \rightsquigarrow_S \bigl(\mathrm{out}_M(x_i, T_i)\bigr)_i.(9)✦

(e) Let d,c∈ℕd, c \in \mathbb{N}, and let xi∈X*x_i \in X^* and ti∈ℕt_i \in \mathbb{N} be families indexed by i∈Ii \in I such that, for every ii, MM has halted on xix_i by time tit_i and AA serves xix_i at every cap T≥2T \ge 2 within c(Bd(T)+1)c(B_d(T) + 1) work bits. Then, with 00 the constant family, 0⇝S(outM(xi,ti))i,Si=Bd(ti+2).0 \rightsquigarrow_S \bigl(\mathrm{out}_M(x_i, t_i)\bigr)_i, \qquad S_i = B_d(t_i + 2).(10)✦

In the paper, the result reads: for a deterministic machine with one writable tape and head, a fixed number of read-only input heads, unit movement and fixed origins for all heads, symbol functions that do not depend on the cap (the sensor σ\sigma here) and a fixed accessor, the finite-control and halting outcome by time TT can be computed deterministically in Õ(T2/5)\tilde O(T^{2/5}) work bits, not counting storage for the read-only input, for every public input xx and supplied binary cap T≥2T \ge 2 for which the access condition holds, with unrestricted simulation time and without materializing the final writable tape; and if the access condition holds for (x,T)(x, T) at every T≥2T \ge 2 and the machine halts on xx after tt steps, its outcome can be computed with no running time supplied in Õ((t+2)2/5)\tilde O((t + 2)^{2/5}) work bits.

What Is Checked

The statements (6) to (10) are made over the one-tape machine MM with its sensor σ\sigma and outcome outM\mathrm{out}_M, the accessor AA and the access condition, the work bits of a Turing machine counted over a window, computability in space SS by a stack machine with a register, and the allowance BdB_d.