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

Authors
Joel David Hamkins
Oxford University
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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI http://projecteuclid.org/euclid.jsl/1183746064
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,130
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

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.
Accelerating Turing Machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Super Turing-Machines.B. Jack Copeland - 1998 - Complexity 4 (1):30-32.

View all 36 citations / Add more citations

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 index
2017-02-21

Total views
12 ( #809,369 of 2,506,503 )

Recent downloads (6 months)
2 ( #277,244 of 2,506,503 )

How can I increase my downloads?

Downloads

My notes