Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

The $\alpha$-union theorem and generalized primitive recursion
HTML articles powered by AMS MathViewer

by Barry E. Jacobs PDF
Trans. Amer. Math. Soc. 237 (1978), 63-81 Request permission

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
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
  • © Copyright 1978 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 237 (1978), 63-81
  • MSC: Primary 03D60; Secondary 68C25
  • DOI: https://doi.org/10.1090/S0002-9947-1978-0479362-8
  • MathSciNet review: 479362