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 |