One-tape computation in two-fifths-power space

Source and verification

This article explains family 137 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Preliminaries: computation time and workspace

A deterministic Turing machine’s running time counts transitions. Its workspace counts the writable memory simultaneously in use. Recomputing a value can save space even if it greatly increases time. Family 137 asks how much memory is necessary to recover the outcome of a computation that originally runs for at most $T$ steps.

The relevant machine has one writable tape, a finite alphabet, and one head moving by at most one cell per transition. It may also have a fixed number of read-only heads with unit-speed motion. The simulator receives an ordinary endmarked read-only input and a binary cap $T\ge 2$. Its requested output is the finite-control state and halt/timeout outcome at that cap. It is not required to retain the entire final tape.

The space measurement is in work bits, excluding the simulator’s read-only input. Write $\tilde{O}(f(T))$ for $f(T)$ times a fixed power of $\log (T+2)$. Graduate familiarity with algorithms, recursion, and asymptotic estimates is sufficient for the main accounting argument below.

🏷️ The public-symbol access condition

Read-only data need an explicit access model. The manuscript fixes cap-independent initial-symbol functions: the same input and tape coordinate mean the same initial symbol in every simulation. A fixed accessor must recover these symbols at every coordinate $|q|\le T$ using polylogarithmic workspace.

The condition includes coordinates reached by speculative local replays, not only those visited by the actual computation. Otherwise a simulation could hide a difficult computation inside a supposedly free tape lookup. Ordinary input access by rescanning satisfies the condition. If several heads read the same tape, their symbol functions must describe consistent underlying contents.

Manuscript result

For each fixed machine and fixed accessor satisfying this condition at $(x,T)$, its capped outcome can be computed deterministically in $\tilde{O}(T^{2/5})$ work bits. If the machine halts after $t$ steps and the access condition holds at every cap, the uncapped outcome can be computed in $\tilde{O}((t+2{)}^{2/5})$ work bits. (OpenAI, 2026)

The theorem supplies no useful bound on the simulator’s running time. The fixed-machine constants and the logarithmic losses are part of the statement. In particular, it implies $O(T^{\alpha })$ space for each fixed $\alpha >2/5$, not a logarithm-free $O(T^{2/5})$ bound.

The one-writable-tape restriction is substantive. Additional read-only heads fit the model; additional independently writable tapes do not inherit this exponent from the theorem.

🏷️ Shifted blocks and local replay

Partition the tape into blocks of width $b$, allowing $b$ different shifts of the block boundaries. Any one head move crosses a boundary for at most one shift. Averaging over shifts therefore gives a partition with $O(1+T/b)$ visits to blocks.

A visit carries two kinds of information. The block itself contains $b$ tape symbols. Its controller consists of the finite state, head positions, clock, and relevant flags, using $O(\log (T+2))$ bits because the machine is fixed.

For a proposed controller transcript, one can check a particular block’s behavior by replaying visits to it from the appropriate initial block contents. This uses one block and the proposed controller data. It does not require a simultaneous materialization of all tape blocks.

The difficulty is obtaining a consistent transcript without saving the entire history. Guessing here is part of a deterministic enumeration: candidates are tested and combined by an exact evaluation procedure. It is not nondeterministic acceptance, and a candidate’s existence is not treated as a free oracle.

🏷️ Epochs, rounds, and the retained-data invariant

Choose $b=k^2$ up to harmless rounding. Group $b$ block visits into an epoch, and group $k$ visits into a round. Thus an epoch has $k$ rounds. The number of epochs has order

$$E=O(1+T/b^2).$$

An epoch’s block data or full controller history fits in $\tilde{O}(b)$ bits. A round guess occupies only $\tilde{O}(k)$ bits. But a recursive algorithm could still fail by retaining too many guesses or too many full words on its stack.

The manuscript organizes dependencies into words representing epoch-start blocks and partial epoch histories. A history depends on the preceding history in the same epoch and on selected epoch-start blocks. A start-block word, in turn, refers only to the previous epoch.

Retained-guess invariant

Along any active dependency path, at most one costly round guess is retained for each epoch. A call that retains such a guess enters an epoch-start block, whose next dependencies belong to an earlier epoch.

