An Operator Embedding Theorem for Complexity Classes of Recursive Functions
Let F (t) be the set of functions computable by some machine using no more than t(x) machine steps on all but finitely many arguments x. If we order the - classes under set inclusion as t varies over the recursive functions, then it is natural to ask how rich a structure is obtained. We show that th...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148861 |
| _version_ | 1811098197950464000 |
|---|---|
| author | Moll, Robert |
| author_facet | Moll, Robert |
| author_sort | Moll, Robert |
| collection | MIT |
| description | Let F (t) be the set of functions computable by some machine using no more than t(x) machine steps on all but finitely many arguments x. If we order the - classes under set inclusion as t varies over the recursive functions, then it is natural to ask how rich a structure is obtained. We show that this structure is very rich indeed. If R is any countable partial order and F is any total effective operator, then we show that there is a recursively enumerable sequence of... |
| first_indexed | 2024-09-23T17:11:26Z |
| id | mit-1721.1/148861 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T17:11:26Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1488612023-03-30T03:00:58Z An Operator Embedding Theorem for Complexity Classes of Recursive Functions Moll, Robert Let F (t) be the set of functions computable by some machine using no more than t(x) machine steps on all but finitely many arguments x. If we order the - classes under set inclusion as t varies over the recursive functions, then it is natural to ask how rich a structure is obtained. We show that this structure is very rich indeed. If R is any countable partial order and F is any total effective operator, then we show that there is a recursively enumerable sequence of... 2023-03-29T14:03:18Z 2023-03-29T14:03:18Z 1973-05 https://hdl.handle.net/1721.1/148861 09618696 MIT-LCS-TM-032 MAC-TM-032 application/pdf |
| spellingShingle | Moll, Robert An Operator Embedding Theorem for Complexity Classes of Recursive Functions |
| title | An Operator Embedding Theorem for Complexity Classes of Recursive Functions |
| title_full | An Operator Embedding Theorem for Complexity Classes of Recursive Functions |
| title_fullStr | An Operator Embedding Theorem for Complexity Classes of Recursive Functions |
| title_full_unstemmed | An Operator Embedding Theorem for Complexity Classes of Recursive Functions |
| title_short | An Operator Embedding Theorem for Complexity Classes of Recursive Functions |
| title_sort | operator embedding theorem for complexity classes of recursive functions |
| url | https://hdl.handle.net/1721.1/148861 |
| work_keys_str_mv | AT mollrobert anoperatorembeddingtheoremforcomplexityclassesofrecursivefunctions AT mollrobert operatorembeddingtheoremforcomplexityclassesofrecursivefunctions |