Infinite Time Turing Machines

Journal of Symbolic Logic 65 (2):567-604 (2000)
  Copy   BIBTEX

Abstract

We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Every $\Pi^1_1$ set, for example, is decidable by such machines, and the semi-decidable sets form a portion of the $\Delta^1_2$ sets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 86,168

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Infinite time Turing machines.Joel David Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.
Infinite time Turing machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.
Infinite Time Turing Machines With Only One Tape.D. E. Seabold & J. D. Hamkins - 2001 - Mathematical Logic Quarterly 47 (2):271-287.
Infinite Computations with Random Oracles.Merlin Carl & Philipp Schlicht - 2017 - Notre Dame Journal of Formal Logic 58 (2):249-270.
Infinite time extensions of Kleene’s $${\mathcal{O}}$$.Ansten Mørch Klev - 2009 - Archive for Mathematical Logic 48 (7):691-703.
Hypermachines.Sy-David Friedman & P. D. Welch - 2011 - Journal of Symbolic Logic 76 (2):620 - 636.
Logically possible machines.Eric Steinhart - 2002 - Minds and Machines 12 (2):259-280.
Supermachines and superminds.Eric Steinhart - 2003 - Minds and Machines 13 (1):155-186.
Infinite Time Turing Machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):521-539.

Analytics

Added to PP
2017-02-21

Downloads
13 (#849,957)

6 months
1 (#863,981)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Joel David Hamkins
Oxford University

Citations of this work

Accelerating Turing machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Infinite time Turing machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.
Hypercomputation and the Physical Church‐Turing Thesis.Paolo Cotogno - 2003 - British Journal for the Philosophy of Science 54 (2):181-223.
SAD computers and two versions of the Church–Turing thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.

View all 41 citations / Add more citations

References found in this work

No references found.

Add more references