On the Kolmogorov complexity of continuous real functions

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationModels of Computation in Context - 7th Conference on Computability in Europe, CiE 2011, Proceedings
Pages81-91
Number of pages11
DOIs
Publication statusPublished - 2011
Event7th Conference on Computability in Europe, CiE 2011 - Sofia, Bulgaria
Duration: 27 Jun 20112 Jul 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6735 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th Conference on Computability in Europe, CiE 2011
Country/TerritoryBulgaria
CitySofia
Period27/06/112/07/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'On the Kolmogorov complexity of continuous real functions'. Together they form a unique fingerprint.

Cite this