OctoInformBeta

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

The simulated machine is a fixed deterministic Turing machine with finitely many states, one writable tape indexed by the integers with one head, and a fixed number of read-only heads, each head starting at a fixed origin and moving by at most one cell per step. A tag names the initial writable tape or one of the read-only heads. For a public input xx, a tag hh and an integer qq, σh(x,q)\sigma_h(x,q) is the symbol at displacement qq from the origin of hh. The outcome at time TT on xx is the state after TT steps together with whether that state is halting. Halting states are absorbing. Work space is the number of bits a machine uses on its work tapes, the read-only tapes that hold xx and any arguments given to the machine in binary not counted. An accessor is a fixed deterministic Turing machine that reads xx and, in binary, a cap TT, a tag hh and a displacement qq. For fixed constants C0,C1≥1C_0,C_1\ge1, the access condition holds for (x,T)(x,T) when, for every tag hh and every integer qq with |q|≤T|q|\le T, the accessor halts with σh(x,q)\sigma_h(x,q) within C0log⁡C1(T+2)C_0\log^{C_1}(T+2) bits of work space. The question is how much work space a deterministic Turing machine needs to compute the outcome at time TT from xx and a binary cap T≥2T\ge2, when its running time is unrestricted.

In Williams’s account, the classical simulation of time tt on one read/write tape in space O(t)O(\sqrt t) is due to Hopcroft and Ullman. Williams proved that deterministic multitape time t(n)≥nt(n)\ge n on inputs of length nn can be simulated in space O(t(n)log⁡t(n))O(\sqrt{t(n)\log t(n)}). His proof rests on the tree-evaluation algorithm of Cook and Mertz. Williams asked whether the square-root space exponent for machines with one tape can be lowered by a fixed positive constant.

The preprint proves that a deterministic Turing machine, given xx and a binary cap T≥2T\ge2, computes the outcome at time TT within O(T2/5log⁡C(T+2))O(T^{2/5}\log^{C}(T+2)) bits of work space for every (x,T)(x,T) satisfying the access condition, its running time unrestricted, where CC and the implied constant depend only on the simulated machine, the accessor, C0C_0 and C1C_1. It proves also that, when the access condition holds for (x,T)(x,T) at every T≥2T\ge2 and the simulated machine halts after tt steps, a deterministic Turing machine given xx alone computes its outcome within O((t+2)2/5log⁡C(t+2))O((t+2)^{2/5}\log^{C}(t+2)) bits of work space. This answers Williams’s question for this model. From these bounds the preprint derives that, for every space-constructible s(n)≥ns(n)\ge n and every fixed 0<ϵ<5/20<\epsilon<5/2, some language decided in space O(s(n))O(s(n)) is decided by no machine of this model in time O(s(n)5/2−ϵ)O(s(n)^{5/2-\epsilon}), a consequence the Lean library does not contain.

The Lean library SpaceSimulation proves both of these space bounds under the same access condition. The results on these pages are the Lean library’s, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every one of them, so the Lean library is the reference. Where the preprint states a result differently, the page gives the Lean library’s statement, with the preprint’s beside it. The preprint is a guide only: it gives the results their order and their names.

The Lean library: SpaceSimulation

SpaceSimulation is a Lean library: 17 items, in four groups. Each has a page written by OctoInform, listed below.

§1. Introduction 3 items
  1. §1 (setting): the simulated machine and its outcome The simulated machine and its outcome at each time. §1
  2. §1 (setting): simulators, space, the accessor and the access condition Simulators, space in work bits and polylogarithmic tape access. §1
  3. Theorem 1 [One-tape simulation in two-fifths-power space] Simulating one-tape machines with accessible symbols in space Õ(T2/5)\tilde O(T^{2/5}). §1
§2. An evaluator with weighted dependency paths 5 items
  1. Lemma 2 [Uniform fields] Prime fields by trial division, with space-bounded sums and products. §2
  2. Lemma 3 [Homogeneous lookup extensions] Homogeneous lookup extensions agree with their tables and are computable. §2
  3. Lemma 4 [Top-coefficient extraction] Weighted sums over a prime field extract top coefficients. §2
  4. §2 (setting): word graphs, factored rules and weighted paths Dependency circuits with factored rules and a coin meter. §2
  5. Lemma 5 [Evaluation along weighted paths] Three registers evaluate a good circuit within its meter. §2
§3. Block visits and epoch transcripts 7 items
  1. §3.1 (setting): controllers, blocks and represented blocks A configuration as a packed controller and its blocks. §3.1
  2. Lemma 6 [A visit accesses one block] Each visit runs the machine inside a single block. §3
  3. Lemma 7 [Local replay] Local block replays certify a controller transcript. §3
  4. §3.2 (setting): epochs, histories and checkpoints The epoch circuit of a tour of block visits. §3.2
  5. Lemma 8 [Factored round rule] Non-base vertices of a tour circuit obey the identity rule. §3
  6. Lemma 9 [Weight of the epoch path] Coins that pay for every step down the epoch circuit. §3
  7. Theorem 1, proof (§3.3): assembly Computing the final controller and reading off the outcome. §3.3
The space calculus (no numbered counterpart in the preprint) 2 items
  1. The indexed space calculus Space bounds certified uniformly by a single stack machine.
  2. Compiling the calculus to Turing machines Stack computations of a label compile to one Turing machine.

No item matches.