One-tape computation: trading unrestricted time for two-fifths-power space

← All digests

Family 137 · Theoretical computer science
Importance 2/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

A computation that runs for $T$ steps can visit and modify as many as $T$ tape cells. To reproduce its final answer, must a simulator remember all those cells at once?

If time is unlimited, the simulator can recompute information instead of retaining it. This creates a time–space tradeoff: repeated reconstruction may save memory at the cost of an enormous increase in running time.

For deterministic machines with one writable tape, a classical simulation uses roughly the square root of the original time as space. The manuscript in this family claims a smaller exponent:

$$O\!\left(T^{2/5}\operatorname{polylog}(T+2)\right)$$

work-space bits. Here $\operatorname{polylog}$ means a fixed power of a logarithm.

The machine model and output are essential. The source has one writable tape and one writable head moving locally. A fixed number of additional read-only heads are allowed. The simulator reports the finite-control and halting outcome by the supplied time cap; it need not materialize the entire final tape. No useful simulation-time bound is asserted.

2. Background and essential definitions

A deterministic Turing machine has a finite control state, a finite tape alphabet, and a head that reads a symbol, writes a symbol, changes state, and moves locally. In this theorem the writable tape is indexed by integers and its head moves at most one cell per step.

The machine itself is fixed. The varying inputs are a public input $x$ and a binary-encoded time cap $T\ge2$. Halting states are made absorbing, so asking for the state after $T$ steps also records whether the machine halted earlier and what its outcome was.

Work space counts bits used by the simulator, excluding the read-only input. The simulator may rescan that input and recompute intermediate objects. Its time can be much larger than $T$.

The theorem includes a precise access condition for initial tape symbols. A fixed procedure must supply the symbol at any displacement $|q|\le T$ from a relevant head origin using polylogarithmic space. The underlying initial symbol functions are fixed independently of the cap. This rules out hiding a cap-dependent computation inside the initial tape description.

Ordinary explicit inputs satisfy the access condition: keep a counter and rescan the input to the requested position or an endmarker. The condition also permits some implicit encodings, provided they admit the same small-space access throughout the entire numerical range that local simulations may inspect.

A bound $\widetilde O(T^{2/5})$ abbreviates $T^{2/5}$ times logarithmic factors. It implies $O(T^{2/5+\eta})$ for every fixed $\eta>0$, but not a log-free $O(T^{2/5})$ endpoint.

3. Development history and previous partial results

Classical work on tape bounds and time–space tradeoffs asked how a long sequential computation could be reconstructed with less stored information. Paterson’s 1972 tape-bound paper, Ibarra and Moran’s single-tape tradeoffs, and Liśkiewicz and Loryś’s 1990 simulations form part of this background.

Williams’s account attributes the classical one-read/write-tape square-root-space simulation to Hopcroft and Ullman. More recently, Williams proved a broader multitape time-to-space simulation using $O(\sqrt{t\log t})$ space under the stated time assumptions. His work asks whether the one-tape square-root exponent can be reduced by a fixed positive amount.

A key ingredient is the Cook–Mertz tree-evaluation algorithm. Its use of shared storage can avoid paying the full size of a value at every recursive level. Goldreich’s exposition explains the role of interpolation and a global register pool.

The present manuscript adapts this kind of recomputation to the special geometry of one writable head. Its proposed gain comes from organizing visits to tape blocks into epochs and arranging that large guesses are retained only on selected recursive dependencies.

The claim is therefore more specific than a new general multitape simulation. It answers the one-tape exponent question in the supplied-cap and symbol-access model, while separately retaining a square-root-type result for a fixed number of writable tapes.

4. What the new manuscripts claim

Fix a deterministic machine with one writable tape and head, a fixed number of read-only heads, fixed head origins, local movement, and a fixed initial-symbol accessor satisfying the stated polylogarithmic-space condition. For every allowed $(x,T)$, the manuscript claims a deterministic simulation of the finite-control and halting outcome by time $T$ using

$$\widetilde O(T^{2/5})$$

work-space bits.

Constants may depend on the fixed machine and accessor but not on the varying input or cap. The bound includes the simulator’s working storage, while the public read-only input itself is excluded. The full final writable tape is not required as output.

If the access condition holds at every cap and the original machine halts after $t$ steps, no running-time bound need be supplied in advance. Trying successively larger caps gives the outcome in $\widetilde O((t+2)^{2/5})$ space.

For every fixed $0<\delta<1/10$, the logarithmic factors can be absorbed to give $O(T^{1/2-\delta})$. This is the claimed fixed improvement over the square-root exponent. The theorem does not assert the endpoint $\delta=1/10$ without logarithmic losses.

