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 |