Randomness, Computation and Mathematics

DOI10.1007/978-3-642-30870-3_17zbMath1358.03058OpenAlexW24458641MaRDI QIDQ2904405

Rodney G. Downey

Publication date: 14 August 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-30870-3_17

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Related Items (1)

Monotonous betting strategies in warped casinos

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
• Unnamed Item
• Unnamed Item
• Randomness on computable probability spaces -- a dynamical point of view
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• Mass problems associated with effectively closed sets
• Effectively closed sets of measures and randomness
• A characterization of the entropies of multidimensional shifts of finite type
• Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences
• Effective dimension of points visited by Brownian motion
• The metamathematics of ergodic theory
• On the relation between descriptional complexity and algorithmic probability
• Mathematical metaphysics of randomness
• The descriptive complexity of Brownian motion
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Limit complexities revisited
• Symbolic dynamics: entropy = dimension = complexity
• Strong jump-traceability. I: The computably enumerable case
• Dynamics of a generic Brownian motion: Recursive aspects
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Lowness properties and randomness
• What can be efficiently reduced to the Kolmogorov-random strings?
• Randomness and Recursive Enumerability
• Martin-Löf random points satisfy Birkhoff’s ergodic theorem for effectively closed sets
• Turing’s Normal Numbers: Towards Randomness
• Limits on the Computational Power of Random Strings
• Kolmogorov complexity and strong approximation of Brownian motion
• Increasing the gap between descriptional complexity and algorithmic probability
• Algorithmic Randomness and Complexity
• Time-Bounded Kolmogorov Complexity and Solovay Functions
• Randomness and Computability: Open Questions
• Calibrating Randomness
• Randomness and differentiability
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Ergodic-Type Characterizations of Algorithmic Randomness
• From index sets to randomness in ∅ⁿ: random reals and possibly infinite computations part II
• Every sequence is reducible to a random one
• A Theory of Program Size Formally Identical to Information Theory
• On the complexity of random strings
• The importance of Π₁⁰ classes in effective randomness
• Information Distance in Multiples
• Kolmogorov Complexity and Solovay Functions
• Reconciling Data Compression and Kolmogorov Complexity
• Kolmogorov Complexity with Error
• Non-computable Julia sets
• Power from Random Strings
• A unified approach to the definition of random sequences
• The definition of random sequences
• Randomness, relativization and Turing degrees
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Effective randomness for continuous measures
• Kolmogorov entropy in the context of computability theory

This page was built for publication: Randomness, Computation and Mathematics