About Segment Complexity of Turing Reductions

From MaRDI portal





Given a class \(\mathcal F\) of non-decreasing functions from the set of natural numbers to itself, let \(\leq_{\mathcal F}\) be the restriction of Turing reducibility defined by the class of oracle Turing machines which for some \(f\) in \(\mathcal F\) and for all inputs \(x\), query their oracle only on places less than or equal to \(f(x)\). After introducing the relations \(\leq_{\mathcal F}\), the author gives conditions on \(\mathcal F\) which are equivalent to \(\leq_{\mathcal F}\) being reflexive and transitive and he shows that the structure of the power set of the natural numbers under inclusion can be embedded into the inclusion structure of the relations \(\leq_{\mathcal F}\) with countable \(\mathcal F\). Next, the author introduces a hierarchy of relations where every level of the hierarchy contains relations \(\leq_{\mathcal F}\) such that \(\mathcal F\) can be defined from the relations contained in the previous levels. Furthermore, the author relates the Kolmogorov complexity of initial prefixes of sets \(A\) and \(B\) where \(A\) is Turing reducible to \(B\) with use bound~\(f\). Finally the author shows that for countable \(\mathcal F\), Friedberg's jump inversion theorem fails with Turing reducibility replaced by \(\leq_{\mathcal F}\).











This page was built for publication: About Segment Complexity of Turing Reductions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4704660)