Chaitin Ω Numbers and Halting Problems

DOI10.1007/978-3-642-03073-4_46zbMath1268.68088arXiv0904.1149MaRDI QIDQ3576077

Kohtaro Tadaki

Publication date: 28 July 2010

Published in: Mathematical Theory and Computational Practice (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic information theory; halting problem; algorithmic randomness; Chaitin \(\Omega \) number; program-size complexity; Turing reduction

Mathematics Subject Classification ID

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

Related Items

Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers, Kobayashi compressibility, Computing halting probabilities from other halting probabilities, Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega, Phase Transition between Unidirectionality and Bidirectionality, LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY

Cites Work

• Unnamed Item
• Randomness and Recursive Enumerability
• Algorithmic Randomness and Complexity
• On initial segment complexity and degrees of randomness
• Algorithmic Information Theory
• A Theory of Program Size Formally Identical to Information Theory
• Computability and Randomness
• Recursively enumerable reals and Chaitin \(\Omega\) numbers