On Relativization and the Existence of Turing Complete Sets
Lane A. Hemachandra, Sanjay K. Jain · UR Research (University of Rochester) · 1989
In this paper we consider the possibility that natural classes such as R and UP lack Turing complete sets. We prove that there exist relativized worlds in which R and UP do not have Turing complete sets. This extends the work of [Sip82] and [HH88], in which it was proven that there exist relativized worlds in which R and UP do not have many-one complete sets.