Browse › Theoretical computer science › 137 One-tape time simulation in two-fifths-power space
Simulating One-Tape Time in Two-Fifths-Power Space
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We show that a fixed deterministic Turing machine with one writable tape and head can be simulated in $O(T^{2/5}\mathop{\mathrm{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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Lean scope notes for family 137: One-tape time simulation in two-fifths-power space (lean/docs/137.md, release of 6 October 2026). Describes the scope of the Lean formalization of the capped $\widetilde O(T^{2/5})$ and uncapped $\widetilde O((t+2)^{2/5})$ simulators under the stated access assumptions, excluding general multitape simulation, hierarchy consequences, and bounded-space-halting results. [AI-generated per source]
- OpenAI math release, OneTapeSpace.lean (Comparator challenge statement) (openai/math, commit fd4aeeb). The comparator file states the two main results,
Fifths.Single.cappedandFifths.Single.unknown, for a one-writable-tape machine under an access hypothesis, with a space bound of the form $c\,T^{2/5}(\log(T+2))^e$.
Possibly relevant literature (found by the agent, not checked)
- Hopcroft, Ullman, Relations between time and tape complexities (J. ACM 15(3):414–427, 1968). The paper credits the classical $O(\sqrt t)$ one-read/write-tape simulation, which Theorem 1 improves, to Hopcroft and Ullman only through Williams's account; this appears to be the original source and is not in the paper's bibliography.
- Y. Shalunov, Improved Bounds on the Space Complexity of Circuit Evaluation (arXiv:2504.20950, v1 April 2025, v2 June 2025). Reduces circuit evaluation directly to Cook–Mertz tree evaluation and recovers a $\sqrt t\log t$-space simulation of time-$t$ machines, which may be relevant to the paper's separate $\widetilde O(\sqrt T)$ multitape simulation.
Digests and expositions
- Latent Seminar, One-tape computation in two-fifths-power space (Latent Seminar, 2026-10-07). Explains the block/epoch construction, retained-guess accounting, reusable-register interpolation, and the resulting two-fifths exponent; the page states that it has not independently verified the complete proof.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 137
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Simulating-One-Tape-Time-in-Two-Fifths-Power-Space-September-25-2026,
author = {{OpenAI}},
title = {{Simulating One-Tape Time in Two-Fifths-Power Space}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Simulating-One-Tape-Time-in-Two-Fifths-Power-Space-September-25-2026/article.pdf}{OAI:Simulating-One-Tape-Time-in-Two-Fifths-Power-Space-September-25-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/137.md. The Lean statements have not been checked by people against the paper's claims.
Family 137: One-tape time simulation in two-fifths-power space
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.
This is the only paper in this family.