Publication at Faculty of Mathematics and Physics |
2017
Abstract
The van Lambalgen theorem is a surprising result in algorithmic information theory concerning the symmetry of relative randomness. It establishes that for any pair of infinite sequences A and B, B is Martin-Löf random and A is Martin-Löf random relative to B if and only if the interleaved sequence is Martin-Löf random.
This implies that A is relative random to B if and only if B is random relative to A. This paper studies the validity of this phenomenon for different notions of time-bounded relative randomness.