Chaitin Ω Numbers and Halting Problems
From MaRDI portal
Publication:3576077
DOI10.1007/978-3-642-03073-4_46zbMath1268.68088arXiv0904.1149OpenAlexW117701256MaRDI QIDQ3576077
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
algorithmic information theoryhalting problemalgorithmic randomnessChaitin \(\Omega \) numberprogram-size complexityTuring reduction
Related Items
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