The distribution of ITRM-recognizable reals

Cite This

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

This item appears in the following Collection(s)

Search KOPS


Browse

My Account