Incompleteness theorems for random reals

DOI10.1016/0196-8858(87)90010-8zbMath0649.03046OpenAlexW2001279301MaRDI QIDQ1105595

Gregory J. Chaitin

Publication date: 1987

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-8858(87)90010-8

zbMATH Keywords

constructive mathematicsrandomnessexponential diophantine equationrandom realsdiophantine theorymodified incompleteness theorems of Gödel typestochastic proofs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Measures of information, entropy (94A17) Second- and higher-order arithmetic and fragments (03F35) Proof theory and constructive mathematics (03F99)

Related Items

Randomness and reducibility, Computational depth and reducibility, Reducibilities relating to Schnorr randomness, Computational depth and reducibility, The dimensions of individual strings and sequences, The Kolmogorov complexity of random reals, Is complexity a source of incompleteness?, QUANTUM ALGORITHMS FOR GENERATING RANDOM SEQUENCES OF INTEGERS, An improved zero-one law for algorithmically random sequences, Fixed point theorems on partial randomness, On initial segment complexity and degrees of randomness, Closed left-r.e. sets, Oscillation in the initial segment complexity of random reals, A Suppes predicate for general relativity and set-theoretically generic spacetimes, Feasible reductions to Kolmogorov-Loveland stochastic sequences, The axiomatic power of Kolmogorov complexity, An incomplete set of shortest descriptions, Computability and randomness of Nash equilibrium in infinite games, The Arnol'd cat: Failure of the correspondence principle, On independent random oracles, Solovay functions and their applications in algorithmic randomness, Closed Left-R.E. Sets, Information-theoretic incompleteness, Things that can be made into themselves, \(\Sigma^ 0_ n\)-complete properties of programs and Martin-Löf randomness, On the computational power of random strings, Efficient exact computation of iterated maps, Unnamed Item, Computing halting probabilities from other halting probabilities, Prefix-free quantum Kolmogorov complexity, Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega, Increasing the gap between descriptional complexity and algorithmic probability, Calibrating Randomness, Quantum algorithmic randomness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The decision problem for exponential diophantine equations
• Gödel's theorem and information
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• A Theory of Program Size Formally Identical to Information Theory
• Information-theoretic computation complexity
• The definition of random sequences
• On Computable Numbers, with an Application to the Entscheidungsproblem