Ordinal machines and admissible recursion theory

Annals of Pure and Applied Logic 160 (3):310-318 (2009)


We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, respectively. We emphasize the algorithmic approach to admissible recursion theory by indicating how the proof of the Sacks–Simpson theorem, i.e., the solution of Post’s problem in α-recursion theory, could be based on α-machines, without involving constructibility theory

Download options


    Upload a copy of this work     Papers currently archived: 72,879

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

9 (#959,112)

6 months
1 (#386,016)

Historical graph of downloads
How can I increase my downloads?

References found in this work

The Α-Finite Injury Method.G. E. Sacks & S. G. Simpson - 1972 - Annals of Mathematical Logic 4 (4):343-367.
The Fine Structure of the Constructible Hierarchy.R. Björn Jensen - 1972 - Annals of Mathematical Logic 4 (3):229.
Metarecursive Sets.G. Kreisel & Gerald E. Sacks - 1965 - Journal of Symbolic Logic 30 (3):318-338.
Turing Computations on Ordinals.Peter Koepke - 2005 - Bulletin of Symbolic Logic 11 (3):377-397.
Metarecursively Enumerable Sets and Their Metadegrees.Graham C. Driscoll - 1968 - Journal of Symbolic Logic 33 (3):389-411.

View all 10 references / Add more references

Citations of this work

Supertasks.Jon Pérez Laraudogoitia - 2008 - Stanford Encyclopedia of Philosophy.
Infinite Computations with Random Oracles.Merlin Carl & Philipp Schlicht - 2017 - Notre Dame Journal of Formal Logic 58 (2):249-270.
Taming Koepke's Zoo II: Register Machines.Merlin Carl - 2022 - Annals of Pure and Applied Logic 173 (3):103041.
The Computational Strengths of Α-Tape Infinite Time Turing Machines.Benjamin Rin - 2014 - Annals of Pure and Applied Logic 165 (9):1501-1511.

View all 7 citations / Add more citations

Similar books and articles

Register Computations on Ordinals.Peter Koepke & Ryan Siders - 2008 - Archive for Mathematical Logic 47 (6):529-548.
Generalized Recursion Theory Ii: Proceedings of the 1977 Oslo Symposium.Jens Erik Fenstad, R. O. Gandy & Gerald E. Sacks (eds.) - 1978 - Sole Distributors for the U.S.A. And Canada, Elsevier North-Holland.
Ptykes in GödelsT Und Definierbarkeit von Ordinalzahlen.Peter Päppinghaus - 1989 - Archive for Mathematical Logic 28 (2):119-141.
HC of an Admissible Set.Sy D. Friedman - 1979 - Journal of Symbolic Logic 44 (1):95-102.
Locally Countable Models of Σ1-Separation.Fred G. Abramson - 1981 - Journal of Symbolic Logic 46 (1):96 - 100.
The Pure Part of HYP(M).Mark Nadel & Jonathan Stavi - 1977 - Journal of Symbolic Logic 42 (1):33-46.