Ordinal complexity of recursive definitions
We classify and compare recursive and iterative definitions of total computable functions according to the complexity of the ordinal structures needed to verify termination. The main results are as follows: Let \(A\) be a set of structured tree-ordinals. \(\text{T-WHILE}(A)\) is a set of functions (denoted by programs) built from sequencing, conditionals and terminating while-loops which use tree parameters \(\alpha\in A\). \(\text{HARDY}(A)\) is, by Theorem I, an equivalent formulation, based on a Kleene-style presentation which includes primitive recursion and adds in the set \(H(A)\) of Hardy functionals \(\{H_ \alpha: \alpha\in A\}\). \(\text{REC}(A)\) is a set of functions defined by composition, conditionals and nested recursions which use parameters from \(A\). Theorem II establishes that, provided \(A\) satisfies suitable conditions such as Turing-machine representability and closure under addition and multiplication, \[ \text{T- WHILE}(A)\equiv\text{ELEM}(H(A))\equiv\text{SPACE}(H(A)). \] Theorem III tells us that under somewhat weaker conditions on \(A\), \(\text{REC}(\omega\cdot A)\equiv\text{T-WHILE}(\omega^ A)\), and is a generalization of a theorem of Tait showing nested recursions over a given well-ordering can be compiled to unnested ones but at the cost of an exponential increase in the size of the well-ordering. Some applications of these theorems are given at the end of the paper, for example: \[ \begin{aligned}\text{REC}(\omega\cdot N) & \equiv \text{WHILE}(\omega^ N)\\& \equiv\text{PRIMITIVE RECURSIVE}\\ \text{REC}(E) & \equiv \text{WHILE}(E)\equiv\text{SPACE}(E)\\ &\equiv \text{PROVABLY RECURSIVE in PA},\end{aligned} \] where \(N\) is the set of finite tree-ordinals and \(E\) is the closure of \(N\) under exponentiation. The first author has subsequently shown that under the weaker conditions, \(\text{PROV}(\lvdash^{\omega\cdot A}_{\Sigma^ 0_ 1 C})\equiv\text{REC}(\omega\cdot A)\), where \(\text{PROV}(\lvdash^ A_{\Sigma^ 0_ 1 C})\) is the set of functions which have a totality proof in \(\omega\)-logic with \(\Sigma^ 0_ 1\) cut-rank and ordinal bound in \(A\).
- Recursion on generalized computable ordinals
- Turing complexity of the ordinals
- scientific article; zbMATH DE number 1390019
- Ordinal recursive complexity of unordered data nets
- DEFINABILITY OF RECURSIVELY ENUMERABLE SETS IN ABSTRACT COMPUTATIONAL COMPLEXITY THEORY
- The recursion-theoretic structure of complexity classes
- scientific article; zbMATH DE number 3885307
- scientific article; zbMATH DE number 4108743
- A characterization of the complexity of recursive predicates
- scientific article; zbMATH DE number 4037837
- A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods
- scientific article; zbMATH DE number 3857078 (Why is no real title available?)
- scientific article; zbMATH DE number 3920456 (Why is no real title available?)
- scientific article; zbMATH DE number 4033742 (Why is no real title available?)
- Nested recursion
- Rapidly growing Ramsey functions
- Slow growing versus fast growing
- Ordinal recursive bounds for Higman's theorem
- Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones
- Transfinite induction within Peano arithmetic
- Complexity hierarchies beyond elementary
- Partitioning 𝛼–large sets: Some lower bounds
- Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
- Optimal bounds for ordinal comparison maps
- Walther recursion
- scientific article; zbMATH DE number 218515 (Why is no real title available?)
- From hierarchies to well-foundedness
- scientific article; zbMATH DE number 806754 (Why is no real title available?)
- Accessible Recursive Functions
- A difference in complexity between recursion and tail recursion
- Iterated inductive definitions revisited
- An ordinal calculus for proving termination in term rewriting
- The hierarchy of terminating recursive programs over N
This page was built for publication: Ordinal complexity of recursive definitions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1193596)
