ECCC-Report TR01-087https://eccc.weizmann.ac.il/report/2001/087Comments and Revisions published for TR01-087en-usWed, 28 Nov 2001 16:39:53 +0200
Paper TR01-087
| Descriptive complexity of computable sequences |
Bruno Durand,
Alexander Shen,
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2001/087We 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.
Wed, 28 Nov 2001 16:39:53 +0200https://eccc.weizmann.ac.il/report/2001/087