JUCS - Journal of Universal Computer Science 11(12): 1970-1985, doi: 10.3217/jucs-011-12-1970

Nonrandom Sequences between Random Sequences

‡ Institut für Theoretische Informatik und Mathematik, Universität der Bundeswehr München, Germany

Corresponding author: Peter Hertling ( hertling@informatik.unibw-muenchen.de ) Citation:
Hertling P (2005) Nonrandom Sequences between Random Sequences. JUCS - Journal of Universal Computer Science 11(12): 1970-1985. https://doi.org/10.3217/jucs-011-12-1970 |

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