Abstract:
Martin-Löf defined infinite random sequences over a finite alphabet via randomness
tests which describe sets having measure zero in a constructive sense. In this paper
this concept is generalized to separable topological spaces with a measure, following a
suggestion of Zvonkin and Levin. After studying basic results and constructions for such
randomness spaces a general invariance result is proved which gives conditions under
which a function between randomness spaces preserves randomness. This corrects and
extends a result by Schnorr. Calude and Jürgensen proved that the randomness notion
for real numbers obtained by considering their b-ary representations is independent
from the base b. We use our invariance result to show that this notion is identical
with the notion which one obtains by viewing the real number space directly as a
randomness space. Furthermore, arithmetic properties of random real numbers are
derived, for example that every computable analytic function preserves randomness.
Finally, by considering the power set of the natural numbers with its natural topology
as a randomness space, we introduce a new notion of a random set of numbers. It
is different from the usual one which is defined via randomness of the characteristic
function, but it can also be characterized in terms of random sequences. Surprisingly,
it turns out that there are infinite co-r.e. random sets.