Space-Bounded Simulation of Multitape Turing Machines
A new proof of a theorem of Hopcroft, Paul, and Valiant is presented: every deterministic multitape Turing machine of time complexity T(n) can be simulated by a deterministic Turing machine of space complexity T(n)/log T(n). The proof includes an overlap argument.
| Үндсэн зохиолчид: | , |
|---|---|
| Хэвлэсэн: |
2023
|
| Онлайн хандалт: | https://hdl.handle.net/1721.1/148975 |