Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-19T03:49:22.575Z Has data issue: false hasContentIssue false
  • English
  • Français

Algorithmic complexity of points in dynamical systems

Published online by Cambridge University Press:  19 September 2008

Homer S. White
Homer S. White
Affiliation:
Division of Science and Mathematics, Pikeville College, Pikeville, KY 41501-1194, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

This work is based on the author's dissertation. We examine the algorithmic complexity (in the sense of Kolmogorov and Chaitin) of the orbits of points in dynamical systems. Extending a theorem of A. A. Brudno, we note that for any ergodic invariant probability measure on a compact dynamical system, almost every trajectory has a limiting complexity equal to the entropy of the system. We use these results to show that for minimal dynamical systems, and for systems with the tracking property (a weaker version of specification), the set of points whose trajectories have upper complexity equal to the topological entropy is residual. We give an example of a topologically transitive system with positive entropy for which an uncountable open set of points has upper complexity equal to zero. We use techniques from universal data compression to prove a recurrence theorem: if a compact dynamical system has a unique measure of maximal entropy, then any point whose lower complexity is equal to the topological entropy is generic for that unique measure. Finally, we discuss algorithmic versions of the theorem of Kamae on preservation of the class of normal sequences under selection by sequences of zero Kamae-entropy.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 13 , Issue 4 , December 1993 , pp. 807 - 830
Copyright
Copyright © Cambridge University Press 1993

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

REFERENCES

[1]Algoet, P. H. & Cover, T. M.. Asymptotic optimally and asymptotic equipartition properties of logoptimum investment. Ann. Prob. 16 (1988), 876–898.CrossRefGoogle Scholar
[2]Barron, A. R.. Logically smooth density estimation. PhD Dissertation. Stanford University, 1985.Google Scholar
[3]Boolos, G. & Jeffrey, R. C.. Computability and Logic. 2nd edn.Cambridge University Press, Cambridge, 1980.Google Scholar
[4]Brudno, A. A.. The complexity of the trajectories of a dynamical system. (Engl. transl.). Russian Math. Surveys. 33 (1979), no. 1197–198.CrossRefGoogle Scholar
[5]Brudno, A. A.. Entropy and the complexity of the trajectories of a dynamical system. Trans. Moscow Math. Soc. 2 (1983), 127–151. (Engl. transl.).Google Scholar
[6]Chaitin, G. J.. On the length of programs for computing finite binary sequences. J. Assoc. Comput. Mach. 13 (1966), 547–569.CrossRefGoogle Scholar
[7]Chaitin, G. J.. Algorithmic Information Theory. Cambridge University Press, Cambridge, 1987.CrossRefGoogle Scholar
[8]Chaitin, G. J.. Information, Randomness, and Incompleteness: Papers on Algorithmic Information Theory. 2nd edn.World Scientific, Singapore, 1990.CrossRefGoogle Scholar
[9]Coffey, J. T. & Goodman, R.. Any code of which we cannot think is good. IEEE Trans. Inform. Theory 36 (1990), 1453–1461.CrossRefGoogle Scholar
[10]Davisson, L. D.. Universal noiseless coding. IEEE Trans. Inform. Theory IT-19 (1973), 783–795.CrossRefGoogle Scholar
[11]Denker, M., Grillenberger, C. & Sigmund, K.. Ergodic Theory on Compact Spaces. Springer Lecture Notes in Mathematics 527. Springer-Verlag, Berlin, 1976.CrossRefGoogle Scholar
[12]Grillenberger, C.. Constructions of strictly ergodic systems I: given entropy. Z. Wahrscheinlichkeitstheorie und venwandte Gebiete 25 (1973), 323–334.CrossRefGoogle Scholar
[13]Kamae, T.. Subsequences of normal sequences. Israel J. Math. 16 (1973), 121–149.CrossRefGoogle Scholar
[14]Kieffer, J. C.. Sample converses in source coding theory. IEEE Trans. Inform. Theory 37 (1991), 263–268.CrossRefGoogle Scholar
[15]Kolmogorov, A. N.. Three approaches to the definition of the concept ‘quantity of information’. Problems of Information Transmission 1 (1965), 3–11.Google Scholar
[16]Lempel, A. & Ziv, J.. On the complexity of finite sequences. IEEE Trans. Inform. Theory IT-22 (1976), 75–81.CrossRefGoogle Scholar
[17]Levin, L. A.. The concept of a random sequence. Sov. Math. Dokl. 14 (1973), 1413–1416.Google Scholar
[18]Martin-Lof, P.. The definition of random sequences. Information and Control 9 (1966), 602–619.CrossRefGoogle Scholar
[19]Martin-Lof, P.. Algorithmen und Zufallige Folgen. Skriptum Erlangen, Berlin, 1966.Google Scholar
[20]Ornstein, D. & Shields, P.. Universal amost sure data compression. Ann. Probability 18 (1990), 441–452.CrossRefGoogle Scholar
[21]Petersen, K.. Ergodic Theory. Cambridge University Press, Cambridge, 1983.CrossRefGoogle Scholar
[22]Rissanen, J.. Universal coding, information, prediction and estimation. IEEE Trans. Inform. Theory IT-30 (1984), 629–636.CrossRefGoogle Scholar
[23]Schnorr, C. P.. Process complexity and effective random tests. J. Comput. Syst. Sci. 7 (1973), 376–378.CrossRefGoogle Scholar
[24]Shields, P. C.. Universal almost sure data compression using Markov types. Prob. Control and Inform. Th. 19 (1990), 269–277.Google Scholar
[25]Solomonoff, R. J.. A formal theory of inductive inference. Information and Control. 7 (1964), 1–22. 224–254.CrossRefGoogle Scholar
[26]Turing, A.. On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. 42 (1936), 230–265.Google Scholar
[27]Uspenskii, V. A., Semenov, A. L. & Shen, A. Kh.. Can an individual sequence of zeroes and ones be random?. Russian Mat. Surveys 45 (1990), 121–189.CrossRefGoogle Scholar
[28]Lambalgen, M. Van. Von Mises' definition of random sequences reconsidered. J. Symbolic Logic 52 (1987), 725–755.CrossRefGoogle Scholar
[29]von Neumann, J.. Theory of Self-Reproducing Automata. Edited and completed by Burks, A. W.. University of Illinois Press, Illinois, 1966.Google Scholar
[30]Vovk, V. G.. The law of the iterated logarithm for random Kolmogorov, or chaotic, sequences. Theory of Probability and its Applications 32 (1987), 413–425 (Engl. transl.).CrossRefGoogle Scholar
[31]White, H. S.. On the algorithmic complexity of trajectories of points in dynamical systems. PhD Dissertation. University of North Carolina at Chapel Hill, 1991.Google Scholar
[32]Yang, Enhui. The proof of Levin's conjecture. Chinese Sci. Bull. 34 (1989), 1761–1765.Google Scholar
[33]Zvonkin, A. K. & Levin, L. A.. The complexity of finite objects and the algorithm-theoretic foundations of the notions of information and randomness. (Engl. transl.) Russian Math. Surveys 25 (1970), no. 683–124.CrossRefGoogle Scholar