Archive for Mathematical Logic 47 (6):529-548 (2008)

We generalize ordinary register machines on natural numbers to machines whose registers contain arbitrary ordinals. Ordinal register machines are able to compute a recursive bounded truth predicate on the ordinals. The class of sets of ordinals which can be read off the truth predicate satisfies a natural theory SO. SO is the theory of the sets of ordinals in a model of the Zermelo-Fraenkel axioms ZFC. This allows the following characterization of computable sets: a set of ordinals is ordinal register computable if and only if it is an element of Gödel’s constructible universe L
Keywords Ordinal computability  Hypercomputation  Infinitary computation  Register machine
Categories (categorize this paper)
DOI 10.1007/s00153-008-0093-3
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: 62,505
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

The Consistency of the Continuum Hypothesis.Kurt Gödel - 1940 - Princeton University Press.
Infinite Time Turing Machines.Joel Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.
Turing Computations on Ordinals.Peter Koepke - 2005 - Bulletin of Symbolic Logic 11 (3):377-397.

Add more references

Citations of this work BETA

On the Number of Gods.Eric Steinhart - 2012 - International Journal for Philosophy of Religion 72 (2):75-83.
Infinite Computations with Random Oracles.Merlin Carl & Philipp Schlicht - 2017 - Notre Dame Journal of Formal Logic 58 (2):249-270.

View all 9 citations / Add more citations

Similar books and articles

Turing Computations on Ordinals.Peter Koepke - 2005 - Bulletin of Symbolic Logic 11 (3):377-397.
Operating on the Universe.Narciso Garcia - 1988 - Archive for Mathematical Logic 27 (1):61-68.
Dynamic Ordinal Analysis.Arnold Beckmann - 2003 - Archive for Mathematical Logic 42 (4):303-334.
On Series of Ordinals and Combinatorics.James P. Jones, Hilbert Levitz & Warren D. Nichols - 1997 - Mathematical Logic Quarterly 43 (1):121-133.
A Comparison of Two Systems of Ordinal Notations.Harold Simmons - 2004 - Archive for Mathematical Logic 43 (1):65-83.
Register System and General Principles of Register Interoperability.Andrejus Novikovas - 2010 - Jurisprudencija: Mokslo darbu žurnalas 122 (4):357-371.
Order Types of Ordinals in Models of Set Theory.John E. Hutchinson - 1976 - Journal of Symbolic Logic 41 (2):489-502.
Fruitful and Helpful Ordinal Functions.Harold Simmons - 2008 - Archive for Mathematical Logic 47 (7-8):677-709.
Computation and Hypercomputation.Mike Stannett - 2003 - Minds and Machines 13 (1):115-153.
Ordinal Arithmetic and $\sigma_{1}$ -Elementarity.Timothy J. Carlson - 1999 - Archive for Mathematical Logic 38 (7):449-460.


Added to PP index

Total views
37 ( #289,871 of 2,446,497 )

Recent downloads (6 months)
1 ( #456,659 of 2,446,497 )

How can I increase my downloads?


My notes