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

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 }\vert\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: $ \alpha $-recursion theory, admissible ordinal, $ \alpha $-computational complexity measure, $ \alpha $-recursively enumerable, priority argument, $ \alpha $-complexity class, primitive recursive ordinal functions, Grzegorczyk hierarchy
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society