The halting problem relativized to complements

Author:
Louise Hay

Journal:
Proc. Amer. Math. Soc. **41** (1973), 583-587

MSC:
Primary 02F30; Secondary 02F25

MathSciNet review:
0327495

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let . It is shown that there exists a set of Turing degree such that is Turing-incomparable to whenever is an r.e. degree with , or or and is r.e. in 0'. This contrasts with the fact that is comparable to for almost all .

**[1]**J. C. E. Dekker and J. Myhill,*Retraceable sets*, Canad. J. Math.**10**(1958), 357–373. MR**0099292****[2]**Louise Hay,*The class of recursively enumerable subsets of a recursively enumerable set*, Pacific J. Math.**46**(1973), 167–183. MR**0392525****[3]**Carl G. Jockusch Jr.,*The degrees of bi-immune sets*, Z. Math. Logik Grundlagen Math.**15**(1969), 135–140. MR**0244043****[4]**Robert W. Robinson,*Interpolation and embedding in the recursively enumerable degrees*, Ann. of Math. (2)**93**(1971), 285–314. MR**0274286****[5]**Hartley Rogers Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462****[6]**Alan L. Selman,*Applications of forcing to the degree-theory of the arithmetical hierarchy*, Proc. London Math. Soc. (3)**25**(1972), 586–602. MR**0314604****[7]**-,*Relativized halting problems*(to appear).**[8]**J. R. Shoenfield,*On degrees of unsolvability*, Ann. of Math. (2)**69**(1959), 644–653. MR**0105355****[9]**John Stillwell,*Decidability of the “almost all” theory of degrees*, J. Symbolic Logic**37**(1972), 501–506. MR**0349369**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
02F30,
02F25

Retrieve articles in all journals with MSC: 02F30, 02F25

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9939-1973-0327495-X

Article copyright:
© Copyright 1973
American Mathematical Society