Traversing an ordinary preceding-history edge costs only a small suspended frame. Traversing the history-to-block edge costs the retained round guess. There are at most $k$ ordinary history edges and one costly edge per epoch. Up to logarithmic factors, the total active path weight is therefore $Ek$.

The crucial detail is that a round guess is not retained across the recursive call for the preceding history. It is retained across the block call that drops the epoch index. Retaining it across both kinds of calls would invalidate this accounting.

🏷️ Evaluation with a reusable register pool

The dependency graph can have enormous recomputation cost. Its identifiers and local navigation nevertheless require only logarithmic storage; the graph is not stored explicitly.

The evaluation lemma associates a maximum active path weight $W$ to a word of width $d$. It bounds space by

$$O((d+W+1)\mathrm{polylog}T).$$

Its strength is a reusable-register contract. A call adds a specified multiple of a word’s encoded value to a selected register and restores all other registers. This must work from arbitrary initial register contents. A procedure requiring every temporary register to start at zero could not safely borrow a caller’s partially filled register.

The construction implements the contract using polynomial interpolation over a finite field. At a high level, it adds a child value to a register, evaluates a local expression, and subtracts the child value again. Interpolation isolates the required coefficient while canceling the unknown baseline contents. Recursive calls therefore share a constant-size pool instead of allocating a new full vector at every depth.

This paragraph uses the interpolation lemma as a computational interface; no background development of abstract algebra is needed. What matters for the space claim is that field elements, interpolation counters, local lookups, suspended scalars, and navigation data are all counted. The local lookup procedures themselves make no recursive word-evaluation calls.

For the tape simulation the ordinary dependencies have fan-in at most two, and three vector registers suffice. The word-width contribution includes reusable local scratch; the path-weight contribution includes retained guesses. Sequential forward and reverse calls reuse the same space.

🏷️ Deriving the exponent

The resulting estimate is

$$\begin{array}{rl}S(T,b)& =\tilde{O}(b+(1+T/b^2)\sqrt{b})\\ & =\tilde{O}(b+\sqrt{b}+T/b^{3/2}).\end{array}$$

The first term stores a block or an epoch history. The last term pays for active round guesses across epochs. Balance the two dominant contributions:

$$\begin{array}{rl}b& =T/b^{3/2},\\ b^{5/2}& =T,\\ b& =T^{2/5}.\end{array}$$

Then $T/b^{3/2}=T^{2/5}$ and the remaining $\sqrt{b}$ term is smaller. Trying the finitely many shifted partitions sequentially reuses the same storage; at least one partition has the required visit bound.

One can also let block width $B$, epoch length $L$, and round length $q$ vary separately. Ignoring logarithms, the two stack contributions are

$$\frac{T}{Bq}+\frac{Tq}{BL}.$$

Their minimum occurs at $q\asymp \sqrt{L}$. If $B,L\le S$, the minimized expression is at least a constant times $T/S^{3/2}$, leading again to the exponent $2/5$ when balanced against storage $S$.

This calculation diagnoses the stated accounting scheme. It is not a lower bound for all possible simulation methods, nor does it prove the exponent optimal.

🏷️ Unknown running time and scope

For a computation that eventually halts, try caps $2,4,8,\dots$, discard workspace after every timeout, and return only on a genuine halt. The first sufficient cap is at most $2\max (t,2)$, so its space bound controls the entire sequence. This argument needs the access condition at every cap and the same initial-symbol functions throughout.

A designated bit of a sequential write-only output can also be monitored by adding its index, a counter, and the monitored bit to the controller. That costs logarithmic extra storage. It does not require storing the whole output stream.

The result illustrates a general proof obligation in space-efficient recursion: identify what is simultaneously alive, not merely the size of one subproblem. Here the saved information has a weighted dependency-path bound, and the register implementation realizes that bound without hidden copies.

Logspace derandomization studies another setting where the memory model is central. Subset Sum time and space gives a complementary example in which regeneration must preserve a specified time budget as well as a memory bound.

🏷️ Key steps and proof outlines

Homogenization makes unknown register contents removable

