Predicative Ordinal Recursion on the Constructive Veblen Hierarchy

Abstract

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 $\ddot{I}{•}_{\ddot{I}‰}(0)={\bigcup }_{k=0}^{\infty }\ddot{I}{•}_k(0)$, where $\{\ddot{I}{•}_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}^{\ddot{I}}‰$. 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.

100 pages