On partial randomness

DOI10.1016/J.APAL.2005.06.004zbMath1077.03022DBLPjournals/apal/CaludeST06OpenAlexW2062443283WikidataQ57001647 ScholiaQ57001647MaRDI QIDQ2576938

Ludwig Staiger, Sebastiaan A. Terwijn, Cristian S. Calude

Publication date: 29 December 2005

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2005.06.004

zbMATH Keywords

martingalesHausdorff dimensionpartial randomnessprogram-size complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (28)

On Oscillation-Free Chaitin h-Random Sequences ⋮ Phase Transition between Unidirectionality and Bidirectionality ⋮ Partial Randomness and Dimension of Recursively Enumerable Reals ⋮ The Kolmogorov complexity of infinite words ⋮ Introduction: computability of the physical ⋮ A statistical mechanical interpretation of algorithmic information theory III: composite systems and fixed points ⋮ Algorithmic thermodynamics ⋮ MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY ⋮ Natural halting probabilities, partial randomness, and zeta functions ⋮ Propagation of partial randomness ⋮ Fixed point theorems on partial randomness ⋮ Exact constructive and computable dimensions ⋮ COMPLEXITY, INFORMATION, ENERGY ⋮ Algorithmically Independent Sequences ⋮ Algorithmic information theory and its statistical mechanical interpretation ⋮ Effectively closed sets of measures and randomness ⋮ Refined Bounds on Kolmogorov Complexity for ω-Languages ⋮ On Oscillation-free ε-random Sequences ⋮ Algorithmically independent sequences ⋮ A Chaitin \(\Omega\) number based on compressible strings ⋮ Representation of left-computable \(\varepsilon \)-random reals ⋮ Fixed Point Theorems on Partial Randomness ⋮ Liouville, computable, Borel normal and Martin-Löf random numbers ⋮ Unnamed Item ⋮ Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension ⋮ Calibrating Randomness ⋮ Cone avoidance and randomness preservation ⋮ Finite state incompressible infinite sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The extent and density of sequences within the minimal-program complexity hierarchies
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• The dimensions of individual strings and sequences
• Kolmogorov complexity and Hausdorff dimension
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Algorithmic Randomness and Complexity
• Relations between varieties of kolmogorov complexities
• The definition of random sequences
• Randomness, relativization and Turing degrees

This page was built for publication: On partial randomness