6533b833fe1ef96bd129b6c8

RESEARCH PRODUCT

Effects of Kolmogorov complexity present in inductive inference as well

Cristian S. CaludeAndris AmbainisKalvis ApsitisMarek KarpinskiIveta SalaTomas LarfeldtRusins FreivaldsJuris Smotrovs

subject

PHAverage-case complexityDiscrete mathematicsStructural complexity theoryKolmogorov complexityKolmogorov structure functionChain rule for Kolmogorov complexityDescriptive complexity theoryMathematicsQuantum complexity theory

description

For all complexity measures in Kolmogorov complexity the effect discovered by P. Martin-Lof holds. For every infinite binary sequence there is a wide gap between the supremum and the infimum of the complexity of initial fragments of the sequence. It is assumed that that this inevitable gap is characteristic of Kolmogorov complexity, and it is caused by the highly abstract nature of the unrestricted Kolmogorov complexity.

yearjournalcountryeditionlanguage
1997-01-01
https://doi.org/10.1007/3-540-63577-7_47