Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Infinite Time Turing Machines

  • Published:
Minds and Machines Aims and scope Submit manuscript

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

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

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.

    Google Scholar 

  • Chihara, C.S. (1965), ‘On the Possibility of Completing an Infinite Process’,Philosophical Review 74, pp. 74–87.

    Google Scholar 

  • Copeland, J. (1998a),Super Turing-Machines, Complexity 4, pp. 30–32.

    Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Google Scholar 

  • Feferman, S. and Spector, C. (1962), ‘Incompleteness Along Paths in Progressions of Theories’,The Journal of Symbolic Logic 27, pp. 383–390.

    Google Scholar 

  • Hamkins J.D. and Lewis A. (2000), ‘Infinite Time Turing Machines’,The Journal of Symbolic Logic 65(2), pp. 567–604.

    Google Scholar 

  • Hamkins J.D. and Seabold, D. (2001), ‘Infinite Time Turing Machines with Only One Tape’,Mathematical Logic Quarterly 47(2), pp. 271–287.

    Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Google Scholar 

  • Laraudogoitia, J.P. (1996), ‘A Beautiful Supertask’,Mind 105(417), pp. 81–84.

    Google Scholar 

  • Pitowsky, (1990), ‘The Physical Church Thesis and Physical Computational Complexity’,Iyyun 39, pp. 81–99.

  • Sacks, G.E. (1990),Higher Recursion Theory, Berlin, Springer.

    Google Scholar 

  • Soare, R.I. (1987),Recursively Enumerable Sets and Degrees, New York, Springer.

    Google Scholar 

  • Thomson, (1954-55), ‘Tasks and Super-Tasks’,Analysis XV, pp. 1–13.

    Google Scholar 

  • 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.

    Google Scholar 

  • Welch, P. (2000a), ‘The Lengths of Infinite time Turing Machine Computations’,Bulletin of the London Mathematical Society 32(2), pp. 129–136.

    Google Scholar 

  • Welch, P. (200b), ‘Eventually Infinite Time Turing Machine Degrees: Infinite tTime Decidable Reals’,Journal of Symbolic Logic 65(3), p. 11.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The City University of New York, New York, USA

    Joel David Hamkins

Authors
  1. Joel David Hamkins

    You can also search for this author inPubMed Google Scholar

Rights and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement


[8]ページ先頭

©2009-2025 Movatter.jp