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
DOI: https://doi.org/10.1090/S0002-9947-1978-0479362-8
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?)

  • [1] M. Blum, A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach. 14 (1967), 322-336. MR 38 #4213. MR 0235912 (38:4213)
  • [2] R. L. Constable, The operator gap, J. Assoc. Comput. Mach. 19 (1972), 175-183. MR 47 #3159. MR 0314608 (47:3159)
  • [3] M. Davis, Computability and unsolvability, McGraw-Hill, New York, 1958. MR 23 #A1525. MR 0124208 (23:A1525)
  • [4] K. Gödel, The consistency of the continuum hypothesis, Ann. of Math. Studies, no. 3, Princeton Univ. Press, Princeton, N. J., 1940. MR 2, 66. MR 0002514 (2:66c)
  • [5] A. Grzegorczyk, Some classes of recursive functions, Rozprawy Math. 4 (1953), 1-45. MR 15,667. 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] -, On generalized computational complexity, J. Symbolic Logic (to appear). MR 0505383 (58:21538)
  • [9] R. B. Jensen and C. Karp, Primitive recursive set functions, Axiomatic Set Theory (Proc. Sympos. Pure Math., Vol. 13, Part I), Amer. Math. Soc., Providence, R. I., 1971. MR 43 #7317. 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 Press, Oxford, 1961, pp. 103-140. MR 26 #3599. MR 0146073 (26:3599)
  • [12] G. Kreisel and G. E. Sacks, Metarecursive sets, J. Sympbolic Logic 30 (1965), 318-338. MR 35 #4097. 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] M. Lerman, Least upper bounds for pairs of $ \alpha $-r.e. $ \alpha $-degrees, J. Symbolic Logic 39 (1974), 49-56. MR 0357091 (50:9559)
  • [17] M. Lerman and G. E. Sacks, Some minimal pairs of $ \alpha $-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 26 #17. MR 0142448 (26:17)
  • [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 $ \alpha $-finite injury method, Ann. Math. Logic 4 (1972), 343-367. MR 51 #5277. MR 0369041 (51:5277)
  • [22] R. A. Shore, $ {\Sigma _n}$ sets which are $ {\Delta _n}$ incomparable (uniformly), J. Symbolic Logic 39 (1974), 295-304. MR 0419197 (54:7229)
  • [23] -, Splitting an $ \alpha $-recursively enumerable set, Trans. Amer. Math. Soc. 204 (1975), 65-77. MR 52 #60. MR 0379154 (52:60)
  • [24] -, The recursively enumerable $ \alpha $-degrees are dense, Ann. Math. Logic (to appear).
  • [25] -, $ \alpha $-recursion theory (to appear).
  • [26] G. Takeuti, Construction of the set theory from the theory of ordinal numbers, J. Math. Soc. Japan 6 (1954), 196-220. MR 16, 783. MR 0067827 (16:783b)
  • [27] -, On the theory of ordinal numbers, J. Math. Soc. Japan 9 (1957), 93-113. MR 19, 237. MR 0086751 (19:237e)
  • [28] T. Tugué, On the partial recursive functions of ordinal numbers, J. Math. Soc. Japan 16 (1964), 1-31. MR 29 #4677. MR 0167404 (29:4677)
  • [29] P. Young, Easy constructions in complexity theory: Gap and speed-up theorems, Proc. Amer. Math. Soc. 37 (1973), 555-563. MR 47 # 1323. MR 0312768 (47:1323)

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

DOI: https://doi.org/10.1090/S0002-9947-1978-0479362-8
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