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