Randomness, Computability, and Density.
We study effectively given positive reals (more specifically, computably enumerable reals) under a measure of relative randomness introduced by Solovay [manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1975] and studied by Calude, Hertling, Khoussainov, and Wang [Theoret. Comput. Sci., 255 (2001), pp. 125--149], Calude [Theoret. Comput. Sci., 271 (2002), pp. 3--14], Kucera and Slaman [SIAM J. Comput., 31 (2002), pp. 199--211], and Downey, Hirschfeldt, and LaForte [Mathematical Foundations of Computer Science 2001, Springer-Verlag, Berlin, 2001, pp. 316--327], among others. 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 $\varphi$ such that for all positive rationals $q<\alpha$ we have $\varphi(q)\!\downarrow<\beta$ and $\beta- \varphi(q) \leqslant c(\alpha- q)$. The intuition is that an approximating sequence for $\alpha$ generates one for $\beta$ whose rate of convergence is not much slower than that of the original sequence. 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 natural question in this area of investigation by proving the density of the Solovay degrees. We also provide a new characterization of the random computably enumerable 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.
Introduction
In this paper we are concerned with eectively generated reals in the interval (0; 1] and
their relative randomness. In what follows, real and rational will mean positive real
and positive rational, respectively. It will be convenient to work modulo 1, that is,
identifying and we do this below without
further comment.
Our basic objects are reals that are limits of computable increasing sequences of ratio-
nals. We call such reals computably enumerable (c.e.), though they have also been called
recursively enumerable, left computable (by Ambos-Spies, Weihrauch, and Zheng [1]),
and, together with the limits of computable decreasing sequences of rationals, semicom-
putable. If, in addition to the existence of a computable increasing sequence q
rationals with limit , there is a total computable function f such that  q f(n) < 2 n
for all n 2 !, then  is called computable. These and related concepts have been
widely studied. In addition to the papers and books mentioned elsewhere in this intro-
duction, we may cite, among others, early work of Rice [24], Lachlan [19], Soare [27],
and Cetin [8], and more recent papers by Ko [16, 17], Calude, Coles, Hertling, and
Khoussainov [5], Ho [15], and Downey and LaForte [14].
A real is random if its dyadic expansion forms a random innite binary sequence (in
the sense of, for instance, Martin-Lof [23]). Chaitin's number
the halting probability
of a universal self-delimiting computer, is a standard random c.e. real. (We will dene
these concepts more formally below.)
Many authors have
studied
and its properties, notably Chaitin [9, 10, 11] and
Martin-Lof [23]. In the very long and widely circulated manuscript [30] (a fragment of
which appeared in [31]), Solovay carefully investigated relationships between Martin-Lof-
Chaitin prex-free complexity, Kolmogorov complexity, and properties of random languages
and reals. See Chaitin [9] for an account of some of the results in this manuscript.
Solovay discovered that several important properties
of
(whose denition is model-
dependent) are shared by another class of reals he
called
lle e, whose denition is
model-independent. To dene this class, he introduced the following reducibility relation
among c.e. reals, called domination or Solovay reducibility.
1.1. Denition. Let  and  be c.e. reals. We say that  dominates , and write
6 S , if there are a constant c and a partial computable function
that for each rational q <  we have '(q)#<  and
We write   S  if  6 S  and  6 S .
The notation 6 dom has sometimes been used instead of 6 S .
Solovay reducibility is naturally associated with randomness because of the following
fact, whose proof we sketch for completeness. Let H() denote the prex-free complexity
of  and K() its standard Kolmogorov complexity. (Most of the statements below also
hold with K() in place of H( ). For the denitions and basic properties of H() and
K( ), see Calude [3] and Li and Vitanyi [22]. Among the many works dealing with
these and related topics, and in addition to those mentioned elsewhere in this paper,
we may cite Solomono [28, 29], Kolmogorov [18], Levin [20, 21], Schnorr [25], and the
expository article Calude and Chaitin [4].) We identify a real  2 (0; 1] with the innite
binary string  such that  = 0:. (The fact that certain reals have two dierent dyadic
expansions need not concern us here, since all such reals are rational.)
1.2. Theorem (Solovay [30]). Let  6 S
be c.e. reals. There is a constant O(1)
such that H(  n) 6 H(  n) +O(1) for all n 2 !.
Proof sketch. We rst sketch the proof of the following lemma, implicit in [30] and noted
by Calude, Hertling, Khoussainov, and Wang [6].
1.3. Lemma. Let c 2 !. There is a constant O(1) such that, for all n > 1 and all
binary strings ;  of length n with j0: 0: j < c2 n , we have jH() H()j 6 O(1).
The proof of the lemma is relatively simple. We can easily write a program P that,
for each su-ciently long , generates the 2c binary strings  0 of length n with
. For any binary strings ;  of length n with j0: 0: j < c2 n , in
order to compute  it su-ces to know a program for  and the position of  on the list
generated by P on input .
Turning to the proof of the theorem, let ' and c be as in Denition 1.1. Let
0:(  n). Since  n is rational and   n < 2 (n+1) , we have  '( n ) < c2 (n+1) . Thus,
by the lemma, H(  n) = H('( n ))+O(1), and hence H(  n) 6 H(  n)+O(1).
Solovay observed
that
dominates all c.e. reals, and Theorem 1.2 implies that if a
c.e. real dominates all c.e. reals then it must be random. This led Solovay to dene a
c.e. real to
be
-like if it dominates all c.e. reals. The point is that the denition of
seems quite model-independent, as opposed to the model-dependent denition of
This circle of ideas was completed recently by Slaman [26], who proved the converse
to the fact that
at e reals are random.
1.4. Theorem (Slaman). A c.e. real is random if and only if it
is
-like.
It is natural to seek to understand the c.e. reals under Solovay reducibility. A useful
characterization of this reducibility is given by the following lemma, which we prove in
the next section.
1.5. Lemma. Let  and  be c.e. reals. Then  6 S  if and only if for every computable
sequence of rationals a 0 ; a
a n
there are a constant c and a computable sequence of rationals " c such that
Phrased another way, Lemma 1.5 says that the c.e. reals dominated by a given c.e.
real  essentially correspond to splittings of  under arithmetic addition.
1.6. Corollary. Let  6 S
be c.e. reals. There is a c.e. real
and a rational c such
that
Proof. Let a 0 ; a be a computable sequence of rationals such that
a n . Let
be as in Lemma 1.5. Dene
each
" n is less than c, the real
is c.e., and of course
.
Solovay reducibility has a number of other beautiful interactions with arithmetic, as
we now discuss.
The relation 6 S is symmetric and transitive, and hence  S is an equivalence relation
on the c.e. reals. Thus we can dene the Solovay degree [] of a c.e. real  as its  S
equivalence class. (When we mention Solovay degrees below, we always mean Solovay
degrees of c.e. reals.) The Solovay degrees form an upper semilattice, with the join of
[] and [] being [+]=[], a fact observed by Solovay and others ( is denitely not
a join operation here). We note the following slight improvement of this result. Recall
that an uppersemilattice U is distributive if for all a
exist
1.7. Lemma. The Solovay degrees of c.e. reals form a distributive uppersemilattice with
Proof. Suppose that  6 S
of rationals such that
1. By Lemma 1.5, there are a constant c
and a computable sequence of rationals " c such that
n . Then
This establishes distributivity.
To see that the join in the Solovay degrees is given by addition, we again apply
Lemma 1.5. Certainly, for any c.e. reals  0 and  1 we have
and hence Conversely, suppose that  0 ;  1 6 . Let a 0 ; a
be a computable sequence of rationals such that
a n . For each
there is a constant c i and a computable sequence of rationals " i
n a n . Thus
n is less than c 0 +c 1 ,
a nal application of Lemma 1.5 show that  0
The proof that the join in the Solovay degrees is also given by multiplication is a
similar application of Lemma 1.5.
There is a least Solovay degree, the degree of the computable reals, as well as a
greatest one, the degree of
For proofs of these facts and more on c.e. reals and
Solovay reducibility, see for instance Chaitin [9, 10, 11], Calude, Hertling, Khoussainov,
and Wang [6], Calude and Nies [7], Calude [2], Slaman [26], and Coles, Downey, and
LaForte [12].
Despite the many attractive features of the Solovay degrees, their structure is largely
unknown. Coles, Downey, and LaForte [12] have shown that this structure is very
complicated by proving that it has an undecidable rst order theory.
One question addressed in the present paper, open since Solovay's original 1974
notes, is whether the structure of the Solovay degrees is dense. Indeed, up to now, it
was not known even whether there is a minimal Solovay degree. That is, intuitively, if
a c.e. real  is not computable, must there be a c.e. real that is also not computable,
yet is strictly less random that ?
In this paper, we show that the Solovay degrees of c.e. reals are dense. To do this
we divide the proof into two parts. We prove that if  <
then there is a c.e. real
with  < S
and we also prove that every incomplete Solovay degree splits over
each lesser degree.
The nonuniform nature of the argument is essential given the techniques we use,
since, in the splitting case, we have a priority construction in which the control of the
injuries is directly tied to the enumeration of
The fact that if a c.e. real  is Solovay-
incomplete
then
must grow more slowly than  is what allows us to succeed. (We
will discuss this more fully in Section 3.) This unusual technique is of some technical
interest, and clearly cannot be applied to proving upwards density, since in that case
the top degree
is
itself. To prove upwards density, we use a dierent technique,
taking advantage of the fact that, however we construct a c.e. real, it is automatically
dominated by
In light of these results, and further motivated by the general question of how randomness
can be produced, it is natural to ask whether the complete Solovay degree can
be split, or in other words, whether there exist nonrandom c.e. reals  and  such that
We give a negative answer to this question, thus characterizing the
random c.e. reals as those c.e. reals that cannot be written as the sum of two c.e. reals
of lesser Solovay degrees.
We remark that there are (non-c.e.) nonrandom reals whose sum is random; the
following is an example of this phenomenon. Dene the real  by letting
is even and
n) otherwise. (Here we identify a real with its dyadic expansion
as above.) Dene the real  by letting
n) otherwise.
Now  and  are clearly nonrandom, but
is random.
Before turning to the details of the paper, we point out that there are other reducibilities
one can study in this context. Coles, Downey, and LaForte [12, 13] introduced one
such reducibility, called sw-reducibility ; it is dened as follows. For sets of natural numbers
A and B, we say that A 6 sw B if there are a computable procedure and a
constant c such that A and the use of on argument x is bounded by x
reals we say that  6 sw  if there are sets A and B such that
is the characteristic function of the set S.
As in the case of Solovay reducibility, it is not di-cult to argue that if  6 sw  then
that
is sw-complete. Furthermore,
Coles, Downey, and LaForte [12] proved the analog of Slaman's theorem above in the
case of sw-reducibility, namely that if a c.e. real is random then it is sw-complete. They
also showed that Solovay reducibility and sw-reducibility are dierent, since there are
c.e. reals , ,
, and - such that  6 S  but
sw  and
S -, and that
there are no minimal sw-degrees of c.e. reals.
1.8. Question. Are the sw-degrees of c.e. reals dense?
Ultimately, the basic reducibility we seek to understand is H-reducibility, where
6H  if there is a constant O(1) such that H(  n) 6 H(  n) +O(1) for all n 2 !.
Little is known about this directly.
Preliminaries
Fix a self-delimiting universal computer M . (That is, for all binary strings , if M()#
then M( 0 )" for all  0 properly extending .) Then one can
dene
via
M()#
(The properties
of
relevant to this paper are independent of the choice of M .)
The c.e.
real
is random in the canonical Martin-Lof sense. Recall that a Martin-
Lof test is a uniformly c.e. sequence fV e : e > 0g of subsets of f0; 1g  such that for all
e > 0,
where  denotes the usual product measure on f0; 1g ! . The string  2 f0; 1g ! and
the real 0: are random, or more precisely, 1-random, if  =T
for every
Martin-Lof test fV e : e > 0g.
An alternate characterization of the random reals can be given via the notion of a
Solovay test. We give a somewhat nonstandard denition of this notion, which will be
useful below. A Solovay test is a c.e. sequence fI of intervals with rational end-points
such that
is the length of the interval I. As Solovay [30]
showed, a real  is random if and only if is nite for every Solovay test
The following lemma, implicit in [30] and proved in [12], provides an alternate characterization
of Solovay reducibility, which is the one that we will use below.
2.1. Lemma. Let  and  be c.e. reals, and let
increasing sequences of rationals converging to  and , respectively. Then  6 S  if
and only if there are a constant d and a total computable function f such that for all
Whenever we mention a c.e. real , we assume that we have chosen a computable
increasing sequence  converging to . The previous lemma guarantees that,
in determining whether one c.e. real dominates another, the particular choice of such
sequences is irrelevant. For convenience of notation, we adopt the convention that, for
any c.e. real  mentioned below, the expression  s  s 1 is equal to  0 when
We will also make use of two more lemmas, the rst of which has Lemma 1.5 as a
corollary.
2.2. Lemma. Let  6 S
be c.e. reals and let  be a computable increasing sequence
of rationals converging to . There is a computable increasing sequence ^
of rationals converging to  such that for some constant c and all s 2 !,
Proof. Fix a computable increasing sequence  rationals converging to , let
d and f be as in Lemma 2.1, and let c > d be such that  f(0) < c 0 . We may assume
without loss of generality that f is increasing.
There must be an s 0 > 0 for which  f(s 0 )  f(0) <
would have
contradicting our choice of d and f . It is now easy to
s0 so that ^
We can repeat the procedure in the previous paragraph with s 0 in place of 0 to
obtain an
s1 such that ^
Proceeding by recursion in this way, we dene a computable increasing sequence
of rationals with the desired properties.
We are now in a position to prove Lemma 1.5.
1.5. Lemma. Let  and  be c.e. reals. Then  6 S
if and only if for every computable
sequence of rationals a 0 ; a
a n
there are a constant c and a computable sequence of rationals " c such that
Proof. The if direction is easy; we prove the only if direction.
Suppose that  6 S . Given a computable sequence of rationals a 0 ; a
i6n a i and apply Lemma 2.2 to obtain c and ^
that lemma. Dene "
n . Now
for all n 2 !,
We nish this section with a simple lemma which will be quite useful below.
2.3. Lemma. Let
be c.e. reals. The following hold for all total computable
functions f and all k 2 !.
1. For each there is an s 2 ! such that either
(a)  t  f(n) < k( t  n ) for all t > s or
2. There are innitely many for which there is an s 2 ! such that  t  f(n) >
Proof. If there are innitely many t 2 ! such that  t  f(n) 6 k( t  n ) and innitely
many
which implies that   S .
If there are innitely many t 2 ! such that  t  f(n) 6 k( t  n ) then
So if this happens for all but nitely many n then  6 S . (The nitely many n for
which   f(n) > k(  n ) can be brought into line by increasing the constant k.)
3 Main Results
We now proceed with the proofs of our main results. We begin by showing that every
incomplete Solovay degree can be split over any lesser Solovay degree.
3.1. Theorem. Let
be c.e. reals. There are c.e. reals  0 and  1 such that
and  0
Proof. We want to build  0 and  1 so that
and the
following requirement is satised for each 2:
By Lemma 2.2 and the fact that
=c  S
for any rational c, we may assume without
loss of generality that 2(
s
(Recall our convention
that  0  c.e. real .)
In the absence of requirements of the form R 1 i;e;k , it is easy to satisfy simultaneously
all requirements of the form R i;e;k : for each s 2 !, simply let  i
s and  1 i
s .
In the presence of requirements of the form R 1 i;e;k , however, we cannot aord to be
quite so cavalier in our treatment of  enough of  has to be kept out of  1 i to
guarantee that  1 i does not dominate .
Most of the essential features of our construction are already present in the case of
two requirements R i;e;k and R 1 i;e 0 ;k 0 , which we now discuss. We assume that R i;e;k has
priority over R 1 i;e 0 ;k 0
and that both  e and  e 0
are total. We will think of the  j as
being built by adding amounts to them in stages. Thus  j
s will be the total amount
added to  j by the end of stage s. At each stage s we begin by adding
s
s 1 to the
current value of each  j ; in the limit, this ensures that  j > S
We will say that R i;e;k is satised through n at stage s if  e (n)[s]# and  s e (n) >
). The strategy for R i;e;k is to act whenever either it is not currently satised
or the least number through which it is satised changes. Whenever this happens, R i;e;k
initializes R 1 i;e 0 ;k 0 , which means that the amount of  2
that R 1 i;e 0 ;k 0 is allowed to
funnel into  i is reduced. More specically, once R 1 i;e 0 ;k 0 has been initialized for the
mth time, the total amount that it is thenceforth allowed to put into  i is reduced to
The above strategy guarantees that if R 1 i;e 0 ;k 0 is initialized innitely often then the
amount put into  i by R 1 i;e 0 ;k 0
(which in this case is all that is put into  i except for
the coding of
adds up to a computable real. In other words,  i  S
< S . But it is
not hard to argue, with the help of Lemma 2.3, that this means that there is a stage s
after which R i;e;k is always satised and the least number through which it is satised
does not change. So we conclude that R 1 i;e 0 ;k 0 is initialized only nitely often, and that
R i;e;k is eventually permanently satised.
This leaves us with the problem of designing a strategy for R 1 i;e 0 ;k 0
that respects the
strategy for R i;e;k . The problem is one of timing. To simplify notation, let ^
s . Since R 1 i;e 0 ;k 0 is initialized only nitely often, there is a certain
that it is allowed to put into  i after the last time it is initialized. Thus
waits until a stage s such that ^
adding nothing to  i until
such a stage is reached, then from that point on it can put all of ^
s into  i , which
of course guarantees its success. The problem is that, in the general construction, a
strategy working with a quota 2 m cannot eectively nd an s such that ^
If it uses up its quota too soon, it may nd itself unsatised and unable to do anything
about it.
The key to solving this problem (and the reason for the hypothesis that  < S
is
the observation that, since the
much more slowly than
the sequence ^
can be used to modulate the amount that R 1 i;e 0 ;k 0
puts into
More specically, at a stage s, if R 1 i;e 0 ;k 0 's current quota is 2 m then it puts into  i
as much of ^
possible, subject to the constraint that the total amount put
into  i by R 1 i;e 0 ;k 0
since the last stage before stage s at which R 1 i;e 0 ;k 0
was initialized
must not exceed 2
s . As we will see below, the fact
that
implies that there
is a stage v after which R 1 i;e 0 ;k 0 is allowed to put in all of ^
In general, at a given stage s there will be several requirements, each with a certain
amount that it wants (and is allowed) to direct into one of the  j . We will work back-
wards, starting with the weakest priority requirement that we are currently considering.
This requirement will be allowed to direct as much of ^
wants (subject to
its current quota, of course). If any of ^
then the next weakest priority
strategy will be allowed to act, and so on up the line.
We now proceed with the full construction. We say that R i;e;k has stronger priority
We say that R i;e;k is satised through n at stage s if
s be the least n through which R i;e;k is satised at stage s, if such an n exists,
and let n i;e;k
A stage s is e-expansionary if
Let q be the last e-expansionary stage before stage s (or let there have been
none). We say that R i;e;k requires attention at stage s if s is an e-expansionary stage
and there is an r 2 [q; s) such that either n i;e;k
r
r 1 .
If R i;e;k requires attention at stage s then we say that each requirement of weaker
priority than R i;e;k is initialized at stage s.
Each requirement R i;e;k has associated with it a c.e. real  i;e;k , which records the
amount put into  1 i for the sake of R i;e;k .
We decide how to distribute at stage s as follows.
1. Let
s
s
s 1 to the current value of each  i .
2. Let i < 2 and be such that 2he; ki be the number of times
R i;e;k has been initialized and let t be the last stage at which R i;e;k was initialized.
Let
(j+m)
(It is not hard to check that  is non-negative.) Add  to " and to the current
values of  i;e;k and  1 i .
3. " to the current value of  0 and end the stage.
Otherwise, decrease j by one and go to step 2.
This completes the construction. Clearly,
We now show by induction that each requirement initializes requirements of weaker
priority only nitely often and is eventually satised. Assume by induction that R i;e;k
is initialized only nitely often. Let be the number of times R i;e;k
is initialized, and let t be the last stage at which R i;e;k is initialized. If  e is not total
then R i;e;k is vacuously satised and eventually stops initializing requirements of weaker
priority, so we may assume that  e is total. Now the following are clearly equivalent:
1. R i;e;k is satised,
2. lim s n i;e;k
s exists and is nite, and
3. R i;e;k eventually stops requiring attention.
Assume for a contradiction that R i;e;k requires attention innitely often.
Since

, part 2 of Lemma 2.3 implies that there are v > u > t such that for all w > v we
Furthermore, by the way the amount  added to  i;e;k
at a given stage is dened in step 2 of the construction,  i;e;k
(j+m)
u and
i;e;k
Thus for all w > v,
(j+m)
(j+m)
(j+m)
From this we conclude that, after stage v, the reverse recursion performed at each stage
never gets past j, and hence everything put into  i after stage v is put in either to code
or for the sake of requirements of weaker priority than R i;e;k .
Let  be the sum of all  1 i;e 0 ;k 0
such that R 1 i;e 0 ;k 0 has weaker priority than R i;e;k .
Let s l > t be the lth stage at which R i;e;k requires attention. If R 1 i;e 0 ;k 0
is the pth
requirement on the priority list and p > j then
s l
l
and hence  is computable.
Putting together the results of the previous two paragraphs, we see that  i 6 S
Since
, this means that
It now follows from Lemma 2.3 that there is an
such that R i;e;k is eventually permanently satised through n, and such that R i;e;k
is eventually never satised through any n 0 < n. Thus lim s n i;e;k
s exists and is nite, and
hence R i;e;k is satised and eventually stops requiring attention.
We now show that the Solovay degrees are upwards dense, which together with the
previous result implies that they are dense.
3.2. Theorem. Let
be a c.e. real. There is a c.e. real  such that
<
.
Proof. We want to build  > S
to satisfy the following requirements for each

and

As in the previous proof, the analysis of an appropriate two-strategy case will be
enough to outline the essentials of the full construction. Let us consider the strategies
S e;k and R e 0 ;k 0 , the former having priority over the latter. We assume that both  e and
are total.
The strategy for S e;k is basically to make  look like
. At each point of the con-
struction, R e 0 ;k 0 has a certain fraction
of
that it is allowed to put into . (This is in
addition to the coding of
into , of course.) We will say that S e;k is satised through
n at stage s if  e (n)#
and
s
e (n) > k( s  n ). Whenever either it is not currently
satised or the least number through which it is satised changes, S e;k initializes R e 0 ;k 0 ,
which means that the fraction
of
that R e 0 ;k 0
is allowed to put into  is reduced.
As in the previous proof, if S e;k is not eventually permanently satised through some
n then the amount put into  by R e 0 ;k 0 is computable, and hence   S
. But, as before,
this implies that there is a stage after which S e;k is permanently satised through some
n and never again satised through any n 0 < n. Once this stage has been reached, R e 0 ;k 0
is free to code a xed fraction
of
into , and hence it too succeeds.
We now proceed with the full construction. We say that a requirement X e;k has
stronger priority than a requirement Y e 0 ;k 0 if either he; ki < he
We say that R e;k is satised through n at stage s if  e (n)# and
s
We say that S e;k is satised through n at stage s if  e (n)# and
s
For a requirement X e;k , let n X e;k
s be the least n through which X e;k is satised at stage s,
if such an n exists, and let n X e;k
As before, a stage s is e-expansionary if
Let X e;k be a requirement and let q be the last e-expansionary stage before stage s (or
there have been none). We say that requires attention at stage s if
s is an e-expansionary stage and there is an r 2 [q; s) such that either n X e;k
r
r 1 .
At stage s, proceed as follows. First add
s
s 1 to the current value of . If no
requirement requires attention at stage s then end the stage. Otherwise, let X e;k be the
strongest priority requirement requiring attention at stage s. We say that X e;k acts at
stage s. If then initialize all weaker priority requirements and end the stage.
be the number of times that R e;k has been
initialized. If s is the rst stage at which R e;k acts after the last time it was initialized
then let t be the last stage at which R e;k was initialized, and otherwise let t be the last
stage at which R e;k acted. Add 2
(j+m)(
s
t ) to the current value of  and end the
stage.
This completes the construction. Since  is bounded by
it
is a well-dened c.e. real. Furthermore,
We now show by induction that each requirement initializes requirements of weaker
priority only nitely often and is eventually satised. Assume by induction that there
is a stage u such that no requirement of stronger priority than X e;k requires attention
after stage u. If  e is not total then X e;k is vacuously satised and eventually stops
requiring attention, so we may assume that  e is total. Now the following are clearly
equivalent:
1. X e;k is satised,
2. lim s n X e;k
s exists and is nite,
3. X e;k eventually stops requiring attention, and
4. X e;k acts only nitely often.
First suppose that be the number of times that
R e;k is initialized. (Since R e;k is not initialized at any stage after stage u, this number
is nite.) Suppose that R e;k acts innitely often. Then the total amount added to  for
the sake of R e;k is 2 (j+m)
and hence   S 2
(j+m)

. It now follows from
Lemma 2.3 that there is an such that R e;k is eventually permanently satised
through n, and such that R e;k is eventually never satised through n 0 < n. Thus
lim s n R e;k
s exists and is nite, and hence R e;k is satised and eventually stops requiring
attention.
Now suppose that acts innitely often. If v > u is the mth stage at
which S e;k acts then the total amount added to  after stage v for purposes other than
coding
is bounded by
. This means that   S
It now
follows from Lemma 2.3 that there is an such that S e;k is eventually permanently
satised through n, and such that S e;k is eventually never satised through n 0 < n. Thus
s exists and is nite, and hence S e;k is satised and eventually stops requiring
attention.
Combining Theorems 3.1 and 3.2, we have the following result.
3.3. Theorem. The Solovay degrees of c.e. reals are dense.
We nish by showing that the hypothesis that  <
in the statement of Theorem
3.1 is necessary. This fact will follow easily from a stronger result which shows
that, despite the upwards density of the Solovay degrees, there is a sense in which the
complete Solovay degree is very much above all other Solovay degrees. We begin with a
lemma giving a su-cient condition for domination.
3.4. Lemma. Let f be an increasing total computable function and let k > 0 be a
natural number. Let  and  be c.e. reals for which there are innitely many s 2 ! such
that k(  s ) >   f(s) , but only nitely many s 2 ! such that k( t  s ) >  f(t)  f(s)
for all t > s. Then  6 S
.
Proof. By taking  as an approximating sequence for
, we may assume that f is the identity.
By hypothesis, there is an r 2 ! such that for all s > r there is a t > s with
. Furthermore, there is an s 0 > r such that k(  s
Given s i , let s i+1 be the least number greater than s i such that k( s i+1
Assuming by induction that k(  s i
, we have
Thus s 0 < s 1 <    is a computable sequence such that k(  s i
for all
Now dene the computable function g by letting g(n) be the least s i that is greater
than or equal to n. Then   g(n) < k(  g(n) ) 6 k(  n ) for all n 2 !, and hence
6 S .
3.5. Theorem. Let  and  be c.e. reals, let f be an increasing total computable func-
tion, and let k > 0 be a natural number. If  is random and there are innitely many
such that k(  s ) >   f(s) then  is random.
Proof. As in Lemma 3.4, we may assume that f is the identity. If  is rational then we
can replace it with a nonrational computable real  0 such that  0  0
s >   s for all
so we may assume that  is not rational.
We assume that  is nonrandom and there are innitely many s 2 ! such that
show that  is nonrandom. The idea is to take a Solovay test
!g such that  2 I i for innitely many use it to build a Solovay
test !g such that  2 J i for innitely many i 2 !.
Let
Except in the trivial case in which   S , Lemma 2.3 guarantees that U is  0
2 . Thus
a rst attempt at building B could be to run the following procedure for all
parallel. Look for the least t such that there is an s < t with s 2 U [t] and  s 2 I i . If
there is more than one number s with this property then choose the least among such
numbers. Begin to add the intervals
to B, continuing to do so as long as s remains in U and the approximation of  remains
in I i . If the approximation of  leaves I i then end the procedure. If s leaves U , say at
stage u, then repeat the procedure (only considering t > u, of course).
If  2 I i then the variable s in the above procedure eventually assumes a value in
U . For this value, k(  s ) >   s , from which it follows that k( u  s ) >   s
for some u > s, and hence that must be in one of the
intervals () added to B by the above procedure.
Since  is in innitely many of the I i , running the above procedure for all
guarantees that  is in innitely many of the intervals in B. The problem is that
we also need the sum of the lengths of the intervals in B to be nite, and the above
procedure gives no control over this sum, since it could easily be the case that we start
working with some s, see it leave U at some stage t (at which point we have already
added to B intervals whose lengths add up to  t 1  s ), and then nd that the next
s with which we have to work is much smaller than t. Since this could happen many
times for each i 2 !, we would have no bound on the sum of the lengths of the intervals
in B.
This problem would be solved if we had an innite computable subset T of U . For
each I i , we could look for an s 2 T such that  s 2 I i , and then begin to add the
intervals () to B, continuing to do so as long as the approximation of  remained in I i .
(Of course, in this easy setting, we could also simply add the single interval [
to B.) It is not hard to check that this would guarantee that if  2 I i then  is in one
of the intervals added to B, while also ensuring that the sum of the lengths of these
intervals is less than or equal to k jI i j. Following this procedure for all would give
us the desired Solovay test B. Unless  6 S , however, there is no innite computable
so we use Lemma 3.4 to obtain the next best thing.
Let
If  6 S  then  is nonrandom, so, by Lemma 3.4, we may assume that S is innite.
Note that k(  s ) >   s for all s 2 S. In fact, we may assume that k(  s ) >   s
for all s 2 S, since if k(  s dier by a rational amount, and
hence  is nonrandom.
The set S is co-c.e. by denition, but it has an additional useful property. Let
If s 2 S[t 1] S[t] then no u 2 (s; t) is in S, since for any such u we have
In other words, if s leaves S at stage t then so do all numbers in (s; t).
To construct B, we run the following procedure P i for all in parallel. Note
that B is a sequence rather than a set, so we are allowed to add more than one copy of
a given interval to B.
1. Look for an s 2 ! such that  s 2 I i .
2. Let
I i then terminate the procedure.
3. If
and go to step 2. Otherwise, add the interval
to B, increase t by one, and repeat step 3.
This concludes the construction of B. We now show that the sum of the lengths of
the intervals in B is nite and that  is in innitely many of the intervals in B.
For each i 2 !, let B i be the set of intervals added to B by P i and let l i be the sum of
the lengths of the intervals in B i . If P i never leaves step 1 then eventually
terminates then l i 6 k( t  s ) for some s; t 2 ! such that  s ;  t 2 I i , and hence
reaches step 3 and never terminates then  2 I i and l i 6 k(  s ) for
some s 2 ! such that  s 2 I i , and hence again l i 6 k jI i j. Thus the sum of the lengths
of the intervals in B is less than or equal to k
To show that  is in innitely many of the intervals in B, it is enough to show that,
for each i 2 !, if  2 I i then  is in one of the intervals in B i .
Fix such that  2 I i . Since  is not rational,  u 2 I i for all su-ciently large
must eventually reach step 3. By the properties of S discussed above,
the variable s in the procedure P i eventually assumes a value in S. For this value,
, from which it follows that k( u  s ) >   s for some u > s,
and hence that must be in one of the intervals (), all of
which are in B i .
3.6. Corollary. If  0 and  1 are c.e. reals such that  0 random then at least
one of  0 and  1 is random.
Proof. Let . For each s 2 !, either 3( 0  0
so for some i < 2 there are innitely many s 2 ! such that 3( i  i
Theorem 3.5,  i is random.
Combining Theorem 3.1 and Corollary 3.6, we have the following results, the second
of which also depends on Theorem 1.4.
3.7. Theorem. A c.e. real
is random if and only if it cannot be written as +  for
c.e. reals ;  < S
3.8. Theorem. Let d be a Solovay degree. The following are equivalent:
1. d is incomplete.
2. d splits.
3. d splits over any lesser Solovay degree.



--R

Weakly computable real numbers
A characterization of c.
Information and Randomness
Nature 400

Centre for Discrete Mathematics and Theoretical Computer Science Research Report Series 59


Algorithmic information theory
Incompleteness theorems for random reals

Randomness and reducibility I

Presentations of computably enumerable reals

On the de
On the continued fraction representation of computable real numbers
Three approaches to the quantitative de

On the notion of a random sequence
The various measures of the complexity of
An Introduction to Kolmogorov Complexity and its Appli- cations


Process complexity and e
Randomness and recursive enumerability
Cohesive sets and recursively enumerable Dedekind cuts


Draft of a paper (or series of papers) on Chaitin's work

--TR

--CTR
Rod Downey , Denis R. Hirschfeldt , Geoff LaForte, Undecidability of the structure of the Solovay degrees of c.e. reals, Journal of Computer and System Sciences, v.73 n.5, p.769-787, August, 2007
kolmogorov complexity;algorithmic information theory;randomness;solovay reducibility;computably enumerable reals