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.
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148975 |
| _version_ | 1826190096716529664 |
|---|---|
| author | Adleman, Leonard M. Loui, Michael C. |
| author_facet | Adleman, Leonard M. Loui, Michael C. |
| author_sort | Adleman, Leonard M. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:34:59Z |
| id | mit-1721.1/148975 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:34:59Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1489752023-03-30T04:20:26Z Space-Bounded Simulation of Multitape Turing Machines Adleman, Leonard M. Loui, Michael C. 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-03-29T14:15:25Z 2023-03-29T14:15:25Z 1980-01 https://hdl.handle.net/1721.1/148975 6312164 MIT-LCS-TM-148 application/pdf |
| spellingShingle | Adleman, Leonard M. Loui, Michael C. Space-Bounded Simulation of Multitape Turing Machines |
| title | Space-Bounded Simulation of Multitape Turing Machines |
| title_full | Space-Bounded Simulation of Multitape Turing Machines |
| title_fullStr | Space-Bounded Simulation of Multitape Turing Machines |
| title_full_unstemmed | Space-Bounded Simulation of Multitape Turing Machines |
| title_short | Space-Bounded Simulation of Multitape Turing Machines |
| title_sort | space bounded simulation of multitape turing machines |
| url | https://hdl.handle.net/1721.1/148975 |
| work_keys_str_mv | AT adlemanleonardm spaceboundedsimulationofmultitapeturingmachines AT louimichaelc spaceboundedsimulationofmultitapeturingmachines |