Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Higher generalizations of the Turing Model
Published online by Cambridge University Press: 05 June 2014
By
Edited by
Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Summary
Abstract. The “Turing Model”, in the form of “Classical Computability Theory”, was generalized in various ways. This paper deals with generalizations where computations may be infinite. We discuss the original motivations for generalizing computability theory and three directions such generalizations took. One direction is the computability theory of ordinals and of admissible structures. We discuss why Post's problem was considered the test case for generalizations of this kind and briefly how the problem was approached. This direction started with metarecursion theory, and so did the computability theory of normal functionals. We survey the key results of the computability theory of normal functionals of higher types, and how, and why, this theory led to the discovery and development of set recursion. The third direction we survey is the computability theory of partial functionals of higher types, and we discuss how the contributions by Platek on the one hand and Kleene on the other led to typed algorithms of interest in Theoretical Computer Science. Finally, we will discuss possible ways to axiomatize parts of higher computability theory.
Throughout, we will discuss to what extent concepts like “finite” and “computably enumerable” may be generalized in more than one way for some higher models of computability.
§1. Introduction. In this paper we will survey what we may call higher analogues of the Turing model. The Turing model, in the most restricted interpretation of the term, consists of the Turing machines as a basis for defining computable functions, decidable languages, semi-decidable languages and so forth.
- Type
- Chapter
- Information
- Turing's LegacyDevelopments from Turing's Ideas in Logic, pp. 397 - 433Publisher: Cambridge University PressPrint publication year: 2014
References
[1] , , and , Full abstraction for PCF (extended abstract), Theoretical aspects of computer software ( and , editors), Springer-Verlag, 1994, Full paper: Information and Computation, vol. 163 (2000), pp. 409–470, pp. 1–15.
[2] , Computability and continuity in finite types, Thesis, University of Utrecht, 1976.
[3] and , Ordinal recursion theory, In Griffor [13], 1999, pp. 277-299.
[4] Yu. , Computable functionals of finite type, Algebra and Logic, vol. 11 (1972), pp. 203-277.Google Scholar
[5] , General recursion theory, Springer-Verlag, 1980.
[6] , , and (editors), Generalized recursion theory II, North-Holland, 1978.
[7] and (editors), Generalized recursion theory, North-Holland, 1974.
[8] , An introduction to β-recursion theory, In Fenstad et al. [6], 1978, pp. 111-126.
[9] , Proof of Mostowski's conjecture, Bulletin d l'Académie Polonaise des Sciences Mathématiques, Astronomiques et Physiques, vol. 8 (1960), pp. 571-575.Google Scholar
[10] , General recursive functionals offinite type and hierarchies of functionals, Annales de la Faculté des Sciences de l'Université de Clermont-Ferrand, vol. 35 (1967), pp. 202-242.Google Scholar
[11] and (editors), Logic colloquium '69, North-Holland, 1971.
[12] , E-recursively enuemrable degrees, Ph.D. thesis, MIT, 1980.
[13] (editor), Handbook of computability theory, Elsevier, 1999.
[14] , Selection functions for recursive functionals, Notre Dame Journal of Formal Logic, vol. 10 (1969), pp. 333-346.Google Scholar
[15] , On effectively discontinuous type-2 objects, The Journal of Symbolic Logic, vol. 36 (1971), pp. 245-248.Google Scholar
[16] , The superjump and the first recursively Mahlo ordinal, In Gandy and Yates [11], 1971, pp. 43-52.
[17] , Contributions to recursion theory on higher types, Thesis, MIT, 1973.
[18] , Recursion on abstract structures, In Griffor [13], 1999, pp. 315-359.
[19] and , On full abstraction for PCF: I. Models, observables and the full abstraction problem, II. Dialogue games and innocent strategies, III. A fully abstract and universal game model, Information and Computation, vol. 163 (2000), pp. 285-408.Google Scholar
[20] , The fine structure of the constructible universe, Annals of Mathematical Logic, vol. 4 (1972), pp. 229-308.Google Scholar
[21] , Classical descriptive set theory, Springer-Verlag, 1995.
[22] , A semantics for Kleene's j-expressions, The Kleene Symposium (, , and , editors), North-Holland, 1980, pp. 353-366.
[23] , Arithmetical predicates and function quantifiers, Transactions of the American Mathematical Society, vol. 79 (1955), pp. 312-340.Google Scholar
[24] , Hierarchies of number-theoretic predicates, American Mathematical Society. Bulletin, vol. 61 (1955), pp. 193-213.Google Scholar
[25] , Countable functionals, Constructivity in mathematics (, editor), North-Holland, 1959, pp. 81-100.
[26] , Recursive functionals and quantifiers of finite types I, American Mathematical Society. Bulletin, vol. 91 (1959), pp. 1-52.Google Scholar
[27] , Recursive functionals and quantifiers of finite types revisited I, In Fenstad et al. [6], 1978, pp. 185-222.
[28] , Recursive functionals and quantifiers of finite types revisited II, The Kleene Symposium (, , and , editors), North-Holland, 1980, pp. 1-29.
[29] , Recursive functionals and quantifiers of finite types revisited III, Patras logic symposion (, editor), North-Holland, 1982, pp. 1-40.
[30] , Unimonotone functions of finite types (Recursive functionals and quantifiers of finite types revisited IV), In Nerode and Shore [42], 1985, pp. 119-138.
[31] , Recursive functionals and quantifiers of finite types revisited V, Transactions of the American Mathematical Society, vol. 325 (1991), pp. 593-630.Google Scholar
[32] , Interpretation of analysis by means offunctionals of finite type, Constructivity in mathematics (, editor), North-Holland, 1959, pp. 101-128.
[33] , Some reasons for generalizing recursion theory, In Gandy and Yates [11], 1971, pp. 139-198.
[34] and , Metarecursive sets, The Journal of Symbolic Logic, vol. 30 (1965), pp. 318-338.Google Scholar
[35] , On suborderings of the α-recursively enumerable degrees, Annals of Mathematical Logic, vol. 4 (1972), pp. 369-392.Google Scholar
[36] , Inadmissibility, tame r.e. sets and the admissible collapse, Annals of Mathematical Logic, vol. 13 (1978), pp. 149-170.Google Scholar
[37] , Recursion in finite types, Ph.D. thesis, MIT, 1972.
[38] , Computations in higher types, Springer-Verlag, 1977.
[39] , Hyperanalytic predicates, Transactions of the American Mathematical Society, vol. 129 (1967), pp. 249-282.Google Scholar
[40] , Axioms for computation theories—first draft, In Gandy and Yates [11], 1971, pp. 199-255.
[41] , Descriptive set theory, second ed., American Mathematical Society, 2009.
[42] and (editors), Proceedings of the AMS-ASL summer institute on Recursion Theory, Proceedings of Symposia in Pure Mathematics, vol. 42, American Mathematical Society, 1985.
[43] , Recursion in 3E and a splitting theorem, Essays on mathematical and philisophical logic (, , and , editors), D. Reidel Publishing Company, 1978, pp. 275-285.
[44] , Set recursion, In Fenstad et al. [6], 1978, pp. 303-320.
[45] , A classification of higher type functionals, Proceedings from 5th Scandinavian Logic Symposium (, , and , editors), Aalborg University Press, 1979, pp. 301-308.
[46] , Degrees of functionals, Annals of Mathematical Logic, vol. 16 (1979), pp. 269-304.Google Scholar
[47] , Computing with functionals—computability theory or computer science?, The Bulletin of Symbolic Logic, vol. 12 (2006), pp. 43-59.Google Scholar
[48] , Foundations of recursion theory, Ph.D. thesis and supplement, Stanford, 1966.
[49] , LCF considered as a programming language, Theoretical Computer Science, vol. 5 (1977), pp. 223-255.Google Scholar
[50] Theory of recursive functions and effective computability, McGraw-Hill, 1967.
[51] , Post's problem, admissible ordinals, and regularity, Transactions of the American Mathematical Society, vol. 124 (1966), pp. 1-23.Google Scholar
[52] , The 1-section of a type n-object, In Fenstad and Hinman [7], 1974, pp. 81-93.
[53] , The k-section of a type n-object, American Journal of Mathematics, vol. 99 (1977), pp. 901-917.Google Scholar
[54] , Post's problem in E-recursion theory, In Nerode and Shore [42], 1985, pp. 177-193.
[55] , On the limits of E-recursive enumerability, Annals of Pure and Applied Logic, vol. 31 (1986), pp. 87-120.Google Scholar
[56] , Higher recursion theory, Springer-Verlag, 1990.
[57] and , The α-finite injury method, Annals of Mathematical Logic, vol. 4 (1972), pp. 343-367.Google Scholar
[58] , On semantics of the applicative algorithmic languages, Thesis (in Russian), Novosibirsk, 1976.
[59] , A type-theoretical alternative to ISWIM, CUCH, OWHY, unpublished manuscript, 1969, Oxford; later published with comments in Theoretical Computer Science, vol. 121 (1993), pp. 411-440.
[60] , The irregular and non-hyperregular α-r.e. degrees, Israel Journal of Mathematics, vol. 22 (1975), pp. 123-155.Google Scholar
[61] , Splitting an α-recursively enumerable set, Transactions of the American Mathematical Society, vol. 204 (1975), pp. 65-78.Google Scholar
[62] , The recursively enumerable α-degrees are dense, Annals of Mathematical Logic, vol. 9 (1976), pp. 123-155.Google Scholar
[63] , Post's problem for admissible sets, In Fenstad and Hinman [7], 1974, pp. 437-441.
[64] , Short course on admissible recursion theory, In Fenstad et al. [6], 1978, pp. 355-390.
[65] , Aspects of E-recursion, Ph.D. thesis, Harvard, 1981.
[66] , The E-recursively enumerable degrees are dense, In Nerode and Shore [42], 1985, 195-213.
[67] , Reflection and forcing in E-recursion theory, Annals of Pure and Applied Logic, vol. 29 (1985), pp. 79-106.Google Scholar
[68] , Recursive well orderings, The Journal of Symbolic Logic, vol. 20 (1955), pp. 151-163.Google Scholar
[69] , Hyperarithmetical quantifiers, Fundamenta Mathematicae, vol. 48 (1959), pp. 313-320.Google Scholar
[70] , Provably recursive functionals of analysis: a consistency proof of analysis by an extension of principles formulated in current intuitionistic mathematics, Recursive function theory (, editor), Proceedings of Symposia in Pure Mathematics, vol. V, American Mathematical Society, 1962, pp. 1-27.
[71] , On priority arguments in Friedberg theories, Thesis, University of Toronto, 1973.
[72] , Recursive dilators and generalized recursion, Proceedings of the Herbrand Symposium (, editor), North-Holland, 1982, pp. 325-332.
[73] , The 1-section of a non-normal type-2 object, In Fenstad et al. [6], 1978, pp. 407-417.
[74] , Transfinite machine models, this volume.
- 2
- Cited by