The distribution of ITRM-recognizable reals

Annals of Pure and Applied Logic 165 (9):1403-1417 (2014)
  Copy   BIBTEX

Abstract

Infinite Time Register Machines are a well-established machine model for infinitary computations. Their computational strength relative to oracles is understood, see e.g. , and . We consider the notion of recognizability, which was first formulated for Infinite Time Turing Machines in [6] and applied to ITRM 's in [3]. A real x is ITRM -recognizable iff there is an ITRM -program P such that PyPy stops with output 1 iff y=xy=x, and otherwise stops with output 0. In [3], it is shown that the recognizable reals are not contained in the ITRM -computable reals. Here, we investigate in detail how the ITRM -recognizable reals are distributed along the canonical well-ordering

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2014.04.010

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 106,169

External links

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

Through your library

My notes

Similar books and articles

Eventually infinite time Turing machine degrees: Infinite time decidable reals.P. D. Welch - 2000 - Journal of Symbolic Logic 65 (3):1193-1203.
The basic theory of infinite time register machines.Merlin Carl, Tim Fischbach, Peter Koepke, Russell Miller, Miriam Nasfi & Gregor Weckbecker - 2010 - Archive for Mathematical Logic 49 (2):249-273.
Needed reals and recursion in generic reals.Andreas Blass - 2001 - Annals of Pure and Applied Logic 109 (1-2):77-88.
Random reals and possibly infinite computations Part I: Randomness in ∅'.Verónica Becher & Serge Grigorieff - 2005 - Journal of Symbolic Logic 70 (3):891-913.
Determinacy and the sharp function on the reals.Derrick Albert DuBose - 1991 - Annals of Pure and Applied Logic 54 (1):59-85.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Schnorr randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533-554.
A covering lemma for L(ℝ).Daniel W. Cunningham - 2002 - Archive for Mathematical Logic 41 (1):49-54.
Maximal pairs of c.e. reals in the computably Lipschitz degrees.Yun Fan & Liang Yu - 2011 - Annals of Pure and Applied Logic 162 (5):357-366.

Analytics

Added to PP
2015-01-22

Downloads
53 (#453,362)

6 months
15 (#211,851)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Add more citations

References found in this work

[Omnibus Review].Thomas Jech - 1992 - Journal of Symbolic Logic 57 (1):261-262.
Infinite time Turing machines.Joel David 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.
Infinite time Turing machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.

View all 6 references / Add more references