Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

Author: Barry E. Jacobs
Journal: Trans. Amer. Math. Soc. 237 (1978), 63-81
MSC: Primary 03D60; Secondary 68C25
MathSciNet review: 479362
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D60, 68C25

Retrieve articles in all journals with MSC: 03D60, 68C25

Additional Information

Keywords: <IMG WIDTH="19" HEIGHT="20" ALIGN="BOTTOM" BORDER="0" SRC="images/img3.gif" ALT="$\alpha$">-recursion theory, admissible ordinal, <IMG WIDTH="19" HEIGHT="20" ALIGN="BOTTOM" BORDER="0" SRC="images/img2.gif" ALT="$\alpha$">-computational complexity measure, <IMG WIDTH="19" HEIGHT="20" ALIGN="BOTTOM" BORDER="0" SRC="images/img28.gif" ALT="$\alpha$">-recursively enumerable, priority argument, <IMG WIDTH="19" HEIGHT="20" ALIGN="BOTTOM" BORDER="0" SRC="images/img1.gif" ALT="$\alpha$">-complexity class, primitive recursive ordinal functions, Grzegorczyk hierarchy
Article copyright: © Copyright 1978 American Mathematical Society