1987 | OriginalPaper | Buchkapitel
Recursion Theory on Baire’s Space
verfasst von : Prof. Dr. Klaus Weihrauch
Erschienen in: Computability
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
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 this chapter we lay the basis for a unified Type 2 recursion theory. Our investigations from Chapter 3.1 and especially Theorem 3.1.14 show that it suffices to study continuity and computability on Baire’s space B . We shall choose the set B = ℕℕ as our standard set on which we develop a theory of continuity (w.r.t. Baire’s topology) and of computability. The theory turns out to be formally similar to Type 1 recursion theory. Most definitions and theorems will appear in a topological and in a computational version in accordance with our previously explained program for Type 2 theory. First we introduce a representation $$ \hat \varphi $$ : B →[B → Bo] of the continuous functions from B to Bo which is effective: it satisfies the Type 2 utm-theorem and smn-theorem. From $$ \hat \varphi $$ we derive a representation φ : B →[B → B] where [B →B] is the set of continuous functions г: B → B the domains of which are the Gδ-subsets of B , and we derive a representation x: B→[B→ℕ] of the set of the continuous functions г: B → ℕ the domains of which are the open subsets of B . The representations φ and x satisfy the utm-theorem and the smn-theorem. As a counterpart of the recursively enumerable subsets in Type 1 theory we study the open and the computably open subsets of B. This Type 2 theory of open subsets of B is formally very similar to the Type 1 theory of the recursively enumerable sets.