Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
  1. Home
  2. Books
  3. General Recursion Theory
Publisher:
Cambridge University Press
Online publication date:
March 2017
Print publication year:
2017
Online ISBN:
9781316717073
DOI:
https://doi.org/10.1017/9781316717073
Subjects:
Mathematics, Logic, Categories and Sets, Computer Science, Programming Languages and Applied Logic
Series:
Perspectives in Logic (10)
Information

Book description

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the tenth publication in the Perspectives in Logic series, Jens E. Fenstad takes an axiomatic approach to present a unified and coherent account of the many and various parts of general recursion theory. The main core of the book gives an account of the general theory of computations. The author then moves on to show how computation theories connect with and unify other parts of general recursion theory. Some mathematical maturity is required of the reader, who is assumed to have some acquaintance with recursion theory. This book is ideal for a second course in the subject.

Refine List

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×

Contents

Contents
References
References
Aanderaa, S. Inductive definitions and their closure ordinals. In: Fenstad-Hinman [31], 207-220
Aczel, P. An axiomatic approach to recursive function theory on the integers. (Circulated notes, 1969)
Aczel, P. Representability in some systems of second-order arithmetic. Israel J. Math. 8, 309-328 (1970)
Aczel, P. Stage comparison theorems and game playing with inductive definitions. (Circulated notes, 1972)
Aczel, P. An axiomatic approach to recursion on admissible ordinals and the Kreisel-Sacks construction of meta-recursion theory. Recursive Function Theory Newsletter, 1974
Aczel, P. Quantifiers, games, and inductive definitions. In: Kanger [73], 1-14
Aczel, P. An introduction to inductive definitions. In: Barwise [12], 739-782
Aczel, P., Hinman, P. G. Recursion in the superjump. In: Fenstad-Hinman [31], 3-41
Barendregt, H. Normed uniformly reflexive structures. In: Bohm [16], 272-286
Barwise, K. J. Admissible sets over models of set theory. In: Fenstad-Hinman [31], 97-122
Barwise, K. J. Admissible Sets and Structures, Perspectives in Mathematical Logic. Berlin, Heidelberg, New York: Springer, 1975, 394 pp.
Barwise, K. J. Handbook of Mathematical Logic. Amsterdam: North-Holland, 1977, 1165 pp.
Barwise, K. J. Monotone quantifiers and admissible sets. In: Fenstad-Gandy-Sacks [30], 1-38
Barwise, K. J., Gandy, R., Moschovakis, Y. N. The next admissible set. J. symbolic Logic 36, 108-120 (1971)
Bergstra, J. Computability and continuity in finite types. Utrecht: Ph.D. thesis, 1976
Böhm, C. λ-Calculus and Computer Science Theory (Proceedings of the Symposium held in Rome, 1975, editor). Berlin, Heidelberg, New York: Springer, 1975, 370 pp.
Butts, R. E., Hintikka, J. Logic, Foundations of Mathematics and Computability Theory (Proceedings of Fifth International Congress of Logic, Methodology and Philosophy of Science, London, Ontario: 1975, editors). Dordrecht: D. Reidel Publishing Company 1977, 406 pp.
Cenzer, D. Ordinal recursion and inductive definitions. In: Fenstad-Hinman [31], 221-264
Devlin, K. J. Aspects of Constructibility. Berlin, Heidelberg, New York: Springer 1973, 240 pp.
Diller, J., Müller, G. H. Proof Theory Symposium, Kiel 1974 (Proceedings of the International Summer Institute and Logic Colloquium, editors). Berlin, Heidelberg, New York: Springer 1975, 383 pp.
Driscoll, G. C, Jr. Metarecursively enumerable sets and their metadegrees. J. symbolic Logic 33, 389-411 (1968)
Ershov, Y. L. Maximal and everywhere defined functionals. Algebra and Logic 13, 210-225 (1974)
Ershov, Y. L. Model C of partial continuous functionals. In: Gandy-Hyland [41], 455-467
Feferman, S. Some applications of the notions of forcing and generic sets. Fund. Math. 56, 325-345 (1964/65)
Feferman, S. Inductive schemata and recursively continuous functionals. In: Gandy-Hyland [41], 373-392
Fenstad, J. E. On axiomatizing recursion theory. In: Fenstad-Hinman [31], 385-404
Fenstad, J. E. Computation theories: an axiomatic approach to recursion on general structures. In: Müller et al. [119], 143-168
Fenstad, J. E. Between recursion theory and set theory. In: Gandy-Hyland [41], 393-406
Fenstad, J. E. On the foundation of general recursion theory: Computations versus inductive definability. In: Fenstad-Gandy-Sacks [30], 99-110
Fenstad, J. E., Gandy, R. O., Sacks, G. E. Generalized Recursion Theory II (Proceedings of the 1977 Oslo Symposium, editors). Amsterdam: North-Holland 1978, 417 pp.
Fenstad, J. E., Hinman, P.G. Generalized Recursion Theory (Proceedings of the 1972 Oslo Symposium, editors). Amsterdam: North-Holland 1974, 456 pp.
Fenstad, J. E., Normann, D. On absolutely measurable sets. Fund. Math. 81, 91-98 (1974)
Friedman, H. Axiomatic recursive function theory. In: Gandy-Yates [44], 113-137
Friedman, H. Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory. In: Gandy-Yates [44], 316-389
Friedman, S. D. An introduction to β-recursion theory. In: Fenstad-Gandy-Sacks [30], 111-126
Friedman, S. D. Negative solutions to Post's problem, I. In: Fenstad-Gandy-Sacks [30], 127-133
Friedman, S. D., Sacks, G. E. Inadmissible recursion theory. Bull. Amer. math. Soc. 82, 255-256 (1977)
Gandy, R. O. General recursive functionals of finite type and hierarchies of functions. Ann. Fac. Sci. Univ. Clermont-Ferrand 55, 5-24 (1967)
Gandy, R. O. Inductive definitions. In: Fenstad-Hinman [31], 265-299
Gandy, R. O. Set-theoretic functions for elementary syntax. In: Jech [69], 103-126
Gandy, R. O., Hyland, J. M. E. Logic Colloquium '76 (Proceedings of the Summer School and Colloquium in Mathematical Logic, Oxford: 1976, editors). Amsterdam: North-Holland 1977, 612 pp.
Gandy, R. O., Hyland, J. M.E. Computable and recursively countable functions of higher type. In: Gandy-Hyland [41], 407-438
Gandy, R. O., Sacks, G. E. A minimal hyperdegree. Fund. Math. 61, 215-223 (1967)
Gandy, R. O., Yates, C. E. M. Logic Colloquium '69 (Proceedings of the Summer School and Colloquium in Mathematical Logic, Manchester: 1969, editors). Amsterdam: North-Holland 1971, 451 pp.
Gordon, C. E. A comparison of abstract computability theories. Los Angeles: Ph.D. thesis 1968
Gregory, J. On a finiteness condition for infinitary languages. Maryland: Ph.D. thesis 1969
Gregory, J. On a finiteness condition for infinitary languages. In: Kueker [94], 143-206
Grilliot, T. J. Selection functions for recursive functionals. Notre Dame J. formal Logic 10, 333-346 (1969)
Grilliot, T. J. Inductive definitions and computability. Trans. Amer. math. Soc. 158, 309-317 (1971)
Grilliot, T. J. On effectively discontinuous type-2 objects. J. symbolic Logic 36, 245-248 (1971)
Grilliot, T. J. Omitting types: applications to recursion theory. J. symbolic Logic 37, 81-89 (1972)
Gurrik, P. K. Om E-rekursjonsteori [in Norwegian]. Oslo: Cand. Real, thesis 1978
Harrington, L. A. Contributions to recursion theory in higher types. MIT: Ph.D. thesis 1973
Harrington, L. A. The superjump and the first recursively Mahlo ordinal. In: Fenstad-Hinman [31], 43-52
Harrington, L. A., MacQueen, D. B. Selection in abstract recursion theory. J. symbolic Logic 41, 153-158 (1976)
Harrington, L. A., Kechris, A. S. On characterizing Spector Classes. J. symbolic Logic 40, 19-24 (1975)
Harrington, L. A., Kechris, A. S. On monotone vs. nonmonotone induction. Bull. Amer. math. Soc. 82, 888-890 (1976)
Harrington, L. A., Kechris, A. S., Simpson, S. G. 1-envelopes of type-2 objects. Amer. math. Soc. Notices 20, A-587 (1973)
Hinman, P. G. Hierarchies of effective descriptive set theory. Trans. Amer. math. Soc. 142, 111-140 (1969)
Hinman, P. G. Degrees of continuous functionals. J. symbolic Logic 38, 393-395 (1973)
Hinman, P. G. Recursion-Theoretic Hierarchies, Perspectives in Mathematical Logic. Berlin, Heidelberg, New York: Springer 1978, 480 pp.
Hinman, P. G., Moschovakis, Y. N. Computability over the continuum. In: Gandy-Yates [44], 77-105
Hodges, W. On the effectivity of some field constructions. Proc. London math. Soc. (3), 32, 133-162 (1976)
Hyland, J. M. E. Recursion theory on the countable functionals. Oxford: Ph.D. thesis 1975
Hyland, J. M. E. Aspects of constructivity in mathematics. In: Gandy-Hyland [41], 439-454
Hyland, J. M. E. The intrinsic recursion theory on the countable or continuous functionals. In: Fenstad- Gandy-Sacks [30], 135-145
Hyland, J. M. E. Filter spaces and continuous functionals. Ann. math. Logic (to appear)
Heyting, A. Constructivity in Mathematics (Proceedings of the Colloquium held at Amsterdam, 1957, editor). Amsterdam: North-Holland 1959, 297 pp.
Jech, T. J. Axiomatic Set Theory II (Proceedings of the Thirteenth Symposium in Pure Mathematics of the Amer. math. Soc, Los Angeles: 1967, editor). Amer. math. Soc, Providence, R.I.: 1974,222 pp.
Jensen, R. B. Admissible sets. (Circulated notes, 1969)
Jensen, R. B. The fine structure of the constructible hierarchy. Ann. math. Logic 4, 229-308 (1972)
Jensen, R. B., Karp, C. Primitive recursive set functions. In: Scott [147], 143-176
Kanger, S. Proceedings of the Third Scandinavian Logic Symposium (Uppsala, Sweden: 1973, editor). Amsterdam: North-Holland 1975, 214 pp.
Kechris, A. S. The Structure of Envelopes: a Survey of Recursion Theory in Higher Types. MIT Logic Seminar Notes, 1973
Kechris, A. S. On Spector Classes. In: Kechris, A. S. and Moschovakis, Y. N. (editors), CABAL SEMINAR. Berlin, Heidelberg, New York: Springer 1978, 245-277
Kechris, A. S. Spector second order classes and reflection. In: Fenstad-Gandy-Sacks [30], 147-183
Kechris, A. S., Moschovakis, Y. N. Recursion in higher types. In: Barwise [12], 681-737
Kleene, S. C. Introduction to Metamathematics. Amsterdam: North-Holland; Groningen: P. Noordhoff; New York: van Nostrand Co. 1952
Kleene, S. C. Arithmetic predicates and function quantifiers. Trans. Amer. math. Soc. 79, 312-340 (1955)
Kleene, S. C. On the forms of the predicates in the theory of constructive ordinals (second paper). Amer. J. math. 77, 405-428 (1955)
Kleene, S. C. Hierarchies of number-theoretic predicates. Bull. Amer. math. Soc. 61, 193-213 (1955)
Kleene, S. C. Countable functional. In: Heyting [68], 81-100
Kleene, S. C. Recursive functional and quantifiers of finite types, I. Trans. Amer. math. Soc. 91, 1-52 (1959)
Kleene, S. C. Quantification of number-theoretic functions. Compositio math. 14, 23-41 (1959)
Kleene, S. C. Recursive functional and quantifiers of finite types, II. Trans. Amer. math. Soc. 108, 106-142 (1963)
Kleene, S. C. Recursive functional and quantifiers of finite types, revisited, I. In: Fenstad-Gandy-Sacks [30], 185-222
Kolaitis, P. G. Recursion in E on a structure versus positive elementary induction. J. symbolic Logic (to appear)
Kreisel, G. Interpretation of analysis by means of functionals of finite type. In: Heyting [68], 101-128
Kreisel, G. Set theoretic problems suggested by the notion of potential totality. In: Infinistic Methods (Proceedings of the 1959 Warsaw Symposium). Oxford: Pergamon Press 1961, pp. 103-140
Kreisel, G. Some reasons for generalizing recursion theory. In: Gandy-Yates [44], 139-198
Kreisel, G., Sacks, G. E. Metarecursive sets. J. symbolic Logic 30, 318-338 (1965)
Kripke, S. Transfinite recursions on admissible ordinals, I, II (abstracts). J. symbolic Logic 29, 161-162 (1964)
Kripke, S. Admissible ordinals and the analytic hierarchy (abstract). J. symbolic Logic 29, 162 (1964)
Kueker, D. W. Infinitary Logic: In Memoriam Carol Karp (A Collection of papers, editor). Berlin, Heidelberg, New York: Springer 1975, 206 pp.
Lavori, P. Recursion in the extended superjump. Illinois J. Math. 21, 752-758 (1977)
Louveau, A. La hierarchie borelienne des ensemble Δ1 1. C.R. Acad. Sc. Paris 285, 601-604 (1977)
Louveau, A. Recursivity and compactness. In: Muller-Scott [120], 303-337
MacQueen, D. B. Post's problem for recursion in higher types. MIT: Ph.D. thesis 1972
Malcev, A. I. Algebraic Systems. Berlin, Heidelberg, New York: Springer 1973, 317 pp.
Maass, W. Inadmissibility, tame r.e. sets and the admissible collapse. Ann. math. Logic 13,149-170 (1978).
Maass, W. Fine structure theory for the constructible universe in α- and β-recursion theory. In: Müller-Scott [120], 339-359
Maass, W. Recursively invariant β-recursion theory. (In preparation)
Miettinen, S., Väänänen, J. Proceedings of the Symposiums on Mathematical Logic, Oulu 1974 and Helsinki 1975. Helsinki: 1977, 103 pp.
Mitschke, G. λ-Kalkiil, 8-Konversion und axiomatische Rekursionstheorie. Darmstadt: Habilitation-schrift 1976
Moldestad, J. Computations in Higher Types. Berlin, Heidelberg, New York: Springer 1977, 203 pp.
Moldestad, J. On the role of the successor function in recursion theory. In: Fenstad-Gandy-Sacks [30], 283-301
Moldestad, J., Normann, D. Models for recursion theory. J. symbolic Logic 41, 719-729 (1976)
Moldestad, J., Stoltenberg-Hansen, V., Tucker, J. V. Finite algorithmic procedures and inductive definability. Math. Scand. (to appear)
Moldestad, J., Stoltenberg-Hansen, V., Tucker, J. V. Finite algorithmic procedures and computation theories. Math. Scand. (to appear)
Moldestad, J., Tucker, J. V. On the classification of computable functions in an abstract setting. (In preparation)
Moschovakis, Y. N. Hyperanalytic predicates. Trans. Amer. math. Soc. 129, 249-282 (1967)
Moschovakis, Y. N. Abstract first-order computability I, II. Trans. Amer. math. Soc. 138, 427-464, 465-504 (1969)
Moschovakis, Y. N. Axioms for computation theories—first draft. In: Gandy-Yates [44], 199-255
Moschovakis, Y. N. Structural characterizations of classes of relations. In: Fenstad-Hinman [31], 53-79
Moschovakis, Y. N. Elementary Induction on Abstract Structures. Amsterdam: North-Holland 1974, 218 pp.
Moschovakis, Y. N. On non-monotone inductive definability. Fundamenta Math. 82, 39-83 (1974)
Moschovakis, Y. N. On the basic notions in the theory of induction. In: Butts-Hintikka [17], 207-236
Moschovakis, Y. N. Descriptive Set Theory. Amsterdam: North-Holland (to appear)
Müller, G. H., Oberschelp, A., Potthoff, K. Logic Conference Kiel, 1974 (Proceedings of the International Summer Institute and Logic Colloquium, editors). Berlin, Heidelberg, New York: Springer 1975, 651 pp.
Müller, G. H., Scott, D. S. Higher Set Theory (Proceedings Oberwolfach 1977, editors). Berlin, Heidelberg, New York: Springer 1978, 476 pp.
Normann, D. On abstract 1-sections. Synthese 27, 259-263 (1974)
Normann, D. Imbedding of higher type theories. Oslo preprint 1974
Normann, D. A continuous functional with non-collapsing hierarchy. J. symbolic Logic 43, 487-491 (1978)
Normann, D. Set recursion. In: Fenstad-Gandy-Sacks [30], 303-320
Normann, D. Recursion in 3 E and a splitting theorem. In: Hintikka, J., Niiniluoto, I, Saarinen, E. (editors), ESSAYS ON MATHEMATICAL AND PHILOSOPHICAL LOGIC. Dordrecht: D. Reidel Publishing Company 1979, 275-285
Normann, D. A jump operator in set recursion. Z. math. Logik und Grundl. Math, (to appear)
Normann, D. Degrees of functionals. Ann. math. Logic (to appear)
Normann, D. Countable functionals and the analytic hierarchy. J. symbolic Logic (to appear)
Normann, D. Recursion in the Countable Functionals. Springer Lecture Notes (to appear)
Normann, D., Stoltenberg-Hansen, V. A non-adequate admissible set with a good degree-structure. In: Fenstad-Gandy-Yates [30], 321-329
Normann, D., Wainer, S. The 1-section of a countable functional. J. symbolic Logic (to appear)
Nyberg, A. Inductive operators on resolvable structures. In: Miettinen-Väänänen [103], 91-100
Platek, R. A. Foundations of Recursion theory. Stanford: Ph.D. thesis and supplement 1966
Richter, W. Recursively Mahlo ordinals and inductive definitions. In: Gandy-Yates [44], 273-288
Richter, W., Aczel, P. Inductive definitions and reflecting properties of admissible ordinals. In: Fenstad- Hinman [31], 301-381
Rogers, H., Jr. Theory of Recursive Functions and Effective Computability. New York: McGraw-Hill 1967, 482 pp.
Rose, H. E., Shepherdson, J. C. Logic Colloquium ’73 (Proceedings of the Summer School and Colloquium in Mathematical Logic, Bristol: 1973, editors). Amsterdam: North-Holland 1975, 513 pp.
Sacks, G. E. Degrees of Unsolvability. Princeton: Ann. math. Studies, No. 55, 1963
Sacks, G. E. The recursively enumerable degrees are dense. Ann. Math. 80, 300-312 (1964)
Sacks, G. E. Post's problem, admissible ordinals and regularity. Trans. Amer. math. Soc. 124, 1-23 (1966)
Sacks, G. E. Forcing with perfect closed sets. In: Scott [147], 331-355
Sacks, G. E. The 1-section of a type n object. In: Fenstad-Hinman [31], 81-93
Sacks, G. E. The k-section of a type-n object. Amer. J. Math. 99, 901-917 (1977)
Sacks, G. E. R.e. sets higher up. In: Butts-Hintikka [17], 173-194
Sasso, L. P. Degrees of unsolvability of partial functions. Berkeley: Ph.D. thesis 1971
Schwichtenberg, H., Wainer, S. S. Infinite terms and recursion in higher types. In: Diller-Müller [20], 314-364
Scott, D. S. Axiomatic Set Theory I (Proceedings of the Thirteenth Symposium in Pure Mathematics of the Amer. math. Soc, Los Angeles: 1967, editor). Providence, R.I.: Amer. math. Soc. 1971, 474 pp.
Shepherdson, J. C. Computations over abstract structures: serial and parallel procedures and Friedman's effective definitional schemes. In: Rose-Shepherdson [137], 445-513
Shoenfield, J. R. A hierarchy based on type two objects. Trans. Amer. math. Soc. 134, 103-108 (1968)
Shore, R. A. Splitting an α-recursively enumerable set. Trans. Amer. math. Soc. 204, 65-78 (1975)
Shore, R. A. The recursively enumerable a-degrees are dense. Ann. math. Logic 9, 123-155 (1976)
Shore, R. A. α-recursion theory. In: Barwise [12], 653-680
Simpson, S. G. Admissible ordinals and recursion theory. MIT: Ph.D. thesis 1971
Simpson, S. G. Degree theory on admissible ordinals. In: Fenstad-Hinman [31], 165-193
Simpson, S. G. Post's problem for admissible sets. In: Fenstad-Hinman [31], 437-441
Simpson, S. G. Short course on admissible recursion theory. In: Fenstad-Gandy-Sacks [30], 355-390
Soare, R. I. Recursively enumerable sets and degrees. Bull. Amer. math. Soc. 84, 1149-1181 (1978)
Spector, C. Recursive well-orderings. J. symbolic Logic 20, 151-163 (1955)
Spector, C. Recursive ordinals and predicative set theory. In: Summaries of talk presented at the Summer Institute for Symbolic Logic, Cornell: 1957
Spector, C. Hyperarithmetic quantifiers. Fundamenta Math. 48, 313-320 (1959)
Spector, C. Inductively defined sets of natural numbers. In: Infinistic Methods (Proceedings of the 1959 Warsaw Symposium). Oxford: Pergamon Press 1961, 97-102
Stoltenberg-Hansen, V. On priority arguments in Friedberg theories. Toronto: Ph.D. thesis 1973
Stoltenberg-Hansen, V. Finite injury arguments in infinite computation theories. Ann. math. Logic 16,57-80 (1979)
Stoltenberg-Hansen, V. A regular set theorem for infinite computation theories. Oslo preprint 1977
Stoltenberg-Hansen, V. Weakly inadmissible recursion theory. In: Fenstad-Gandy-Sacks [30], 391-405
Strong, H. R. Algebraically generalized recursive function theory. IBM J. Res. Devel. 12, 465-475 (1968)
Troelstra, A.S. Metamathematical Investigations of Intuitionistic Analysis, Arithmetic, and Analysis (A collection of papers, editor). Berlin, Heidelberg, New York: Springer 1973, 485 pp.
Tucker, J. V. Computing in algebraic systems. Oslo preprint 1978
Wagner, E. G. Uniform reflexive structures: on the nature of Godelizations and relative computability. Trans. Amer. math. Soc. 144, 1-41 (1969)
Wainer, S. S. A hierarchy for the 1-section of any type two object. J. symbolic Logic 39, 88-94 (1974)
Wang, H. Remarks on constructive ordinals and set theory. In: Summaries of talks presented at the Summer Institute for Symbolic Logic. Cornell: 1957

Metrics

Full text views

Total number of HTML views: 0
Total number of PDF views: 0 *
Loading metrics...

Book summary page views

Total views: 0 *
Loading metrics...

* Views captured on Cambridge Core between #date#. This data will be updated every 24 hours.

Usage data cannot currently be displayed.