CHAITIN’S Ω AS A CONTINUOUS FUNCTION

DOI10.1017/jsl.2019.60zbMath1471.03068OpenAlexW2972880515MaRDI QIDQ5107240

Wolfgang Merkle, Rupert Hölzl, Liang Yu, Joseph S. Miller, Frank Stephan

Publication date: 17 April 2020

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/jsl.2019.60

zbMATH Keywords

Kolmogorov complexitycomputable analysisChaitin's number

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32) Computation over the reals, computable analysis (03D78)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random numbers as probabilities of machine behavior
• Representation of left-computable \(\varepsilon \)-random reals
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Analogues of Chaitin's Omega in the computably enumerable sets
• Time-bounded Kolmogorov complexity and Solovay functions
• Denjoy, Demuth and density
• COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS
• Algorithmic Randomness and Complexity
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Randomness and halting probabilities
• On initial segment complexity and degrees of randomness
• A Theory of Program Size Formally Identical to Information Theory
• USING ALMOST-EVERYWHERE THEOREMS FROM ANALYSIS TO STUDY RANDOMNESS
• The Probability of a Computable Output from a Random Oracle
• Kolmogorov Complexity and Solovay Functions
• Computing and Combinatorics
• Random reals and possibly infinite computations Part I: Randomness in ∅′