Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-12T22:14:21.578Z Has data issue: false hasContentIssue false
  • English
  • Français

Computability and information in models of randomness and chaos†

Published online by Cambridge University Press:  01 April 2008

CRISTOBAL ROJAS
CRISTOBAL ROJAS*
Affiliation:
LIENS, CNRS – ENS, 45 rue d'Ulm, F-75230 Paris cedex 05, France and CREA, Ecole Polytechnique, 1 rue Descartes. 75005Paris Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper presents a short survey of some recent approaches relating two different areas, viz. deterministic chaos and computability. Chaos in classical physics may be approached by dynamical (equationally determined) systems or stochastic ones (as random processes). However, randomness has also been effectively modelled using recursion theoretic tools by P. Martin-Löf. We recall its connections to Kolmogorov complexity and show some applications to dynamical systems. This allows us to introduce results that connect well-established notions of entropy and algorithmic information.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 18 , Issue 2 , April 2008 , pp. 291 - 307
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bailly, F. and Longo, G. (2007) Randomness and Determination in the interplay between the Continuum and the Discrete (to appear). (Downloadable as revised English version of the appendix to the book: Bailly, F. and Longo, G. (2006) Mathématiques et sciences de la nature. La singularité physique du vivant, Hermann, Paris.)Google Scholar
Birkhoff, G. D. (1931) Proof of the ergodic theorem. Proc. Nat. Acad. Sci. 17 656–660.CrossRefGoogle ScholarPubMed
Brudno, A. A. (1983) Entropy and the complexity of the trajectories of a dynamical system. Trans. Mosc. Math. Soc. 44 127–151.Google Scholar
Chaitin, G. (1987) Algorithmic Information Theory, Cambridge University Press.CrossRefGoogle Scholar
Kolmogorov, A. N. (1933) Grundbegriffe der Wahrsceinlichkeitsrechung. Ergebnisse der Mathematik und ihrer Grenzgebiete.Google Scholar
Kolmogorov, A. N. (1963) The theory of probability. Transactions of mathematical monographs 1, AMS.Google Scholar
Kolmogorov, A. N. (1983) Combinatorial basis of information theory and probability theory. Russ. Math. Surveys 38 29–40CrossRefGoogle Scholar
Gács, P. (1993) Lecture notes on descriptional complexity and randomness, Boston University 1–67.Google Scholar
Galatolo, S. (1999) Pointwise information entropy for metric spaces. Nonlinearity 12 1289–1298.CrossRefGoogle Scholar
Galatolo, S. (2000) Orbit complexity by computable structures. Nonlinearity 13 1531–1546.CrossRefGoogle Scholar
Hertling, P. and Weihrauch, K. (1998) Randomness spaces. Springer-Verlag Lecture Notes in Computer Science 1443 796–807.CrossRefGoogle Scholar
vanLambalgen, M. Lambalgen, M. (1987) Random sequence, Academish Proefschrift, Amsterdam.Google Scholar
Levin, L. A. and Zvonkin, A. K. (1970) The complexity of finite objects and the algorithmic foundations of the notions of information and randomness. Russ. Math. Surveys 25.Google Scholar
Levin, L. A. (1984) Randomness conservation inequalities: information and independence in mathematical theories. Inf. and Control 61 15–37.CrossRefGoogle Scholar
Lévy, P. (1925) Calcul des probabilités, Gauthiers-Villars.Google Scholar
Li, M. and Vitanyi, P. (1997) An introduction to Kolmogorov complexity and its applications, Springer-Verlag.CrossRefGoogle Scholar
MartinLöf, P. (1966) The definition of random sequence. Inf. and Control 9 602–619.CrossRefGoogle Scholar
Petersen, K. (1983) Ergodic theory, Cambridge University Press.CrossRefGoogle Scholar
Rogers, H. (1967) Theory of recursive functions and effective computability, McGraw Hill.Google Scholar
V'Yugin, V. V. (1997) Effective convergence in probability and an ergodic theorem for individual random sequences. Theory Probab. Appl. 42 (1)39–50.CrossRefGoogle Scholar