Randomness and halting probabilities

DOI10.2178/JSL/1164060463MaRDI QIDQ3416122zbMATH OpenOpenAlexWikidataFDO

Authors Verónica Becher, Santiago Figueira, Serge Grigorieff, Joseph S. Miller

Publication date 19 January 2007

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

Full work available at URL https://doi.org/10.2178/jsl/1164060463

zbMATH Keywords

Turing machinerandom realshalting 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)

Recommendations

• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Random numbers as probabilities of machine behavior
• The probability of a computable output from a random oracle
• Computing halting probabilities from other halting probabilities
• Chaitin \(\Omega \) numbers and halting problems

Cites work

• A Theory of Program Size Formally Identical to Information Theory
• Randomness and recursive enumerability
• Randomness, computability, and density
• Recursively enumerable reals and Chaitin \(\Omega\) numbers

Cited in

(23)

• Computing halting probabilities from other halting probabilities
• Randomness and universal machines
• Every computably enumerable random real is provably computably enumerable random
• \(\Sigma^ 0_ n\)-complete properties of programs and Martin-Löf randomness
• Random reals à la Chaitin with or without prefix-freeness
• scientific article; zbMATH DE number 4079400 (Why is no real title available?)
• Natural halting probabilities, partial randomness, and zeta functions
• What percentage of programs halt?
• From index sets to randomness in ∅ⁿ: random reals and possibly infinite computations part II
• Recursive events in random sequences
• Universality probability of a prefix-free machine
• scientific article; zbMATH DE number 1665444 (Why is no real title available?)
• scientific article; zbMATH DE number 1886067 (Why is no real title available?)
• The probability of a computable output from a random oracle
• Chaitin's \(\Omega\) as a continuous function
• A variant of Chaitin's Omega function
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Chaitin's halting probability and the compression of strings using oracles
• Kolmogorov complexity in perspective. I: Information theory and randomness
• Randomness and uniform distribution modulo one
• Differences of halting probabilities
• Random numbers as probabilities of machine behavior
• Kobayashi compressibility

This page was built for publication: Randomness and halting probabilities

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