Post’s Problem for ordinal register machines: An explicit approach

Annals of Pure and Applied Logic 160 (3):302-309 (2009)

Authors
Joel David Hamkins
Oxford University
Abstract
We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2009.01.004
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 39,545
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

Infinite Time Turing Machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.
Turing Computations on Ordinals.Peter Koepke - 2005 - Bulletin of Symbolic Logic 11 (3):377-397.
The Α-Finite Injury Method.G. E. Sacks & S. G. Simpson - 1972 - Annals of Mathematical Logic 4 (4):343-367.
The Alpha-Finite Injury Method.G. E. Sacks - 1972 - Annals of Mathematical Logic 4 (4):343.

View all 7 references / Add more references

Citations of this work BETA

Discrete Transfinite Computation Models.Philip D. Welch - 2011 - In S. B. Cooper & Andrea Sorbi (eds.), Computability in Context: Computation and Logic in the Real World. World Scientific. pp. 375--414.

Add more citations

Similar books and articles

Register Computations on Ordinals.Peter Koepke & Ryan Siders - 2008 - Archive for Mathematical Logic 47 (6):529-548.
Infinite Time Turing Machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.
Infinite Time Turing Machines.Joel David Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.
A Model-Theoretic Approach to Ordinal Analysis.Jeremy Avigad & Richard Sommer - 1997 - Bulletin of Symbolic Logic 3 (1):17-52.
Assignment of Ordinals to Patterns of Resemblance.Gunnar Wilken - 2007 - Journal of Symbolic Logic 72 (2):704 - 720.
Ordinal Arithmetic and Sigma_{1}-Elementarity.Timothy J. Carlson - 1999 - Archive for Mathematical Logic 38 (7):449-460.
On a Certain Class Ofm-Address Machines.Jerzy Ejsmund - 1971 - Studia Logica 28 (1):131 - 137.
A Dao of Technology?Barry Allen - 2010 - Dao: A Journal of Comparative Philosophy 9 (2):151-160.
On Unlimited Register Machines.R. J. Baxter - 1972 - Mathematical Logic Quarterly 18 (7):97-102.
The Bachmann-Howard Structure in Terms of Σ1-Elementarity.Gunnar Wilken - 2006 - Archive for Mathematical Logic 45 (7):807-829.

Analytics

Added to PP index
2013-12-22

Total views
22 ( #345,426 of 2,325,369 )

Recent downloads (6 months)
1 ( #917,442 of 2,325,369 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature