Archive for Mathematical Logic 49 (2):249-273 (2010)

Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all ${\Pi^1_1}$ sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRM-clockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not ${n \in r}$ with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs
Keywords Ordinal computability  Hypercomputation  Infinitary computation  Register machine
Categories (categorize this paper)
DOI 10.1007/s00153-009-0167-x
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: 72,634
Through your library

References found in this work BETA

Infinite Time Turing Machines.Joel Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.
The Fine Structure of the Constructible Hierarchy.R. Björn Jensen - 1972 - Annals of Mathematical Logic 4 (3):229.
Turing Computations on Ordinals.Peter Koepke - 2005 - Bulletin of Symbolic Logic 11 (3):377-397.
Register Computations on Ordinals.Peter Koepke & Ryan Siders - 2008 - Archive for Mathematical Logic 47 (6):529-548.
Ordinal Machines and Admissible Recursion Theory.Peter Koepke & Benjamin Seyfferth - 2009 - Annals of Pure and Applied Logic 160 (3):310-318.

Add more references

Citations of this work BETA

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.

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.
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.
Logically Possible Machines.Eric Steinhart - 2002 - Minds and Machines 12 (2):259-280.
Hypermachines.Sy-David Friedman & P. D. Welch - 2011 - Journal of Symbolic Logic 76 (2):620 - 636.
Register System and General Principles of Register Interoperability.Andrejus Novikovas - 2010 - Jurisprudencija: Mokslo darbu žurnalas 122 (4):357-371.
Supermachines and Superminds.Eric Steinhart - 2003 - Minds and Machines 13 (1):155-186.
Infinite Time Extensions of Kleene’s $${\mathcal{O}}$$.Ansten Mørch Klev - 2009 - Archive for Mathematical Logic 48 (7):691-703.
Accelerating Turing Machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
On the Possibility, or Otherwise, of Hypercomputation.Philip D. Welch - 2004 - British Journal for the Philosophy of Science 55 (4):739-746.


Added to PP index

Total views
70 ( #167,633 of 2,533,674 )

Recent downloads (6 months)
1 ( #389,210 of 2,533,674 )

How can I increase my downloads?


My notes