Annals of Pure and Applied Logic 164 (5):566-576 (2013)
Abstract |
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 |
Options |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
Continuous Lattices and Domains.G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. W. Mislove & D. S. Scott - 2007 - Studia Logica 86 (1):137-138.
Arithmetical Representations of Brownian Motion I.Willem Fouché - 2000 - Journal of Symbolic Logic 65 (1):421-442.
Algorithmic Randomness of Continuous Functions.George Barmpalias, Paul Brodhead, Douglas Cenzer, Jeffrey B. Remmel & Rebecca Weber - 2008 - Archive for Mathematical Logic 46 (7-8):533-546.
Citations of this work BETA
No citations found.
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.
Algorithmic Randomness of Continuous Functions.George Barmpalias, Paul Brodhead, Douglas Cenzer, Jeffrey B. Remmel & Rebecca Weber - 2008 - Archive for Mathematical Logic 46 (7-8):533-546.
Kolmogorov Complexity Estimates for Detection of Viruses in Biologically Inspired Security Systems: A Comparison with Traditional Approaches.Sanjay Goel & Stephen F. Bush - 2003 - Complexity 9 (2):54-73.
Every 2-Random Real is Kolmogorov Random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Program Size Complexity for Possibly Infinite Computations.Verónica Becher, Santiago Figueira, André Nies & Silvana Picchi - 2005 - Notre Dame Journal of Formal Logic 46 (1):51-64.
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.
Kolmogorov Complexity and Set Theoretical Representations of Integers.Marie Ferbus-Zanda & Serge Grigorieff - 2006 - Mathematical Logic Quarterly 52 (4):375-403.
Kolmogorov Complexity and Characteristic Constants of Formal Theories of Arithmetic.Shingo Ibuka, Makoto Kikuchi & Hirotaka Kikyo - 2011 - Mathematical Logic Quarterly 57 (5):470-473.
Kolmogorov Complexity and Information Theory. With an Interpretation in Terms of Questions and Answers.Peter D. Grünwald & Paul M. B. Vitányi - 2003 - Journal of Logic, Language and Information 12 (4):497-529.
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.
Analytics
Added to PP index
2013-12-12
Total views
172 ( #68,145 of 2,506,116 )
Recent downloads (6 months)
1 ( #416,984 of 2,506,116 )
2013-12-12
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?
Downloads