Ordinal complexity of recursive definitions (Q1193596): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1084099 |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Stanley S. Wainer / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3773880 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3695270 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rapidly growing Ramsey functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3325707 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nested recursion / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Slow growing versus fast growing / rank | |||
Normal rank |
Revision as of 14:19, 16 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ordinal complexity of recursive definitions |
scientific article |
Statements
Ordinal complexity of recursive definitions (English)
0 references
27 September 1992
0 references
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\).
0 references
subrecursion
0 references
hierarchy
0 references
recursive and iterative definitions of total computable functions
0 references
structured tree-ordinals
0 references
Hardy functionals
0 references
nested recursions
0 references
0 references