Simulating One-Tape Time in Two-Fifths-Power Space
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/Simulating-One-Tape-Time-in-Two-Fifths-Power-Space
curl -X POST /api/v1/records/openai-math/Simulating-One-Tape-Time-in-Two-Fifths-Power-Space/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Simulating-One-Tape-Time-in-Two-Fifths-Power-Space/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'