{"id":"openai-math/Simulating-One-Tape-Time-in-Two-Fifths-Power-Space","pdf":"https://github.com/openai/math/blob/main/preprints/Simulating-One-Tape-Time-in-Two-Fifths-Power-Space-September-25-2026/article.pdf","url":"https://github.com/openai/math/tree/main/preprints/Simulating-One-Tape-Time-in-Two-Fifths-Power-Space-September-25-2026","tags":["computational-complexity","turing-machines","space-complexity","simulation"],"score":0,"title":"Simulating One-Tape Time in Two-Fifths-Power Space","domain":"Theoretical computer science","family":"137","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":true,"family_title":"One-tape time simulation in two-fifths-power space"}