One-tape time simulation in two-fifths-power space

What OpenAI claims

Determines the halting and finite-control outcome of a fixed deterministic one-writable-tape machine up to time T using O(T^2/5 log^C(T+2)) space, improving the square-root exponent. Heads move at most one cell per step; finitely many read-only input heads are allowed. Initial contents are independent of T, and contents and input symbols have polylogarithmic-space access. Simulation time is unrestricted. (Lean)

Paper

1. Simulating One-Tape Time in Two-Fifths-Power Space

   25 September 2026 · Preprint, not peer reviewed · PDF

   We show that a fixed deterministic Turing machine with one writable tape and head can be simulated in O(T^2/5polylog (T+2)) work-space bits when a binary time cap T ≥ 2 is supplied. The simulator computes the finite-control and halting outcome by time T; its running time is unrestricted. The result allows a fixed number of read-only input heads and requires a fixed accessor that supplies every initial writable and read-only symbol within distance T of the relevant head origin in polylogarithmic space. This improves the square-root space exponent for one-tape machines, answering Williams's question for this model.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.