On the Kolmogorov complexity of continuous real functions
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2013
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/56380/ |
| _version_ | 1848799320964333568 |
|---|---|
| author | Farjudian, Amin |
| author_facet | Farjudian, Amin |
| author_sort | Farjudian, Amin |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T20:33:48Z |
| format | Article |
| id | nottingham-56380 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T20:33:48Z |
| publishDate | 2013 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-563802019-04-01T13:20:27Z https://eprints.nottingham.ac.uk/56380/ On the Kolmogorov complexity of continuous real functions Farjudian, Amin 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. Elsevier 2013-05-31 Article PeerReviewed application/pdf en https://eprints.nottingham.ac.uk/56380/1/2013-Farjudian-On_the_Kolmogorov_complexity_of_continuous_real_functions-APAL_Journal.pdf Farjudian, Amin (2013) On the Kolmogorov complexity of continuous real functions. Annals of Pure and Applied Logic, 164 (5). pp. 566-576. ISSN 0168-0072 Kolmogorov complexity; Algorithmic randomness; Computable analysis; Domain theory; Measure theory; Prevalence http://dx.doi.org/10.1016/j.apal.2012.11.003 doi:10.1016/j.apal.2012.11.003 doi:10.1016/j.apal.2012.11.003 |
| spellingShingle | Kolmogorov complexity; Algorithmic randomness; Computable analysis; Domain theory; Measure theory; Prevalence Farjudian, Amin On the Kolmogorov complexity of continuous real functions |
| title | On the Kolmogorov complexity of continuous real functions |
| title_full | On the Kolmogorov complexity of continuous real functions |
| title_fullStr | On the Kolmogorov complexity of continuous real functions |
| title_full_unstemmed | On the Kolmogorov complexity of continuous real functions |
| title_short | On the Kolmogorov complexity of continuous real functions |
| title_sort | on the kolmogorov complexity of continuous real functions |
| topic | Kolmogorov complexity; Algorithmic randomness; Computable analysis; Domain theory; Measure theory; Prevalence |
| url | https://eprints.nottingham.ac.uk/56380/ https://eprints.nottingham.ac.uk/56380/ https://eprints.nottingham.ac.uk/56380/ |