Iterated relative recursive enumerability

Abstract

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 ⊕ 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 → X ⊕ W e X . 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 a n -r.e.[ C ] set A such that A ⊕ C is not of ( m+n )-REA degree. We conjecture that this holds also for m ≥2.