Computations with oracles: Generalized selection (Q2277251)

The class of Turing machines with an oracle is studied in this paper. An oracle is a partial one-place integer function. A function which is computed by the Turing machine with an oracle \({\mathcal F}\) is denoted as \(\{z\}^{{\mathcal F}}\). B(\({\mathcal F})=\{<z,x>:\{z\}^{{\mathcal F}}(x)\) is defined\(\}\). A set C is called \({\mathcal F}\)-denumerable if it is the domain of definition of an \({\mathcal F}\)-computing function. An integer set A is adapted to the oracle \({\mathcal F}\) if B(\({\mathcal F})\leq_ mA\) and the following condition holds true (conjugate election principle on A): \(\{\) x,y\(\}\cap A\neq \emptyset \to \{V_ A\}^{{\mathcal F}}(x,y)\in \{x,y\}\cap A\) for some \(V_ A\); the function \(\{V_ A\}^{{\mathcal F}}\) is called selecting. If B(\({\mathcal F})\) is adapted to \({\mathcal F}\), then \({\mathcal F}\) is called a regular oracle. The following statements hold true for regular oracles: 1. The union of finite or \({\mathcal F}\)-denumerable families of \({\mathcal F}\)- denumerable sets is \({\mathcal F}\)-denumerable. 2. The projection of an \({\mathcal F}\)-denumerable set is \({\mathcal F}\)- denumerable. 3. A function of an \({\mathcal F}\)-denumerable set is \({\mathcal F}\)-denumerable. 4. If a set and its addition are \({\mathcal F}\)-denumerable, then this set is \({\mathcal F}\)-decidable. The article is devoted to the question to what extent the selection properties on B(\({\mathcal F})\) listed above could be generalized to any set A adapted to \({\mathcal F}\).