TR01-087 Authors: Bruno Durand, Alexander Shen, Nikolay Vereshchagin

Publication: 28th November 2001 16:39

Downloads: 1536

Keywords:

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 almost all n given n as input prints the n-prefix

of x. We prove that this bound is tight up to a constant factor.