The reusable-register lemma rests on an exact coefficient identity. Encode a Boolean word $u\in \{0,1{\}}^d$ by $\bar{u}=(u,1)$. For a vector $z=(z_1,\dots ,z_d,z_{\ast })$ over the finite field used by the evaluator, define

$$B_u(z)=\prod _{j:u_j=1}{z}_j\prod _{j:u_j=0}(z_{\ast }-z_j).$$

At an encoded Boolean word $\bar{v}$, this is one if $u=v$ and zero otherwise. Therefore a total Boolean lookup $f$ has an extension $\tilde{f}(z)={\sum }_{u}f(u)B_u(z)$ agreeing with $f$ on Boolean encodings and homogeneous of degree $d$. Multiple word inputs use a separate copy of this basis for each input.

Homogeneity is essential. The constant-one lookup extends to $z_{\ast }^d$, not to the literal constant one. Shifting a borrowed register may make its last coordinate zero, so arguments valid only in the affine slice $z_{\ast }=1$ would not support arbitrary register contents. The paper’s “Evaluation along weighted paths” section keeps the homogeneous extension even for predicates that happen to be constant on some semantic inputs. (OpenAI, 2026)

Top coefficients erase the borrowed baseline

Choose $L+1$ distinct field elements $S_L$ and weights

$${\omega }_L(s)={\left(\prod _{u\in S_L\setminus \{s\}}(s-u)\right)}^{-1}.$$

Lagrange interpolation gives $[X^L]p(X)={\sum }_s{\omega }_L(s)p(s)$ for every polynomial of degree at most $L$. If $Q$ is homogeneous of degree $L$, substitution gives the stronger operational identity

$$\sum _{s\in S_L}{\omega }_L(s)Q(a+sv)=Q(v)$$

for arbitrary baseline $a$. Each degree-$L$ monomial contributes its value at $v$ to the top coefficient; all terms involving $a$ have lower degree and disappear. The field has more than $L$ elements, so the denominators are nonzero. No division by a factorial is used, which matters because the construction works in characteristic two.

A recursive call can consequently add $sv$ to a borrowed register containing $a$, evaluate a local polynomial there, and subtract $sv$. Summing with these weights recovers a function of the semantic value $v$ while restoring $a$. The method may enumerate exponentially many Boolean assignments to evaluate a lookup, but it stores only the current assignment, field scalars, and counters. The theorem permits this large running time.

The loop order determines the path weights

At a history vertex, let $H$ be the preceding history, $A_1,\dots ,A_N$ the required block words, and $Y\in \{0,1{\}}^g$ a round guess. The semantic identity sums the guessed output $G_Y(H)$ times all consistency predicates $P_{Y,i}(H,A_i)$. Homogeneous extension gives degree $(N+1)d$ in the history argument and degree $d$ in each block argument.

The evaluator first shifts the history register, before entering the coordinate or guess loops. Inside those loops it interpolates one block argument at a time, multiplies the resulting scalar into an accumulator, and discards that factor. After all coordinates and guesses are finished, it unshifts the history. Thus a recursive history call suspends only small scalar bookkeeping; a block call suspends the $g$-bit guess. This realizes edge weights one and $g+1$, respectively, rather than charging $g$ on both kinds of edge.

For tape simulation, a costly block call decreases the epoch index. There is therefore at most one retained round guess per epoch along an active path. The ordinary history edges within an epoch cost at most the number of rounds. With $b=k^2$ and $E=O(1+T/b^2)$ epochs, the path weight is $O(Ek)$ up to logarithmic factors. A constant pool of vector registers contributes the separate $b$ term, yielding $\tilde{O}(b+T/b^{3/2})$.

The recursive contract quantifies over every initial assignment to the entire register pool. A child may borrow the caller’s partially accumulated output, but must restore it before returning. This stronger statement is exactly what permits three registers to serve an arbitrarily deep computation. The exponent $2/5$ follows only after this implementation and retained-data analysis justify the space expression being balanced.

🏷️ Manuscripts and verification scope

• Simulating One-Tape Time in Two-Fifths-Power Space — pinned manuscript and companion source.

No family scope page was present at lean/docs/137.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Simulating One-Tape Time in Two-Fifths-Power Space.