KOPS - The Institutional Repository of the University of Konstanz

# The distribution of ITRM-recognizable reals

## Files in this item

Files Size Format View

There are no files associated with this item.

CARL, Merlin, 2012. The distribution of ITRM-recognizable reals

@unpublished{Carl2012distr-21349, title={The distribution of ITRM-recognizable reals}, year={2012}, author={Carl, Merlin} }

The distribution of ITRM-recognizable reals 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}\$,<br />that there is no universal \$ITRM\$ in terms of recognizability and consider a relativized notion of recognizability. 2013-02-06T10:01:00Z eng Carl, Merlin terms-of-use Carl, Merlin 2012 2013-02-06T10:01:00Z