The 𝛼-union theorem and generalized primitive recursion

Jacobs, Barry E.

doi:10.1090/S0002-9947-1978-0479362-8

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
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 }\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.

[1] Manuel Blum, A machine-independent theory of the complexity of recursive functions., J. Assoc. Comput. Mach. 14 (1967), 322–336. MR 0235912 (38 #4213)
[2] Robert L. Constable, The operator gap, J. Assoc. Comput. Mach. 19 (1972), 175–183. MR 0314608 (47 #3159)
[3] Martin Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York, 1958. MR 0124208 (23 #A1525)
[4] Kurt Gödel, The Consistency of the Continuum Hypothesis, Annals of Mathematics Studies, no. 3, Princeton University Press, Princeton, N. J., 1940. MR 0002514 (2,66c)
[5] Andrzej Grzegorczyk, Some classes of recursive functions, Rozprawy Mat. 4 (1953), 46. MR 0060426 (15,667d)
[6] Leo Harrington, Some contributions to the theory of recursion on higher types, Ph.D. Thesis, Massachusetts Institute of Technology, 1972.
[7] B. E. Jacobs, $\alpha$ -computational complexity, Ph.D. Thesis; Tech. Report IMM-408, Courant Inst. Math. Sci., New York Univ., New York, 1975.
[8] Barry E. Jacobs, On generalized computational complexity, J. Symbolic Logic 42 (1977), no. 1, 47–58. MR 0505383 (58 #21538)
[9] Ronald B. Jensen and Carol Karp, Primitive recursive set functions, Axiomatic Set Thoory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967), Amer. Math. Soc., Providence, R.I., 1971, pp. 143–176. MR 0281602 (43 #7317)
[10] S. C. Kleene, Introduction to metamathematics, North-Holland, Amsterdam, 1971.
[11] G. Kreisel, Set theoretic problems suggested by the notion of potential totality., Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw, 1959) Pergamon, Oxford, 1961, pp. 103–140. MR 0146073 (26 #3599)
[12] G. Kreisel and Gerald E. Sacks, Metarecursive sets, J. Symbolic Logic 30 (1965), 318–338. MR 0213233 (35 #4097)
[13] S. Kripke, Transfinite recursion on admissible ordinals. I, II (abstracts), J. Symbolic Logic 29 (1964), 161-162.
[14] -, The theory of transfinite recursions, Class Notes by A. Thomas Tymoczko (unpublished).
[15] A. Leggett and R. Shore, Types of simple $\alpha$ -recursively enumerable sets (to appear).
[16] Manuel Lerman, Least upper bounds for minimal pairs of 𝛼-r.e. 𝛼-degrees, J. Symbolic Logic 39 (1974), 49–56. MR 0357091 (50 #9559)
[17] Manuel Lerman and Gerald E. Sacks, Some minimal pairs of 𝛼-recursively enumerable degrees, Ann. Math. Logic 4 (1972), 415–442. MR 0439605 (55 #12491)
[18] M. Machover, The theory of transfinite recursion, Bull. Amer. Math. Soc. 67 (1961), 575–578. MR 0142448 (26 #17), http://dx.doi.org/10.1090/S0002-9904-1961-10696-4
[19] E. McCreight and A. Meyer, Classes of computable functions defined by bounds on computation, Preliminary report, Proc. ACM Sympos. on Theory of Computing, 1969, pp. 79-88.
[20] R. Platek, Foundations of recursion theory, Ph.D. Thesis, Stanford Univ., 1966.
[21] G. E. Sacks and S. G. Simpson, The 𝛼-finite injury method, Ann. Math. Logic 4 (1972), 343–367. MR 0369041 (51 #5277)
[22] Richard A. Shore, ∑_{𝑛} sets which are Δ_{𝑛}-incomparable (uniformly), J. Symbolic Logic 39 (1974), 295–304. MR 0419197 (54 #7229)
[23] Richard A. Shore, Splitting an 𝛼-recursively enumerable set, Trans. Amer. Math. Soc. 204 (1975), 65–77. MR 0379154 (52 #60), http://dx.doi.org/10.1090/S0002-9947-1975-0379154-1
[24] -, The recursively enumerable $\alpha$ -degrees are dense, Ann. Math. Logic (to appear).
[25] -, $\alpha$ -recursion theory (to appear).
[26] Gaisi Takeuti, Construction of the set theory from the theory of ordinal numbers, J. Math. Soc. Japan 6 (1954), 196–220. MR 0067827 (16,783b)
[27] Gaisi Takeuti, On the theory of ordinal numbers, J. Math. Soc. Japan 9 (1957), 93–113. MR 0086751 (19,237e)
[28] Tosiyuki Tugué, On the partial recursive functions of ordinal numbers, J. Math. Soc. Japan 16 (1964), 1–31. MR 0167404 (29 #4677)
[29] Paul Young, Easy constructions in complexity theory: Gap and speed-up theorems, Proc. Amer. Math. Soc. 37 (1973), 555–563. MR 0312768 (47 #1323), http://dx.doi.org/10.1090/S0002-9939-1973-0312768-7

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|

Bibliography