The $\alpha$-union theorem and generalized primitive recursion

Abstract:

A generalization to $\alpha$-recursion theory of the McCreight-Meyer Union Theorem is proved. Theorem. Let $\Phi$ be an $\alpha$-computational complexity measure and $\{ {f_\varepsilon }|\varepsilon < \alpha \}$ an $\alpha$-r.e. strictly increasing sequence of $\alpha$-recursive functions. Then there exists an $\alpha$-recursive function k such that $C_k^\Phi = { \cup _{\varepsilon < \alpha }}C_{{f_\varepsilon }}^\Phi$. The proof entails a no-injury cancellation atop a finite-injury priority construction and necessitates a blocking strategy to insure proper convergence. Two infinite analogues to ($\omega$-) primitive recursive functions are studied. Although these generalizations coincide at $\omega$, they diverge on all admissible $\alpha > \omega$. Several well-known complexity properties of primitive recursive functions hold for one class but fail for the other. It is seen that the Jensen-Karp ordinally primitive recursive functions restricted to admissible $\alpha > \omega$ cannot possess natural analogues to Grzegorczyk’s hierarchy.