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).