Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Conservatively Approximable Functions
verfasst von : Sebastian Wyman
Erschienen in: Logical Foundations of Computer Science
Verlag: Springer Berlin Heidelberg
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
In the study of computable functions on the Cantor space 2
ℕ
, it is well-known that the image of such a function is an effectively closed set, or
$\Pi^0_1$
class and in fact a
decidable
closed set. Here a closed subset
Q
of the Cantor space is decidable if the set of finite strings
w
which have an extension in
Q
is a computable set. It was shown recently by Cenzer, Dashti and King that the set of itineraries of a computable function is also a decidable closed set. Now the set of itineraries of a continuous function is always a
subshift
, meaning that it is closed under prefixes. It was also shown that any decidable shift is the set of itineraries of some computable function on 2
ℕ
. This paper defines the new notion of a
conservatively approximable
function on the Cantor space in order to have a family of functions whose images, and itineraries, can be arbitrary
$\Pi^0_1$
classes.