Iterated relative recursive enumerability (Q1344547): Difference between revisions

A result of Soare and Stob asserts that for any non-recursive r.e. set \(C\), there exists a r.e.\([C]\) set \(A\) such that \(A \oplus C\) is not of r.e. degree. A set \(Y\) is called [of] \(m\)-REA (\(m\)-REA\([C]\)) [degree] iff it is [Turing equivalent to] the result of applying \(m\)-many iterated `hops' to the empty set (to \(C\)), where a hop is any function of the form \(X \mapsto X \oplus W^ X_ e\). The cited result is the special case \(m = 0\), \(n = 1\) of our Theorem. For \(m = 0,1\), and any \((m + 1)\)-REA set \(C\), if \(C\) is not of \(m\)-REA degree, then for all \(n\) there exists an \(n\)-r.e.\([C]\) set \(A\) such that \(A \oplus C\) is not of \((m + n)\)-REA degree. We conjecture that this holds also for \(m \geq 2\).