Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
\(ITRM\)-Recognizability from Random Oracles
verfasst von : Merlin Carl
Erschienen in: Evolving Computability
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
By a theorem of Sacks, if a real \(x\) is recursive relative to all elements of a set of positive Lebesgue measure, \(x\) is recursive. This statement - and the analogous statement for non-meagerness instead of positive Lebesgue measure - has been shown to carry over to many models of transfinite computations in [7]. Here, we start exploring another analogue concerning recognizability rather than computability. We show that, for Infinite Time Register Machines (\(ITRM\)s), if a real \(x\) is recognizable relative to all elements of a non-meager Borel set \(Y\), then \(x\) is recognizable.