The distribution of ITRM-recognizable reals


Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

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 deposit-license eng Carl, Merlin Carl, Merlin 2012 2013-02-06T10:01:00Z

Das Dokument erscheint in:

KOPS Suche


Mein Benutzerkonto