View Related Documents

Abstract

A c.e. real x is Solovay reducible (S-reducible) to another c.e. real y if y is at least as difficult to be approximated as x. In this case, y is at least as random as x. Thus, the S-reducibility classifies relative randomness of c.e. reals such that the c.e. random reals are complete in the class of c.e. reals under the S-reducibility. In this paper we investigate extensions of the S-reducibility outside the c.e. reals. We show that the straightforward extension does not behave satisfactorily. Then we introduce two new extensions which coincide with the S-reducibility on the c.e. reals and behave reasonably outside the c.e. reals. Both of these extensions imply the rH-reducibility of Downey, Hirschfeldt and LaForte [6]. At last we show that even under the rH-reducibility the computably approximable random reals cannot be characterized as complete elements of this reduction.

Fulltext Preview

Image of the first page of the fulltext document