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

halting probabilityrandom realsTuring machine

Mathematics Subject Classification ID

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

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 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

(24)

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

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)