Space-Bounded Simulation of Multitape Turing Machines
| dc.contributor.author | Adleman, Leonard M. | en_US |
| dc.contributor.author | Loui, Michael C. | en_US |
| dc.date.accessioned | 2023-03-29T14:15:25Z | |
| dc.date.available | 2023-03-29T14:15:25Z | |
| dc.date.issued | 1980-01 | |
| dc.identifier.uri | https://hdl.handle.net/1721.1/148975 | |
| dc.description.abstract | 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. | en_US |
| dc.relation.ispartofseries | MIT-LCS-TM-148 | |
| dc.title | Space-Bounded Simulation of Multitape Turing Machines | en_US |
| dc.identifier.oclc | 6312164 |
