Annals of Pure and Applied Logic 164 (5):566-576 (2013)

Kolmogorov complexity was originally defined for finitely-representable objects. Later, the definition was extended to real numbers based on the asymptotic behaviour of the sequence of the Kolmogorov complexities of the finitely-representable objects—such as rational numbers—used to approximate them.This idea will be taken further here by extending the definition to continuous functions over real numbers, based on the fact that every continuous real function can be represented as the limit of a sequence of finitely-representable enclosures, such as polynomials with rational coefficients.Based on this 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’ continuous real function has such a high-growth Kolmogorov complexity. An asymptotic bound on the Kolmogorov complexities of total single-valued computable real functions will be presented as well
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2012.11.003
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,091
Through your library

References found in this work BETA

Arithmetical Representations of Brownian Motion I.Willem Fouché - 2000 - Journal of Symbolic Logic 65 (1):421-442.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Compressibility and Kolmogorov Complexity.Stephen Binns & Marie Nicholson - 2013 - Notre Dame Journal of Formal Logic 54 (1):105-123.
Every 2-Random Real is Kolmogorov Random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Kolmogorov Complexity and Noncomputability.George Davie - 2002 - Mathematical Logic Quarterly 48 (4):574-581.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
The Modal Logic of Continuous Functions on the Rational Numbers.Philip Kremer - 2010 - Archive for Mathematical Logic 49 (4):519-527.
Kolmogorov Complexity and the Second Incompleteness Theorem.Makoto Kikuchi - 1997 - Archive for Mathematical Logic 36 (6):437-443.
Relative Kolmogorov Complexity and Geometry.Stephen Binns - 2011 - Journal of Symbolic Logic 76 (4):1211-1239.
Quasi‐Completeness and Functions Without Fixed‐Points.Ilnur I. Batyrshin - 2006 - Mathematical Logic Quarterly 52 (6):595-601.


Added to PP index

Total views
172 ( #68,145 of 2,506,116 )

Recent downloads (6 months)
1 ( #416,984 of 2,506,116 )

How can I increase my downloads?


My notes