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 ${ \phi}_{ { \omega}}({ 0}) = \bigcup_{ k=0}^{ \infty} { \phi}_k({ 0})$, where $\{ { \phi}_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}^{ \omega}$. 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.
Categories: math.LO cs.CC cs.LO