Randomness and Reducibility
Status: published in the Journal of Computer and System
Sciences, vol. 68 (2004), pp. 96 - 114
(extended
abstract in the proceedings
of MFCS 2001, Lecture Notes in Computer Science 2136
(Springer, 2001)).
Availability: DVI, PostScript, and 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.
drh@math.uchicago.edu