×

Recursion theoretic operators and morphisms on numbered sets. (English) Zbl 0548.03023

The paper is concerned with computable operators on type 2 sets like \(P\omega\), \(P\omega^ 2\), and \(T^{\omega}\). Standard continuity and computability on \(P\omega\) derived from the theory of complete partial orders is taken as the basis. Two embeddings of \(P\omega\) into \(P\omega^ 2\) are considered, \(A\to A':=<A,\emptyset >\) inducing Scott’s topology on \(P\omega\), and \(A\to A^*:=<A,\bar A>\) inducing Cantor’s topology on \(P\omega\). The computable operators on \(P\omega^ 2\) induce four different kinds of partial operators on \(P\omega\) among which are Turing operators and enumeration operators. These operators are compared with each other and with formerly defined ones. Canonical numberings of the computable operators are introduced and shown to be equivalent to known standard numberings. Finally, an extension theorem for Turing operators is proved. The paper enriches the theory of type 2 computability and provides some new interesting insights.
Reviewer: K.Weihrauch

MSC:

03D65 Higher-type and set recursion theory
03D45 Theory of numerations, effectively presented structures
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
03D30 Other degrees and reducibilities in computability and recursion theory
PDFBibTeX XMLCite
Full Text: DOI EuDML