JavaScript is disabled for your browser. Some features of this site may not work without it.

Iterated relative recursive enumerability

Cholak, Peter A.; Hinman, Peter G.

Cholak, Peter A.; Hinman, Peter G.

1994-10

Citation:Cholak, Peter A.; Hinman, Peter G.; (1994). "Iterated relative recursive enumerability." Archive for Mathematical Logic 33 (5): 321-346. <http://hdl.handle.net/2027.42/46068>

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.