Journal of Symbolic Logic 65 (2):567-604 (2000)
| Authors |
|
| 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 |
Mark as duplicate
Export citation
Request removal from index
|
Download options
References found in this work BETA
No references found.
Citations of this work BETA
Hypercomputation and the Physical Church‐Turing Thesis.Paolo Cotogno - 2003 - British Journal for the Philosophy of Science 54 (2):181-223.
Do Accelerating Turing Machines Compute the Uncomputable?B. Jack Copeland & Oron Shagrir - 2011 - Minds and Machines 21 (2):221-239.
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.
Eventually Infinite Time Turing Machine Degrees: Infinite Time Decidable Reals.P. D. Welch - 2000 - Journal of Symbolic Logic 65 (3):1193-1203.
Eventually Infinite Time Turing Machine Degrees: Infinite Time Decidable Reals.P. D. Welch - 2000 - Journal of Symbolic Logic 65 (3):1193-1203.
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.
The Basic Theory of Infinite Time Register Machines.Merlin Carl, Tim Fischbach, Peter Koepke, Russell Miller, Miriam Nasfi & Gregor Weckbecker - 2010 - Archive for Mathematical Logic 49 (2):249-273.
Infinite Time Extensions of Kleene’s $${\mathcal{O}}$$.Ansten Mørch Klev - 2009 - Archive for Mathematical Logic 48 (7):691-703.
Observability of Turing Machines: A Refinement of the Theory of Computation.Yaroslav Sergeyev & Alfredo Garro - 2010 - Informatica 21 (3):425–454.
Post's Problem for Supertasks has Both Positive and Negative Solutions.Joel David Hamkins & Andrew Lewis - 2002 - Archive for Mathematical Logic 41 (6):507-523.
Turing Oracle Machines, Online Computing, and Three Displacements in Computability Theory.Robert I. Soare - 2009 - Annals of Pure and Applied Logic 160 (3):368-399.
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 )
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
