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
Transfinite machine models
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
§1. Introduction. In recent years there has emerged the study of discrete computational models which are allowed to act transfinitely. By ‘discrete’ we mean that the machine models considered are not analogue machines, but compute by means of distinct stages or in units of time. The paradigm of such models is, of course, Turing's original machine model. If we concentrate on this for a moment, the machine is considered to be running a program P perhaps on some natural number input n ∈ ℕ and is calculating P(n). Normally we say this is a successful computation if the machine halts after a finite number of stages and we may read off some designated form of output: ‘P(n)↓’ However if the machine fails to halt after a finite time it may be exhibiting a variety of behaviours on its tape. Mathematically we may ask what happens ‘in the limit’ as the number of stages approaches ω. The machine may of course go haywire, and simply be rewriting a particular cell infinitely often, or else the Read/Write head may go ‘off to infinity’ as it moves inexorably down the tape. These kind of considerations are behind the notion of ‘computation in the limit’ which we consider below.
Or, it may only rewrite finitely often to any cell on the tape, and leave something meaningful behind: an infinite string of 0, Is and thus an element of Cantor space 2ℕ. What kind of elements could be there?
- Type
- Chapter
- Information
- Turing's LegacyDevelopments from Turing's Ideas in Logic, pp. 493 - 529Publisher: Cambridge University PressPrint publication year: 2014
References
[1] , Admissible sets and structures, Perspectives in Mathematical Logic, Springer Verlag, 1975.
[2] , , and , Safe recursive set functions, submitted, 2012.
[3] and , Can Newtonian systems, bounded in space, time, mass and energy compute all functions?, Theoretical Computer Science, vol. 371 (2007), pp. 4-19.Google Scholar
[4] and , A strengthening of Jensens principles, The Journal of Symbolic Logic, vol. 45 (1980), no. 2, pp. 251-264.Google Scholar
[5] , , and , On a theory of computation and complexity over the real numbers, Notices of the American Mathematical Society. New Series, vol. 21 (1989), no. 1, pp. 1-46.Google Scholar
[6] , The truth is never simple, The Journal of Symbolic Logic, vol. 51 (1986), no. 3, pp. 663-681.Google Scholar
[7] , , , , , and , The basic theory of infinite time register machines, Archive for Mathematical Logic, vol. 49 (2010), no. 2, pp. 249-273.Google Scholar
[8] , Infinite time Turing machines and Borel reducibility, Mathematical theory and computational practice, Lecture Notes in Computer Science, vol. 5635, Springer, 2009, pp. 129-133.
[9] and , Infinite time decidable equivalence relation theory, Notre Dame Journal for Formal Logic, vol. 52 (2011), no. 2, pp. 203-228.Google Scholar
[10] , Effective Mathematics of the Uncountable, ch. Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals, to appear.
[11] , Computability: an introduction to recursive function theory, Cambridge University Press, 1980.
[12] , Building infinite machines, British Journal for the Philosophy of Science, vol. 52 (2001), no. 4, pp. 671-682.Google Scholar
[13] , Ordinal time Turing computation, Ph.D. thesis, Bristol, 2009.
[14] , , and , P ≠ NP ∩ co-NP for the infinite time Turing machines, Journal of Logic and Computation, vol. 15 (2005), pp. 577-592.Google Scholar
[15] , Constructibility, Perspectives in Mathematical Logic, Springer Verlag, Berlin, Heidelberg, 1984.
[16] Metarecursively enumerable sets and their metadegrees, The Journal of Symbolic Logic, vol. 33 (1968), pp. 389-411.Google Scholar
[17] , A revenge-immune solution to the semantic paradoxes, Journal of Philosophical Logic, vol. 32 (2003), no. 3, pp. 139-177.Google Scholar
[18] and , An elementary approach to the fine structure of L, The Bulletin of Symbolic Logic, vol. 3 (1997), no. 4, pp. 453-468.Google Scholar
[19] and , Two observations concerning infinite time Turing machines, BIWOC 2007 Report (, editor), Bonn, January 2007, Hausdorff Centre for Mathematics, also at http://www.logic.univie.ac.at/sdf/papers/joint.philip.ps, pp. 44-47.
[20] and , Hypermachines, The Journal of Symbolic Logic, vol. 76 (2011), no. 2, pp. 620-636.Google Scholar
[21] , On a proof of Mostowski's conjecture, Bulletin de l'Academie Polonaise des Sciences. Série des Sciences Mathématiques, Astronomiques et Physiques, vol. 8 (1960), pp. 571-575.Google Scholar
[22] and , Infinite time Turing machines, The Journal of Symbolic Logic, vol. 65 (2000), no. 2, pp. 567-604.Google Scholar
[23] , Post's problem for supertasks has both positive and negative solutions, Archive for Mathematical Logic, vol. 41 (2002), pp. 507-523.Google Scholar
[24] , , and , The complexity of qickly ORM-decidable sets, Computation and logic in the real world: Proceedings of CiE 2007, Siena ( and , editors), Lecture Notes in Computer Science, vol. 4497, Springer-Verlag, Berlin, 2007, pp. 488-496.
[25] and , Post's problem for ordinal register machines, Computation and logic in the real world: Proceedings of CiE2007, Siena ( and , editors), Lecture Notes in Computer Science, vol. 4497, Springer-Verlag, Berlin, 2007, pp. 358-367.
[26] and , Post's problem for ordinal register machines: an explicit approach, Annals of Pure and Applied Logic, vol. 160 (2009), no. 3, pp. 302-309.Google Scholar
[27] , , , and , Infinite time computable model theory, New computational paradigms ( et al., editors), Springer-Verlag, Berlin, 2008, pp. 521-557.
[28] and , Infinite time Turing machines with only one tape, Mathematical Logic Quarterly, vol. 47 (2001), no. 2, pp. 271-287.Google Scholar
[29] and , Pf ≠ NPf almost everywhere, Mathematical Logic Quarterly, vol. 49 (2003), no. 5, pp. 536-540.Google Scholar
[30] , Analytic determinacy and 0#, The Journal of Symbolic Logic, vol. 43 (1978), no. 4, pp. 684-693.Google Scholar
[31] , Notes on naive semantics, Journal of Philosophical Logic, vol. 11 (1982), pp. 61-102.Google Scholar
[32] , Recursion-theoretic hierarchies, Ω Series in Mathematical Logic, Springer, Berlin, 1978.
[33] and , On Kleene degrees of analytic sets, Proceedings of the Kleene symposium (, , and , editors), Studies in Logic, North-Holland, 1980, pp. 347-352.
[34] , On Spector classes, Cabal seminar 76–77 ( and , editors), Lecture Notes in Mathematics Series, vol. 689, Springer, 1978, pp. 245-278.
[35] , Recursive quantifiers and functionals of finite type I, Transactions of the American Mathematical Society, vol. 91 (1959), pp. 1-52.Google Scholar
[36] , Turing-machine computable functionals of finite type I, Proceedings of the 1960 conference on Logic, Methodology and Philosophy of Science, Stanford University Press, 1962, pp. 38-45.
[37] , Turing-machine computable functionals of finite type II, Proceedings of the London Mathematical Society, vol. 12 (1962), pp. 245-258.Google Scholar
[38] , Recursive quantifiers and functionals of finite type II, Transactions of the American Mathematical Society, vol. 108 (1963), pp. 106-142.Google Scholar
[39] , Recursive functionals and quantifiers of finite types revisited, Generalized Recursion Theory II, Proceedings 2nd Scandinavian Logic Symposium, Oslo, 1977, Studies in Logic and Foundations of Mathematics, vol. 94, North-Holland, Amsterdam, New York, 1978, pp. 185-222.
[40] , Magister thesis, ILLC Amsterdam, 2007.
[41] , Turing computation on ordinals, The Bulletin of Symbolic Logic, vol. 11 (2005), pp. 377-397.Google Scholar
[42] and , Ordinal computations, Mathematical Structures in Computer Science, vol. 16 (2006), no. 5, pp. 867-884.Google Scholar
[43] and , An enhanced theory of infinite time register machines, Logic and the theory of algorithms ( et al., editors), Lecture Notes in Computer Science, vol. 5028, Springer, 2008, Swansea, pp. 306-315.
[44] and , Ordinal machines and admissible recursion theory, Annals of Pure and Applied Logic, vol. 160 (2009), no. 3, pp. 310-318.Google Scholar
[45] , Towards a theory of infinite time Blum–Shub–Smale machines, CiE 2012 Proceedings, 2012.
[46] and , Computing the recursive truth predicate on ordinal register machines, Logical approaches to computational barriers ( et al., editors), Computer Science Report Series, Swansea, 2006, p. 21.
[47] and , A generalised dynamical system, infinite time register machines, and -CA0, Proceedings of CiE 2011, Sofia (, editor), 2011.
[48] , Transfinite recursion on admissible ordinals I, II, The Journal of Symbolic Logic, vol. 29 (1964), pp. 161-162.Google Scholar
[49] , Transfinite computability (abstract), Notices of the American Mathematical Society, vol. 10 (1963), p. 286.Google Scholar
[50] , Revision sequences and computers with an infinite amount of time, Journal of Logic and Computation, vol. 11 (2001), pp. 25-40.Google Scholar
[51] , Space bounds for infinitary computations, Logical approaches to computational barriers, CiE 2006 ( et al., editors), Lecture Notes in Computer Science, vol. 3988, Springer-Verlag, 2006, pp. 319-329.
[52] , Well founded iterations of infinite time turing machines, Ways of proof theory (, editor), Ontos, 2010.
[53] , The theory of transfinite recursion, Bulletin of the American Mathematical Society, vol. 67 (1961), pp. 575-578.Google Scholar
[54] , Computation: Finite and infinite machines, Prentice-Hall, 1967.
[55] and , The limits of determinacy in second order number theory, Proceedings of the London Mathematical Society, (to appear).
[56] , Descriptive set theory, Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 1980.
[57] , Turing's models, in this volume, 2012.
[58] , Foundations of recursion theory, Ph.D. thesis, Stanford, 1966.
[59] , Trial and error predicates and the solution to a problem of Mostowski, The Journal of Symbolic Logic, vol. 30 (1965), pp. 49-57.Google Scholar
[60] , An ordinal analysis of parameter-free comprehension, Archive for Mathematical Logic, vol. 44 (2005), no. 3, pp. 263-362.Google Scholar
[61] , Recursive function theory, Higher Mathematics, McGraw, 1967.
[62] , Post's problem, admissible ordinals and regularity, Transactions of the American Mathematical Society, vol. 124 (1966), pp. 1-23.Google Scholar
[63] , Higher recursion theory, Perspectives in Mathematical Logic, Springer Verlag, 1990.
[64] and , The α-finite injury method, Annals of Mathematical Logic, vol. 4 (1972), pp. 343-367.Google Scholar
[65] , P ≠ NP for infinite time Turing machines, Monatshefte für Mathematik, vol. 139 (2003), no. 4, pp. 335-340.Google Scholar
[66] and , Fine structure theory, Handbook of set theory (, , and , editors), vol. 1, Springer Verlag, Heidelberg, New York, 2010, pp. 605-656.
[67] and , Computability of recursive functionals, Journal of the Association of Computing Machinery, vol. 10 (1963), pp. 217-255.Google Scholar
[68] , Splitting an α recursively enumerable set, Transactions of the American Mathematical Society, vol. 204 (1975), pp. 65-78.Google Scholar
[69] , The recursively enumerable α-degrees are dense, Annals of Mathematical Logic, vol. 9 (1976), pp. 123-155.Google Scholar
[70] , Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer, January 1999.
[71] , Determinacy and type-2 recursion, The Journal of Symbolic Logic, vol. 36 (1971), p. 374.Google Scholar
[72] , Hyperarithmetic quantifiers, Fundamenta Mathematicae, vol. 48 (1959), pp. 313-320.Google Scholar
[73] , Analytic sets and Borel isomorphisms, Fundamenta Mathematicae, vol. 108 (1980), pp. 83-88.Google Scholar
[74] , On the recursive functions of ordinal numbers, Journal of the Mathematical Society of Japan, vol. 12 (1960), pp. 119-128.Google Scholar
[75] , On the partial recursive functions of ordinal numbers, Journal of the Mathematical Society of Japan, vol. 16(1964), pp. 1-31.Google Scholar
[76] , Minimality arguments in the infinite time Turing degrees, Sets and proofs: Proceedings of the Logic Colloquium 1997, Leeds ( and , editors), London Mathematical Society Lecture Note Series, vol. 258, Cambridge University Press, 1999.
[77] , Eventually Infinite Time Turing degrees: infinite time decidable reals, The Journal of Symbolic Logic, vol. 65 (2000), no. 3, pp. 1193-1203.Google Scholar
[78] , The length of infinite time Turing machine computations, Bulletin of the London Mathematical Society, vol. 32 (2000), pp. 129-136.Google Scholar
[79] , Post's and other problems in higher type supertasks, Classical and new paradigms of computation and their complexity hierarchies, papers of the conference Foundations of the Formal Sciences III (, , and , editors), Trends in Logic, vol. 23, Kluwer, October 2004, pp. 223-237.
[80] , Bounding lemmata for non-deterministic halting times of transfinite Turing machines, Theoretical Computer Science, vol. 394 (2008), pp. 223-228.Google Scholar
[81] , Turing unbound: The extent of computations in Malament–Hogarth spacetimes, British Journal for the Philosophy of Science, vol. 15 (2008), no. 4, pp. 659-674.Google Scholar
[82] , Ultimate truth vis à vis stable truth, The Review of Symbolic Logic, vol. 1 (2008), no. 1, pp. 126-142.Google Scholar
[83] , Characteristics of discrete transfinite Turing machine models: halting times, stabilization times, and normal form theorems, Theoretical Computer Science, vol. 410 (2009), pp. 426-442.Google Scholar
[84] , Determinacy in strong cardinal models, The Journal of Symbolic Logic, vol. 76 (2011), no. 2, pp. 719-728.Google Scholar
[85] , Weak systems of determinacy and arithmetical quasi-inductive definitions, The Journal of Symbolic Logic, vol. 76 (2011), no. 2, pp. 418-436.Google Scholar
- 5
- Cited by