1 · The essentials
A computer following a fixed set of rules may take many steps while changing symbols on a single tape. This result asks how much working memory another computer needs to determine whether that process has stopped by a chosen step limit, and what internal state it reaches. The manuscript gives a way to do this with memory growing roughly as the step limit raised to the two-fifths power, with an additional factor involving logarithms. That improves the square-root power described in the source for this one-tape setting. The saving concerns memory only: the simulation has no restriction on how long it takes. The result requires that starting symbols can be retrieved using little memory, and it allows a fixed number of extra heads that can read input but cannot change it. The main result has a Lean formalization.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine checking a clerk who follows fixed instructions while reading and editing one long strip of paper, moving at most one position at a time. The simulator is like an auditor who determines the clerk’s status by a deadline using a smaller scratchpad, but may spend unrestricted time doing the audit. The image does not explain how the memory saving is achieved.
Why it matters
The result improves the space exponent from one-half to two-fifths for the stated one-writable-tape model. The abstract describes this as answering Williams’s question for that model. It separates the memory needed to determine a computation’s outcome from the time spent carrying out the simulation.
2 · Going further
Fix a deterministic Turing machine with one writable tape and one head on that tape, and supply a binary time cap . The task is to compute its finite-control and halting outcome by time , not to report the entire tape contents. The stated workspace bound is bits, also written in the repository summary as .
The model permits a fixed number of read-only input heads, and heads move at most one cell per step. Initial contents are independent of . A fixed accessor must supply every initial writable-tape symbol and read-only input symbol within distance of the relevant head origin using polylogarithmic space. The simulator’s running time is unrestricted.
The abstract identifies the improvement over the square-root space exponent and describes it as answering Williams’s question for this model. It does not describe the construction or the main steps of the argument, so no argument mechanism can be extracted from the supplied text. Only the main manuscript is supplied; no companion-manuscript relationship is specified. The main result is marked as Lean-formalized, but the source provides no further breakdown of the formalization’s scope.
Useful notions
- Deterministic Turing machines
- Time caps and halting
- Workspace measured in bits
- Big-O notation
- Powers and logarithmic factors
What was known before / what is new
Before
The source identifies a square-root space exponent as the benchmark improved by this result for one-tape machines. It also refers to Williams’s question, without supplying its historical details or a separate statement beyond this model-specific context.
New
The main manuscript gives a simulation using workspace bits to determine the finite-control and halting outcome by time . It accommodates a fixed number of read-only input heads under the stated symbol-access assumptions. The main result has a Lean formalization.
Limits and assumptions
The result concerns a fixed deterministic machine with one writable tape and head, with heads moving at most one cell per step, and at most a fixed number of read-only input heads. It assumes a binary cap , initial contents independent of , and a fixed polylogarithmic-space accessor for the relevant starting symbols. The output is the finite-control and halting outcome by the cap; the source does not state a guarantee of reconstructing the full final tape. Simulation time is unrestricted. The main result is Lean-formalized, but no detailed formalization scope is provided. The supplied text identifies no remaining open problem and makes no corresponding claim for more general machine models.
Mini glossary
- Deterministic Turing machine —
- A tape-based computation model whose rules determine its next action from its current state and the symbols it reads.
- Finite control —
- The machine’s internal state, as distinct from its tape contents.
- Workspace —
- The working memory used by the simulator, measured here in bits.
- Polylogarithmic space —
- A memory bound that grows no faster than a fixed power of a logarithm of the relevant size parameter.
- Accessor —
- The fixed procedure that retrieves the required initial tape and input symbols within the stated memory bound.
Keywords : One-tape simulation · Space complexity · Lean formalization
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Determines the halting and finite-control outcome of a fixed deterministic one-writable-tape machine up to time T using 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.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Simulating One-Tape Time in Two-Fifths-Power Space
25/09/2026We show that a fixed deterministic Turing machine with one writable tape and head can be simulated in 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.