Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 11 / Issue 12

available in:   PDF (164 kB) PS (150 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-011-12-1970


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