RELATIVIZING CHAITIN'S HALTING PROBABILITY

DOI10.1142/S0219061305000468MaRDI QIDQ3379458zbMATHFDO

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

Publication date 6 April 2006

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

zbMATH Keywords

Kolmogorov complexityeffective randomnesshalting probability

Mathematics Subject Classification ID

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

Recommendations

• Randomness and halting probabilities
• Computing halting probabilities from other halting probabilities
• Chaitin \(\Omega \) numbers and halting problems
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• Chaitin's halting probability and the compression of strings using oracles

Cites work

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

Cited in

(44)

• Randomness and halting probabilities
• THE REVERSE MATHEMATICS OF THEOREMS OF JORDAN AND LEBESGUE
• Randomness and universal machines
• Chaitin's \(\Omega\) as a continuous function
• Computing halting probabilities from other halting probabilities
• Representation of left-computable \(\varepsilon \)-random reals
• Differences of halting probabilities
• Defining a randomness notion via another
• Measures and their random reals
• Relativized depth
• An extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system
• The axiomatic power of Kolmogorov complexity
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• Things that can be made into themselves
• Analogues of Chaitin's Omega in the computably enumerable sets
• Cupping with random sets
• Lowness properties and approximations of the jump
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Natural halting probabilities, partial randomness, and zeta functions
• Non-cupping and randomness
• \(\Sigma^ 0_ n\)-complete properties of programs and Martin-Löf randomness
• Chaitin \(\Omega \) numbers and halting problems
• \(\Pi_1^0 \) classes, LR degrees and Turing degrees
• Difference randomness
• Propagation of partial randomness
• Effectively closed sets of measures and randomness
• Universality probability of a prefix-free machine
• PA RELATIVE TO AN ENUMERATION ORACLE
• Computability theory. Abstracts from the workshop held April 25 -- May 1, 2021 (hybrid meeting)
• Random reals à la Chaitin with or without prefix-freeness
• The importance of \(\Pi^0_1\) classes in effective randomness
• scientific article; zbMATH DE number 1665444 (Why is no real title available?)
• Calibrating Randomness
• Randomness and Computability: Open Questions
• Chaitin's halting probability and the compression of strings using oracles
• Cone avoidance and randomness preservation
• Random numbers as probabilities of machine behavior
• Randomness and differentiability
• On initial segment complexity and degrees of randomness
• The probability of a computable output from a random oracle
• Universal recursively enumerable sets of strings
• Two more characterizations of \(K\)-triviality
• Depth, highness and DNR degrees
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega

This page was built for publication: RELATIVIZING CHAITIN'S HALTING PROBABILITY

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3379458)