Effective symbolic dynamics, random points, statistical behavior, complexity and entropy

DOI10.1016/j.ic.2009.05.001zbMath1185.68368arXiv0801.0209OpenAlexW2107892052WikidataQ56038299 ScholiaQ56038299MaRDI QIDQ1049402

Mathieu Hoyrup, Stefano Galatolo, Cristobal Rojas

Publication date: 12 January 2010

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0801.0209

zbMATH Keywords

entropyorbit complexityalgorithmic randomnesscomputable partitioneffective symbolic dynamicsKolmogorov-chaitin complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (max. 100)

On stability of probability laws with respect to small violations of algorithmic randomness ⋮ Computability and Dynamical Systems ⋮ Effective S-adic Symbolic Dynamical Systems ⋮ Computability of probability measures and Martin-Löf randomness over metric spaces ⋮ Statistical properties of dynamical systems -- Simulation and abstract computation ⋮ An approach of randomness of a sample based on its weak ergodic limit ⋮ Fiber entropy and algorithmic complexity of random orbits ⋮ Numeration and discrete dynamical systems ⋮ Computability on measurable functions ⋮ Characterization of Kurtz randomness by a differentiation theorem ⋮ Randomness on computable probability spaces -- a dynamical point of view ⋮ Computability, noncomputability, and hyperbolic systems ⋮ Randomness and Determination, from Physics and Computing towards Biology ⋮ On effective Birkhoff's ergodic theorem for computable actions of amenable groups ⋮ Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness ⋮ An Application of Computable Distributions to the Semantics of Probabilistic Programming Languages ⋮ From exact sciences to life phenomena: Following Schrödinger and Turing on programs, life and causality ⋮ Classical, quantum and biological randomness as relative unpredictability ⋮ Schnorr randomness and the Lebesgue differentiation theorem ⋮ Computable Measure Theory and Algorithmic Randomness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamics and abstract computability: computing invariant measures
• Constructive dimension equals Kolmogorov complexity
• A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties
• Ergodic theorems for individual random sequences
• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• What are SRB measures, and which dynamical systems have them?
• Random elements in effective topological spaces with measure.
• Computability on computable metric spaces
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Dynamical systems and computable information
• The dimensions of individual strings and sequences
• Computability of probability measures and Martin-Löf randomness over metric spaces
• Uniform test of algorithmic randomness over a general space
• Applications of Effective Probability Theory to Martin-Löf Randomness
• Эффективная сходимость по вероятности и эргодическая теорема для индивидуальных случайных последовательностей
• Algorithmic complexity of points in dynamical systems
• Orbit complexity by computable structures
• The development of dynamics in the 20th century and the contribution of Jürgen Moser
• Notions of Probabilistic Computability on Represented Spaces

This page was built for publication: Effective symbolic dynamics, random points, statistical behavior, complexity and entropy