Nikolay Vereshchagin

We present a simplified proof of Solovay-Calude-Coles theorem

stating that there is an enumerable undecidable set with the

following property: prefix

complexity of its initial segment of length n is bounded by prefix

complexity of n (up to an additive constant).

Ludwig Staiger

The present paper generalises results by Tadaki [12] and Calude et al. [1] on oscillation-free partially random infinite strings. Moreover, it shows that oscillation-free partial Chaitin randomness can be separated from scillation-free partial strong Martin-L\"of randomness by $\Pi_{1}^{0}$-definable sets of infinite strings.

more >>>