Complexity Classes of Recursive Functions
An honest function is one whose size honestly reflects its computation time. In 1969 Meyer and McCreight proved the "honesty theorem," which says that for every t, the t-computable functions are the same as the t'computable functions for some honest honest t'.
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149418 |
| _version_ | 1811092982701490176 |
|---|---|
| author | Moll, Robert |
| author2 | Meyer, Albert R. |
| author_facet | Meyer, Albert R. Moll, Robert |
| author_sort | Moll, Robert |
| collection | MIT |
| description | An honest function is one whose size honestly reflects its computation time. In 1969 Meyer and McCreight proved the "honesty theorem," which says that for every t, the t-computable functions are the same as the t'computable functions for some honest honest t'. |
| first_indexed | 2024-09-23T15:37:41Z |
| id | mit-1721.1/149418 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:37:41Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1494182023-03-30T03:13:24Z Complexity Classes of Recursive Functions Moll, Robert Meyer, Albert R. An honest function is one whose size honestly reflects its computation time. In 1969 Meyer and McCreight proved the "honesty theorem," which says that for every t, the t-computable functions are the same as the t'computable functions for some honest honest t'. 2023-03-29T14:57:18Z 2023-03-29T14:57:18Z 1973-06 https://hdl.handle.net/1721.1/149418 02338047 MIT-LCS-TR-110 MAC-TR-110 application/pdf |
| spellingShingle | Moll, Robert Complexity Classes of Recursive Functions |
| title | Complexity Classes of Recursive Functions |
| title_full | Complexity Classes of Recursive Functions |
| title_fullStr | Complexity Classes of Recursive Functions |
| title_full_unstemmed | Complexity Classes of Recursive Functions |
| title_short | Complexity Classes of Recursive Functions |
| title_sort | complexity classes of recursive functions |
| url | https://hdl.handle.net/1721.1/149418 |
| work_keys_str_mv | AT mollrobert complexityclassesofrecursivefunctions |