|
One-tape time simulation in two-fifths-power space
at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages
LOADING...
0%
thinking... about 3 hours remaining
GAME #137
One-tape time simulation in two-fifths-power space
1 level of pure algorithms, speed!
PLAY
LEAN
VERIFIED
If this game doesn't work on your computer, go here for help. (Lean version available!)expertly designed by an internal OpenAI model
| >>> How to Play <<< |
| One-tape time simulation in two-fifths-power space. Determines the halting and finite-control outcome of a fixed deterministic one-writable-tape machine up to time T using $O(T^{2/5}\log^C(T+2))$ 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. |
| >>> Level Select <<< |
|
We show that a fixed deterministic Turing machine with one writable tape and head can be simulated in $O(T^{2/5}\mathop{\mathrm{polylog}}\nolimits (T+2))$ 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.
|
|