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 Cite Plain text    BibTeX    Formatted text Zotero EndNote Reference Manager RefWorks

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