Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917029513003008 |
|---|---|
| author | Tabatabai, Amirhossein Akbar Greati, Vitor Ramanayake, Revantha |
| author_facet | Tabatabai, Amirhossein Akbar Greati, Vitor Ramanayake, Revantha |
| contents | Inspired by Leivant's work on absolute predicativism, Bellantoni and Cook in 1992 introduced a structurally restricted form of recursion called predicative recursion. Using this recursion scheme on the inductive structures of natural numbers and binary strings, they provide a structural and machine-independent characterization of the classes of linear-space and polynomial-time computable functions, respectively. This recursion scheme can be applied to any well-founded or inductive structure, and its underlying principle, predicativization, extends naturally to other computational frameworks, such as higher-order functionals and nested recursion.
In this paper, we initiate a systematic project to gauge the computational power of predicative recursion on arbitrary well-founded structures. As a natural measuring stick for well-foundedness, we use constructive ordinals. More precisely, for any downset $\mathsf{A}$ of constructive ordinals, we define a class $\mathrm{PredR}_{\mathsf{A}}$ of predicative ordinal recursive functions that are permitted to employ a suitable form of predicative recursion on the ordinals in $\mathsf{A}$. We focus on the case that $\mathsf{A}$ is a downset of constructive ordinals below $ϕ_{ω}({0}) = \bigcup_{k=0}^{\infty} ϕ_k({0})$, where $\{ϕ_k\}_{k=0}^{\infty}$ are the functions in the Veblen hierarchy with finite index. We give a complete classification of $\mathrm{PredR}_{\mathsf{A}}$ -- for those downsets that contain at least one infinite ordinal -- in terms of the Grzegorczyk hierarchy $\{\mathcal{E}_k\}_{k=2}^ω$. In this way, we extend Bellantoni-Cook's characterization of $\mathcal{E}_2$ (the class of linear-space computable functions) to obtain a machine-independent and structural characterization of the entire Grzegorczyk hierarchy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18497 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Predicative Ordinal Recursion on the Constructive Veblen Hierarchy Tabatabai, Amirhossein Akbar Greati, Vitor Ramanayake, Revantha Logic Computational Complexity Logic in Computer Science 03D15, 03D20, 03D60, 03F15 F.1.3; F.4.1 Inspired by Leivant's work on absolute predicativism, Bellantoni and Cook in 1992 introduced a structurally restricted form of recursion called predicative recursion. Using this recursion scheme on the inductive structures of natural numbers and binary strings, they provide a structural and machine-independent characterization of the classes of linear-space and polynomial-time computable functions, respectively. This recursion scheme can be applied to any well-founded or inductive structure, and its underlying principle, predicativization, extends naturally to other computational frameworks, such as higher-order functionals and nested recursion. In this paper, we initiate a systematic project to gauge the computational power of predicative recursion on arbitrary well-founded structures. As a natural measuring stick for well-foundedness, we use constructive ordinals. More precisely, for any downset $\mathsf{A}$ of constructive ordinals, we define a class $\mathrm{PredR}_{\mathsf{A}}$ of predicative ordinal recursive functions that are permitted to employ a suitable form of predicative recursion on the ordinals in $\mathsf{A}$. We focus on the case that $\mathsf{A}$ is a downset of constructive ordinals below $ϕ_{ω}({0}) = \bigcup_{k=0}^{\infty} ϕ_k({0})$, where $\{ϕ_k\}_{k=0}^{\infty}$ are the functions in the Veblen hierarchy with finite index. We give a complete classification of $\mathrm{PredR}_{\mathsf{A}}$ -- for those downsets that contain at least one infinite ordinal -- in terms of the Grzegorczyk hierarchy $\{\mathcal{E}_k\}_{k=2}^ω$. In this way, we extend Bellantoni-Cook's characterization of $\mathcal{E}_2$ (the class of linear-space computable functions) to obtain a machine-independent and structural characterization of the entire Grzegorczyk hierarchy. |
| title | Predicative Ordinal Recursion on the Constructive Veblen Hierarchy |
| topic | Logic Computational Complexity Logic in Computer Science 03D15, 03D20, 03D60, 03F15 F.1.3; F.4.1 |
| url | https://arxiv.org/abs/2510.18497 |