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

Cite Plain text    BibTeX    Formatted text Zotero EndNote Reference Manager RefWorks

Options Edit Mark as duplicate Find it on Scholar Request removal from index Revision history