RELATIVIZING CHAITIN'S HALTING PROBABILITY

DOI10.1142/S0219061305000468zbMath1093.03025MaRDI QIDQ3379458

Denis R. Hirschfeldt, André Nies, Joseph S. Miller, Rodney G. Downey

Publication date: 6 April 2006

Published in: Journal of Mathematical Logic (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexityhalting probabilityeffective randomness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10)

Related Items

Randomness and differentiability ⋮ Cupping with random sets ⋮ Defining a randomness notion via another ⋮ Randomness and universal machines ⋮ Universality probability of a prefix-free machine ⋮ Propagation of partial randomness ⋮ Depth, Highness and DNR Degrees ⋮ CHAITIN’S Ω AS A CONTINUOUS FUNCTION ⋮ On initial segment complexity and degrees of randomness ⋮ Relativized depth ⋮ PA RELATIVE TO AN ENUMERATION ORACLE ⋮ On the gap between trivial and nontrivial initial segment prefix-free complexity ⋮ Computability theory. Abstracts from the workshop held April 25 -- May 1, 2021 (hybrid meeting) ⋮ The axiomatic power of Kolmogorov complexity ⋮ Two more characterizations of \(K\)-triviality ⋮ \(\Pi_1^0 \) classes, LR degrees and Turing degrees ⋮ Effectively closed sets of measures and randomness ⋮ Random numbers as probabilities of machine behavior ⋮ Lowness properties and approximations of the jump ⋮ Things that can be made into themselves ⋮ The importance of Π₁⁰ classes in effective randomness ⋮ Computing halting probabilities from other halting probabilities ⋮ Difference randomness ⋮ Chaitin's halting probability and the compression of strings using oracles ⋮ Randomness and Computability: Open Questions ⋮ Calibrating Randomness ⋮ Measures and their random reals ⋮ Non-cupping and randomness ⋮ Cone avoidance and randomness preservation ⋮ THE REVERSE MATHEMATICS OF THEOREMS OF JORDAN AND LEBESGUE

Cites Work

• Lowness properties and randomness
• Randomness and Recursive Enumerability
• Algorithmic Randomness and Complexity
• Relative randomness and real closed fields
• Every sequence is reducible to a random one
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic Information Theory
• There is no degree invariant half-jump
• The axiomatization of randomness
• The definition of random sequences
• Randomness, relativization and Turing degrees
• Creative sets