Nonrandom Sequences between Random Sequences

Peter Hertling (Institut für Theoretische Informatik und Mathematik, Universität der Bundeswehr München, Germany)

Abstract: Let us say that an infinite binary sequence q lies above an infinite binary sequence p if q can be obtained from p by replacing selected 0's in p by 1's. We show that above any infinite binary Martin-Löf random sequence p there exists an infinite binary nonrandom sequence q above which there exists an infinite binary random sequence r. This result is of interest especially in connection with the new randomness notion for sets of natural numbers introduced in [Hertling and Weihrauch 1998, Hertling and Weihrauch 2003] and in connection with its relation to the Martin-Löf randomness notion for infinite binary sequences.

Keywords: algorithmic information theory, algorithmic randomness, random binary sequences, random sets

Categories: F.1, H.1.1