Journal of Symbolic Logic 65 (3):1193-1203 (2000)

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the L ζ -stables. It also implies that the machines devised are "Σ 2 Complete" amongst all such other possible machines. It is shown that least upper bounds of an "eventual jump" hierarchy exist on an initial segment
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2586695
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: 55,981
Through your library

References found in this work BETA

Computability and Logic.George S. Boolos, John P. Burgess & Richard C. Jeffrey - 2003 - Bulletin of Symbolic Logic 9 (4):520-521.

Add more references

Citations of this work BETA

Guest Editors’ Introduction.Riccardo Bruni & Shawn Standefer - 2019 - Journal of Philosophical Logic 48 (1):1-9.
Ultimate Truth Vis- À- Vis Stable Truth.P. D. Welch - 2008 - Review of Symbolic Logic 1 (1):126-142.
Infinite Time Extensions of Kleene’s $${\Mathcal{O}}$$.Ansten Mørch Klev - 2009 - Archive for Mathematical Logic 48 (7):691-703.

Add more citations

Similar books and articles

Building Infinite Machines.E. B. Davies - 2001 - British Journal for the Philosophy of Science 52 (4):671-682.
Infinite Time Turing Machines.Joel David Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.
Is the Human Mind a Turing Machine?D. King - 1996 - Synthese 108 (3):379-89.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Is There a Nonrecursive Decidable Equational Theory?Benjamin Wells - 2002 - Minds and Machines 12 (2):301-324.
Infinite Time Turing Machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.


Added to PP index

Total views
39 ( #258,015 of 2,403,575 )

Recent downloads (6 months)
1 ( #551,240 of 2,403,575 )

How can I increase my downloads?


My notes