The manuscript also discusses space-hierarchy consequences for suitable decision languages in the one-writable-head model. Those are class nonmembership statements, not lower bounds at every input length, and do not extend to arbitrary multitape or random-access machines. The core theorem is the simulation with its explicit access and output conventions.

5. Why the advance matters

Provisional importance: 2/5. The result would improve a longstanding space exponent in a fundamental but restricted computation model. It shows how local tape motion can support more aggressive recomputation than the standard square-root organization.

The exponent reduction is mathematically meaningful even with logarithmic factors. For sufficiently large caps, a fixed power saving dominates any fixed logarithmic overhead. The theorem also handles ordinary explicit input access and additional read-only heads, making the model broader than a completely isolated blank-tape computation.

The rating reflects the specialization of the conclusion. Simulation time is unrestricted, there is only one writable head, and the output is a finite-control outcome. These restrictions limit direct algorithmic applications compared with a fast general-purpose simulation or a bound for arbitrary writable tapes.

The main methodological interest is the accounting of suspended information along recursive calls. Reducing memory requires controlling not only the size of each local object but also which objects must remain live together while deeper computations run.

6. The main idea

Cut the tape where the head crosses infrequently

Partition the writable tape into blocks of width $b$, allowing the partition’s offset to vary. Averaging over offsets shows that one choice has only $O(T/b)$ block visits. The head moves one cell at a time, so it cannot cross many block boundaries without spending steps.

During one visit, a long block of tape interacts with the rest of the computation through a short controller description: machine state, head positions, elapsed time, and terminal flags. Once a candidate controller transcript is fixed, all visits to an individual block can be replayed from that block’s initial contents.

This factors consistency over blocks. Rather than store the whole tape, the simulator can enumerate proposed transcripts and check their local consequences, using recomputation whenever old block contents are needed.

Separate epochs from smaller rounds

Group about $b$ block visits into an epoch. Within an epoch, append controller information in rounds of about $\sqrt b$ visits. A block and the relevant history each fit in $\widetilde O(b)$ bits.

A naive recursive evaluation would keep a large round guess on every call stack level. The manuscript instead uses interpolation to evaluate a history update without retaining that guess during calls to the preceding history. The guess is kept only when calling for a block state at the start of an epoch.

That selected call moves immediately to earlier epochs. Consequently a dependency path pays for at most one retained round guess per epoch, rather than once for every step of the history reconstruction.

Borrow registers and restore their contents

The evaluator implements an additive update to one chosen register while restoring every other register, even when the shared pool initially contains arbitrary data. A recursive descendant can therefore borrow registers holding the caller’s inputs or partially accumulated output, provided it restores them before returning.

Finite-field interpolation supplies this controlled evaluation. The fields and local arithmetic can be generated with polylogarithmic space, and the procedure may enumerate large finite sets because time is not the constrained resource.

The claimed space accounting becomes

$$\widetilde O\!\left( b+\left(1+\frac{T}{b^2}\right)\sqrt b \right).$$

The first term pays for local block and history storage. The second pays for retained guesses along the epoch dependencies. Its main contribution is $T/b^{3/2}$. Balancing that with $b$ gives $b^{5/2}$ of order $T$, hence

$$b\asymp T^{2/5}.$$

This calculation explains the exponent once the evaluator and dependency claims are available. It is not a proof that two fifths is optimal for every possible simulation strategy.

7. Scope, limitations, and open questions

The theorem’s unrestricted simulation time is essential to its interpretation. The simulator repeatedly enumerates and reconstructs information. Its own time may be enormous, so the result cannot be iterated as though it were a faster simulation with a new small time cap.

One writable head supplies the block-visit structure. Additional read-only heads are tracked in the short controller, but additional writable tapes change the dependency pattern. The manuscript does not claim the same two-fifths bound for general multitape machines.

The accessor must work at every coordinate within distance $T$ relevant to the capped invocation, including coordinates inspected during proposed local computations. Providing only the symbols visited by the actual unknown run would be a weaker and insufficient interface.

The final tape is not materialized. A user needing every final cell has a different output requirement and may face an output-size cost absent from the stated decision simulation.

The paper explains why adjusting its three scales alone does not lower the exponent further. That observation concerns this construction, not a lower bound on all methods. Better space exponents, useful time–space tradeoffs, and extensions to more writable heads remain distinct questions.

8. Sources and further reading

Williams gives the modern square-root-space result and the one-tape question. Cook–Mertz and Goldreich explain the shared-storage interpolation background. The earlier tape-simulation papers locate the historical tradeoff problem. The source manuscript below specifies the symbol-access interface, weighted dependency evaluator, and two-fifths calculation.

Source manuscripts

• M1. OpenAI, Simulating One-Tape Time in Two-Fifths-Power Space (September 25, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.