Random elements in effective topological spaces with measure

Following a suggestion of Zvonkin and Levin, we generalize Martin-Löf’s definition of infinite random sequences over a finite alphabet via randomness tests to effective topological spaces with a measure. We show that under weak computability conditions there is a universal randomness test. We prove a theorem on randomness preserving functions which corrects and extends a result by Schnorr and apply it to a number of examples. In particular, we show that a real number is random if, and only if, it has a random b-ary representation, for any b⩾2. We show that many computable, continuously differentiable real functions preserve randomness. Especially, all computable analytic functions which are not constant on any open subset of their domain preserve randomness. Finally, we introduce a new randomness concept for subsets of natural numbers, which we characterize in terms of random sequences. Surprisingly, it turns out that there are infinite co-r. e. random sets.

Authors

• Peter Hertling
• Klaus Weihrauch

Keywords

• Algorithmic randomness
• Randomness tests
• Random real numbers
• Random sets