One-tape time simulation in two-fifths-power space
OpenAI research collection · 1 manuscript · Source checked 2026-10-19
OpenAI's result summary
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.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
Simulating One-Tape Time in Two-Fifths-Power Space
We show that a fixed deterministic Turing machine with one writable tape and head can be simulated in O(T^{2/5}\mathop{polylog}\nolimits (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…
Full source abstract
We show that a fixed deterministic Turing machine with one writable tape and head can be simulated in O(T^{2/5}\mathop{polylog}\nolimits (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.
This PDF is listed in OpenAI's formalization catalogue. See the scope and dependencies before interpreting coverage.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.