326Accesses
32Citations
Abstract
Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.References
Buchi, J.R. (1962), Logic, Methodology and Philosophy and Science, inProc.1960 Int.Congr., Vol. 1 of 1, Stanford, CA: Stanford University Press.
Chihara, C.S. (1965), ‘On the Possibility of Completing an Infinite Process’,Philosophical Review 74, pp. 74–87.
Copeland, J. (1998a),Super Turing-Machines, Complexity 4, pp. 30–32.
Copeland, J. (1998b), Even TuringMachines Can Compute Uncomputable Functions, in C. Calude, J. Casti, M. Dinneen, eds,Unconventional Models of Computation, London: Springer, pp. 150–164.
Copeland, J. (2002), Accelerating TuringMachines, Minds and Machines, in C. Cleland, ed.,Special Issue on Effective Procedures, (in press).
Earman, J. (1995), Bangs, Crunches, Whimpers and Shrieks: Singularities and Acausalities in Relativistic Spacetimes, Oxford University Press, New York: The Clarendon Press.
Earman J. and Norton, J.D. (1993), ‘Forever is a Day: Supertasks in Pitowski and Malament-Hogarth Spacetimes’,Philos.Sci. 60(1), pp. 22–42.
Feferman, S. and Spector, C. (1962), ‘Incompleteness Along Paths in Progressions of Theories’,The Journal of Symbolic Logic 27, pp. 383–390.
Hamkins J.D. and Lewis A. (2000), ‘Infinite Time Turing Machines’,The Journal of Symbolic Logic 65(2), pp. 567–604.
Hamkins J.D. and Seabold, D. (2001), ‘Infinite Time Turing Machines with Only One Tape’,Mathematical Logic Quarterly 47(2), pp. 271–287.
Hamkins J.D. and Lewis, A. (2002) ‘Post's Problem for Supertasks Has Both Positive and Negative Solutions’,Archive for Mathematical Logic 41(6), pp. 507–523.
Hogarth, (1992), ‘Does General Relativity Allow an Observer to View an Eternity in a Finite Time?’Foundations of Physics Letters 5, pp. 173–181.
Hogarth, (1994), ‘Non-Turing Computers and Non-Turing Computability,’ in D. Hull, M. Forbes and R.B. Burian, eds., Vol. 1 ofEast Lansing: Philosophy of Science Association, pp. 126–138.
Löwe, B. (2001), ‘Revision Sequences and Computers with an Infinite Amount of Time’,Logic Comput. 11(1), pp. 25–40.
Laraudogoitia, J.P. (1996), ‘A Beautiful Supertask’,Mind 105(417), pp. 81–84.
Pitowsky, (1990), ‘The Physical Church Thesis and Physical Computational Complexity’,Iyyun 39, pp. 81–99.
Sacks, G.E. (1990),Higher Recursion Theory, Berlin, Springer.
Soare, R.I. (1987),Recursively Enumerable Sets and Degrees, New York, Springer.
Thomson, (1954-55), ‘Tasks and Super-Tasks’,Analysis XV, pp. 1–13.
Welch, P. (1999), ‘Friedman's Trick: Minimality Arguments in the Infinite Time Turing Degrees’, inSets and Proofs, Proceedings ASL Logic Colloquium, 258, pp. 425–436.
Welch, P. (2000a), ‘The Lengths of Infinite time Turing Machine Computations’,Bulletin of the London Mathematical Society 32(2), pp. 129–136.
Welch, P. (200b), ‘Eventually Infinite Time Turing Machine Degrees: Infinite tTime Decidable Reals’,Journal of Symbolic Logic 65(3), p. 11.
Author information
Authors and Affiliations
The City University of New York, New York, USA
Joel David Hamkins
- Joel David Hamkins
You can also search for this author inPubMed Google Scholar
Rights and permissions
About this article
Cite this article
Hamkins, J.D. Infinite Time Turing Machines.Minds and Machines12, 521–539 (2002). https://doi.org/10.1023/A:1021180801870
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative