One-tape time simulation in two-fifths-power space

The explanation

Picture a simple machine that runs for ten billion steps, so T = 10^10. It works on one long strip of cells, called a tape. A head reads and writes one cell, then moves at most one cell left or right. A fixed rule table decides each step. This is a one-tape Turing machine. Now ask a second program, the simulator, to work out how the run ends. The simulator may take as long as it likes. The question is how little memory it needs.

The classical answer is memory of about the square root of the step count. For ten billion steps that is about 100,000 units. This paper brings it down to about the two-fifths power of T. For ten billion steps that is about 10,000, ten times less. The gap widens as T grows. At T = 10^20 it is 10^10 against 10^8, a factor of 100. Both figures leave out a factor that grows like a fixed power of log T. Here log₂ T is about 33, and the paper does not state that powerSource 1. So these numbers show the trend, not exact memory sizes.

The square-root simulation for one-tape machines is old. Williams's account attributes it to Hopcroft and Ullman. In 2025, Ryan Williams showed that any multitape machine running t steps fits in about √(t log t) memory. His proof builds on a 2024 method of Cook and Mertz. That method lets nested calculations share one pool of memory and restore it afterward. In his full paper, Williams asked whether the one-tape square-root exponent could drop by a fixed amount. This paper proves that it can. Any exponent above 2/5 works, and 2/5 sits a full tenth below 1/2Source 2.

The first idea is to cut the tape into blocks of equal width b. Then shift the cut points and count how often the head crosses a block edge. Each head move crosses an edge for exactly one of the b possible shifts. So across all b shifts there are at most T crossings in total. Some shift therefore has at most T/b crossingsSource 3. With T = 10^10 and b = 10,000, that is at most a million. Each stay inside one block is a visit. Between visits only a short summary passes along: the state, head positions, elapsed time and end flagsSource 4.

That short summary makes checking cheap. Suppose someone hands over the full list of summaries. Then each block can be replayed on its own, from its starting contentsSource 5. Whether the list is right splits into separate checks, one per block. The hard part is that the simulator must guess these summaries. A nested calculation has to hold its guess while deeper calls run. If every level held one, the memory would pile up. The paper groups b visits into an epoch and guesses them in rounds of √b visitsSource 6. It arranges the calls so any chain of nested calls holds at most one round guess per epochSource 7. In the example, that means rounds of 100 visits and 101 epochs. Balancing block size against these held guesses gives the two-fifths exponentSource 8.

This splitting is also why the result needs a single writable tape. With two writable tapes, one step can depend on two blocks at once, and the checks no longer splitSource 9. For several writable tapes the paper gives only a separate square-root boundSource 10,Source 11. The machine may still have extra heads that only read the inputSource 12. The paper also needs the starting tape contents to be readable with very little memory. Ordinary inputs meet that condition by rescanningSource 13.

The saving is in memory only. The simulator may run far longer than the machine it copies, so this cannot be turned into a speed-upSource 14. No time cap is needed either. The simulator can try caps 2, 4, 8 and so on until the machine actually haltsSource 15. The paper does not claim that two-fifths is the best possible. Its own count shows only that tuning this method's three sizes cannot do betterSource 16.

How sure is this? A computer proof checker called Lean has checked formal versions of both main statements. One has a supplied time cap, and one has an unknown halting time. The multitape comparison and the paper's consequences for time and memory classes are outside that check. No specialist review of the paper has been published.

What it doesn't show. This does not speed up any computation, and it gives no two-fifths bound for machines with several writable tapes.