The distribution of ITRM-recognizable reals

Abstract

Infinite Time Register Machines ($ITRM$'s) are a well-established machine model for infinitary computations. Their computational strength relative to oracles is understood, see e.g. \cite{Koe}, \cite{KoeWe} and \cite{KoeMi}. We consider the notion of recognizability, which was first formulated for Infinite Time Turing Machines in \cite{HamLew} and applied to $ITRM$'s in \cite{ITRM}. A real $x$ is $ITRM$-recognizable iff there is an $ITRM$-program $P$ such that $P^{y}$ stops with output $1$ iff $y=x$, and otherwise stops with output $0$. In \cite{ITRM}, it is shown that the recognizable reals are not contained in the computable reals. Here, we investigate in detail how the $ITRM$-recognizable reals are distributed along the canonical well-ordering $<{L}$ of G"odel's constructible hierarchy $L$. In particular, we prove that the recognizable reals have gaps in $<{L}$,that there is no universal $ITRM$ in terms of recognizability and consider a relativized notion of recognizability.