Speaker
Assylbek Issakhov
KazakhBritish Technical University
Talks at this conference:
Tuesday, 16:30, J336 
Types of minimal numberings with hyperimmune oracles 
Authors: Assylbek Issakhov and Fariza Rakymzhankyzy Let \(F\) be a family of total functions which is computable by an oracle \(A\), where \(A\) is an arbitrary set. A numbering \(\alpha:\omega\mapsto \mathcal F\) is called \(A\)computable if the binary function \(\alpha(n)(x)\) is \(A\)computable, [1]. We call a numbering \(\alpha\) decidable (resp., positive, and Friedberg) if equivalence relation \(\theta_{\alpha} = \{ (x,y) \mid \alpha (x) = \alpha (y) \}\) is computable (resp., c.e., and identity). An infinite set \(A\) is hyperimmune iff no recursive function majorizes \(A\). A degree is called hyperimmune if it contains a hyperimmune set, otherwise it is hyperimmune free. Every nonzero degree comparable with \(0'\) is hyperimmune. In [2] it was proved that there is a c.e. noncomputable set \(B\) such that \(B\leq_{T} A\) iff for all families \(S\) of sets, it is true that if \(S\) has an \(A\)computable Friedberg numbering, then \(S\) has infinitely many positive nondecidable \(A\)computable numberings. It is known that if \(\mathcal F\) is an infinite \(A\)computable family of total functions, where \(A\) is a hyperimmune set, then \(\mathcal F\) has infinitely many pairwise nonequivalent \(A\)computable Friedberg numberings, [3]. Let \(\mathcal F\) be an infinite \(A\)computable family of total functions, where \(A\) is a hyperimmune set. Then Theorem. \(\mathcal F\) has infinitely many pairwise nonequivalent positive nondecidable \(A\)computable numberings. Theorem. \(\mathcal F\) has infinitely many pairwise nonequivalent minimal nonpositive \(A\)computable numberings. We know that if \(\mathcal F\) is an infinite \(A\)computable family of total functions, where \(\emptyset' \leq_{T} A\), then the Rogers semilattice \(R_{A} (\mathcal F)\) contains an ideal without minimal elements, [4]. Now we are interested in investigating such property for the case with hyperimmune oracles. Bibliography
