Randomness and Reducibility

by Rod Downey, Denis R. Hirschfeldt, and Geoff LaForte

Journal of Computer and System Sciences 68 (2004) 96 - 114 (extended abstract in the Proceedings of MFCS 2001, Lecture Notes in Computer Science 2136 (Springer, 2001)).

preprint version (PDF)

journal version (PDF)

Abstract. How random is a real? Given two reals, which is more random? If we partition reals into equivalence classes of reals of the "same degrees of randomness", what does the resulting structure look like? The goal of this paper is to look at questions like these, specifically by studying the properties of reducibilities that act as measures of relative randomness, as embodied in the concept of initial-segment complexity. One such reducibility, called domination or Solovay reducibility, has proved to be a powerful tool in the study of randomness of effectively presented reals. Motivated by certain shortcomings of Solovay reducibility, we introduce two new reducibilities and study, among other things, the relationships between these various measures of relative randomness.