Type of Publication: | Preprint |
Author: | Carl, Merlin |
Year of publication: | 2012 |
ArXiv-ID: | arXiv:1208.1901 |
Summary: |
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. |
Subject (DDC): | 510 Mathematics |
Bibliography of Konstanz: | Yes |
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} }