Chaitin Ω Numbers and Halting Problems
From MaRDI portal
Publication:3576077
DOI10.1007/978-3-642-03073-4_46zbMath1268.68088arXiv0904.1149MaRDI 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 theory; halting problem; algorithmic randomness; Chaitin \(\Omega \) number; program-size complexity; Turing reduction
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