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 , a tag and an integer , is the symbol at displacement from the origin of . The outcome at time on is the state after 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 and any arguments given to the machine in binary not counted. An accessor is a fixed deterministic Turing machine that reads and, in binary, a cap , a tag and a displacement . For fixed constants , the access condition holds for when, for every tag and every integer with , the accessor halts with within bits of work space. The question is how much work space a deterministic Turing machine needs to compute the outcome at time from and a binary cap , when its running time is unrestricted.
In Williams’s account, the classical simulation of time on one read/write tape in space is due to Hopcroft and Ullman. Williams proved that deterministic multitape time on inputs of length can be simulated in space . 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 and a binary cap , computes the outcome at time within bits of work space for every satisfying the access condition, its running time unrestricted, where and the implied constant depend only on the simulated machine, the accessor, and . It proves also that, when the access condition holds for at every and the simulated machine halts after steps, a deterministic Turing machine given alone computes its outcome within bits of work space. This answers Williams’s question for this model. From these bounds the preprint derives that, for every space-constructible and every fixed , some language decided in space is decided by no machine of this model in time , 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.
SpaceSimulation is a Lean library: 17 items, in four groups. Each has a page written by OctoInform, listed below.
No item matches.