Nonrandom Sequences between Random Sequences
Дата
Авторы
Hertling,Peter
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
algorithmic information theory , algorithmic randomness , random binary sequences , random sets