Randomness, Computability, and Density

by Rod G. Downey, Denis R. Hirschfeldt, and André Nies

Status: published in the SIAM Journal on Computing 31 (2002) 1169 - 1183.

Availability: journal version and preprint

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 α dominates β if there are a constant c and a partial computable function f such that, for all positive rationals q < α, f(q) converges, f(q) < β, and β-f(q) < c(α-q). The intuition is that an approximating sequence for α generates one for β. It is not hard to show that if α dominates β then the initial segment complexity of α is at least that of β.

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