Iterated relative recursive enumerability
Tóm tắt
A result of Soare and Stob asserts that for any non-recursive r.e. setC, there exists a r.e.[C] setA such thatA⊕C is not of r.e. degree. A setY is called [of]m-REA (m-REA[C] [degree] iff it is [Turing equivalent to] the result of applyingm-many iterated ‘hops’ to the empty set (toC), where a hop is any function of the formX→X ⊕W
e
X
. The cited result is the special casem=0,n=1 of our Theorem. Form=0,1, and any (m+1)-REA setC, ifC is not ofm-REA degree, then for alln there exists an-r.e.[C] setA such thatA ⊕C is not of (m+n)-REA degree. We conjecture that this holds also form≥2.
Tài liệu tham khảo
[ChHi] Cholak, P.A., Hinman, P.G.: Iterated Relative Recursive Enumerability (abstract). Abstr. Am. Math. Soc.881, 347 (1993)
[JoSh1] Jockusch, C.G., Shore, R.A.: Pseudo-jump operators. I: the r.e. case. Trans Amer. Math. Soc.275, 599–609 (1983)
[JoSh2] Jockusch, C.G., Shore, R.A.: Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers. Jour. Sympb. Log.49, 1205–1236 (1984)
[SoSt] Soare, R.I., Stob, M.: Relative Recursive Enumerability. In: Stern, J. (ed.) Proceedings of the Herbrand Symposium: Logic Colloqium '81, pp. 299–324. Amsterdam: North-Holland 1982
[So] Soare, R.I.: Recursively enumerable sets and degrees, xviii+437 pp. Berlin Heidelberg: Springer 1987