Chaitin Ω Numbers and Halting Problems

DOI10.1007/978-3-642-03073-4_46zbMath1268.68088arXiv0904.1149OpenAlexW117701256MaRDI 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 theoryhalting problemalgorithmic randomnessChaitin \(\Omega \) numberprogram-size complexityTuring reduction

Mathematics Subject Classification ID

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

Related Items (6)

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

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

This page was built for publication: Chaitin Ω Numbers and Halting Problems