TY - GEN

T1 - On the Kolmogorov complexity of continuous real functions

AU - Farjudian, Amin

PY - 2011

Y1 - 2011

N2 - Kolmogorov complexity was originally defined for finitely-representable objects. Later, the definition was extended to real numbers based on the behaviour of the sequence of Kolmogorov complexities of finitely-representable objects-such as rational numbers-used to approximate them. The idea will be taken further here by extending the definition to functions over real numbers. Any real function can be represented as the limit of a sequence of finitely-representable enclosures, such as polynomials with rational coefficients. The asymptotic behaviour of the sequence of Kolmogorov complexities of the enclosures in such a sequence can be considered as a measure of practical suitability of the sequence as the candidate for representation of that real function. Based on that definition, we will prove that for any growth rate imaginable, there are real functions whose Kolmogorov complexities have higher growth rates. In fact, using the concept of prevalence, we will prove that 'almost every' real function has such a high-growth Kolmogorov complexity. Moreover, we will present an asymptotic bound on the Kolmogorov complexities of total single-valued computable real functions.

AB - Kolmogorov complexity was originally defined for finitely-representable objects. Later, the definition was extended to real numbers based on the behaviour of the sequence of Kolmogorov complexities of finitely-representable objects-such as rational numbers-used to approximate them. The idea will be taken further here by extending the definition to functions over real numbers. Any real function can be represented as the limit of a sequence of finitely-representable enclosures, such as polynomials with rational coefficients. The asymptotic behaviour of the sequence of Kolmogorov complexities of the enclosures in such a sequence can be considered as a measure of practical suitability of the sequence as the candidate for representation of that real function. Based on that definition, we will prove that for any growth rate imaginable, there are real functions whose Kolmogorov complexities have higher growth rates. In fact, using the concept of prevalence, we will prove that 'almost every' real function has such a high-growth Kolmogorov complexity. Moreover, we will present an asymptotic bound on the Kolmogorov complexities of total single-valued computable real functions.

UR - http://www.scopus.com/inward/record.url?scp=80053042706&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-21875-0_9

DO - 10.1007/978-3-642-21875-0_9

M3 - Conference contribution

AN - SCOPUS:80053042706

SN - 9783642218743

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 81

EP - 91

BT - Models of Computation in Context - 7th Conference on Computability in Europe, CiE 2011, Proceedings

T2 - 7th Conference on Computability in Europe, CiE 2011

Y2 - 27 June 2011 through 2 July 2011

ER -