An Improved Proof of the Rabin-Harmanis-Stearns Conjecture
We offer an improved presentation of Aanderaa's constructive proof of the Rabin-Hartmanis-Stearns conjecture: For all k≥2, there exists a language Lk such that Lk can be recoginzed by a k-worktape real time Turing machine but cannot be recognized by any (k-1)-worktape real time Turing machine....
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148951 |
| _version_ | 1811094015527878656 |
|---|---|
| author | Perry, Harold M. |
| author_facet | Perry, Harold M. |
| author_sort | Perry, Harold M. |
| collection | MIT |
| description | We offer an improved presentation of Aanderaa's constructive proof of the Rabin-Hartmanis-Stearns conjecture: For all k≥2, there exists a language Lk such that Lk can be recoginzed by a k-worktape real time Turing machine but cannot be recognized by any (k-1)-worktape real time Turing machine. |
| first_indexed | 2024-09-23T15:54:11Z |
| id | mit-1721.1/148951 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:54:11Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1489512023-03-30T03:10:01Z An Improved Proof of the Rabin-Harmanis-Stearns Conjecture Perry, Harold M. We offer an improved presentation of Aanderaa's constructive proof of the Rabin-Hartmanis-Stearns conjecture: For all k≥2, there exists a language Lk such that Lk can be recoginzed by a k-worktape real time Turing machine but cannot be recognized by any (k-1)-worktape real time Turing machine. 2023-03-29T14:12:17Z 2023-03-29T14:12:17Z 1979-01 https://hdl.handle.net/1721.1/148951 4637436 MIT-LCS-TM-123 application/pdf |
| spellingShingle | Perry, Harold M. An Improved Proof of the Rabin-Harmanis-Stearns Conjecture |
| title | An Improved Proof of the Rabin-Harmanis-Stearns Conjecture |
| title_full | An Improved Proof of the Rabin-Harmanis-Stearns Conjecture |
| title_fullStr | An Improved Proof of the Rabin-Harmanis-Stearns Conjecture |
| title_full_unstemmed | An Improved Proof of the Rabin-Harmanis-Stearns Conjecture |
| title_short | An Improved Proof of the Rabin-Harmanis-Stearns Conjecture |
| title_sort | improved proof of the rabin harmanis stearns conjecture |
| url | https://hdl.handle.net/1721.1/148951 |
| work_keys_str_mv | AT perryharoldm animprovedproofoftherabinharmanisstearnsconjecture AT perryharoldm improvedproofoftherabinharmanisstearnsconjecture |