Abstract:
This thesis establishes significant new results in the area of algorithmic randomness.
These results elucidate the deep relationship between randomness
and computability.
A number of results focus on randomness for finite strings. Levin introduced
two functions which measure the randomness of finite strings. One
function is derived from a universal monotone machine and the other function
is derived from an optimal computably enumerable semimeasure. Gacs
proved that infinitely often, the gap between these two functions exceeds the
inverse Ackermann function (applied to string length). This thesis improves
this result to show that infinitely often the difference between these two functions
exceeds the double logarithm. Another separation result is proved for
two different kinds of process machine.
Information about the randomness of finite strings can be used as a computational
resource. This information is contained in the overgraph. Muchnik
and Positselsky asked whether there exists an optimal monotone machine
whose overgraph is not truth-table complete. This question is answered in the
negative. Related results are also established.
This thesis makes advances in the theory of randomness for infinite binary
sequences. A variant of process machines is used to characterise computable
randomness, Schnorr randomness and weak randomness. This result is extended
to give characterisations of these types of randomness using truthtable
reducibility. The computable Lipschitz reducibility measures both the
relative randomness and the relative computational power of real numbers. It
is proved that the computable Lipschitz degrees of computably enumerable
sets are not dense.
Infinite binary sequences can be regarded as elements of Cantor space.
Most research in randomness for Cantor space has been conducted using the
uniform measure. However, the study of non-computable measures has led to
interesting results. This thesis shows that the two approaches that have been
used to define randomness on Cantor space for non-computable measures:
that of Reimann and Slaman, along with the uniform test approach first introduced
by Levin and also used by Gacs, Hoyrup and Rojas, are equivalent.
Levin established the existence of probability measures for which all infinite sequences are random. These measures are termed neutral measures. It is
shown that every PA degree computes a neutral measure. Work of Miller is
used to show that the set of atoms of a neutral measure is a countable Scott set
and in fact any countable Scott set is the set of atoms of some neutral measure.
Neutral measures are used to prove new results in computability theory. For
example, it is shown that the low computable enumerable sets are precisely
the computably enumerable sets bounded by PA degrees strictly below the
halting problem.
This thesis applies ideas developed in the study of randomness to computability
theory by examining indifferent sets for comeager classes in Cantor
space. A number of results are proved. For example, it is shown that there
exist 1-generic sets that can compute their own indifferent sets.
