Randomness, Computability, and Density
Status: published in the SIAM Journal
on Computing, vol. 31 (2002), pp. 1169 - 1183 (extended
abstract in the Proceedings
of STACS
2001, Lecture Notes in Computer Science 2010
(Springer, 2001)).
Availability: DVI, PostScript, and PDF
Abstract. We study effectively given positive reals (more
specifically, computably enumerable reals) under a measure of relative
randomness introduced by Solovay. This measure is called domination or
Solovay reducibility, and is defined by saying that alpha
dominates beta if there are a constant c and a partial
computable function f such that, for all positive rationals
q < alpha, f(q) converges,
f(q) < beta, and beta-f(q)
< c(alpha-q). The intuition is that an
approximating sequence for alpha generates one for
beta. It is not hard to show that if alpha dominates
beta then the initial segment complexity of alpha is at
least that of beta.
In this paper we are concerned with structural properties of the
degree structure generated by Solovay reducibility. We answer a
long-standing question in this area of investigation by proving the
density of the Solovay degrees. We also provide a new characterization
of the random c.e. reals in terms of splittings in the Solovay
degrees. Specifically, we show that the Solovay degrees of computably
enumerable reals are dense, that any incomplete Solovay degree splits
over any lesser degree, and that the join of any two incomplete
Solovay degrees is incomplete, so that the complete Solovay degree
does not split at all. The methodology is of some technical interest,
since it includes a priority argument in which the injuries are
themselves controlled by randomness considerations.
drh@math.uchicago.edu