RELATIVIZING CHAITIN'S HALTING PROBABILITY

DOI10.1142/S0219061305000468zbMATH Open1093.03025MaRDI QIDQ3379458FDOQ3379458

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)

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

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)

Cites Work

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

Cited In (41)

• \(\Pi_1^0 \) classes, LR degrees and Turing degrees
• Computing halting probabilities from other halting probabilities
• Universal recursively enumerable sets of strings
• Randomness and universal machines
• Effectively closed sets of measures and randomness
• CHAITIN’S Ω AS A CONTINUOUS FUNCTION
• Representation of left-computable \(\varepsilon \)-random reals
• Relativized depth
• \(\Sigma^ 0_ n\)-complete properties of programs and Martin-Löf randomness
• Random reals à la Chaitin with or without prefix-freeness
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• Natural halting probabilities, partial randomness, and zeta functions
• The importance of \(\Pi^0_1\) classes in effective randomness
• Two more characterizations of \(K\)-triviality
• Analogues of Chaitin's Omega in the computably enumerable sets
• 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)
• Lowness properties and approximations of the jump
• Things that can be made into themselves
• Universality probability of a prefix-free machine
• Title not available (Why is that?)
• Calibrating Randomness
• Randomness and Computability: Open Questions
• Chaitin's halting probability and the compression of strings using oracles
• Randomness and halting probabilities
• Defining a randomness notion via another
• Cone avoidance and randomness preservation
• THE REVERSE MATHEMATICS OF THEOREMS OF JORDAN AND LEBESGUE
• The axiomatic power of Kolmogorov complexity
• Measures and their random reals
• An extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system
• Cupping with random sets
• Randomness and differentiability
• Non-cupping and randomness
• Difference randomness
• On initial segment complexity and degrees of randomness
• Depth, Highness and DNR Degrees
• Chaitin \(\Omega \) numbers and halting problems
• Propagation of partial randomness
• PA RELATIVE TO AN ENUMERATION ORACLE
• Random numbers as probabilities of machine behavior

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)