On Kurtz randomness

DOI10.1016/j.tcs.2004.03.055zbMath1070.68054OpenAlexW1998987045MaRDI QIDQ1885902

Stephanie Reid, Evan J. Griffiths, Rodney G. Downey

Publication date: 12 November 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.03.055

zbMATH Keywords

Kolmogorov complexityKurtz randomnessRandomnessLowness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Recursively (computably) enumerable sets and degrees (03D25)

Related Items

Sub-computable Bounded Pseudorandomness, Higher Kurtz randomness, Kobayashi compressibility, How powerful are integer-valued martingales?, Process and truth-table characterisations of randomness, Coherence of reducibilities with randomness notions, Algorithmically random series and Brownian motion, Lowness for Kurtz randomness, Lowness and nullsets, Calibrating Randomness, Degrees of sets having no subsets of higher m- and t t-degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Lowness properties and randomness
• Computational randomness and lowness
• Randomness and Recursive Enumerability
• Randomness, Computability, and Density
• On Schnorr and computable randomness, martingales, and machines
• Algorithmic Randomness and Complexity
• Notions of weak genericity
• Von Mises' definition of random sequences reconsidered
• A Theory of Program Size Formally Identical to Information Theory
• Schnorr Randomness
• Lowness for the class of random sets
• Lowness for the Class of Schnorr Random Reals
• A unified approach to the definition of random sequences
• The definition of random sequences