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

Bruno Durand, Alexander Shen, Nikolay Vereshchagin

We study different notions of descriptive complexity of

computable sequences. Our main result states that if for almost all

n the Kolmogorov complexity of the n-prefix of an infinite

binary sequence x conditional to n

is less than m then there is a program of length

m^2+O(1) that for ...
more >>>