Chaitin \(\Omega\) numbers, Solovay machines, and Gödel incompleteness.

DOI10.1016/S0304-3975(01)00068-8zbMath1042.68045WikidataQ57001702 ScholiaQ57001702MaRDI QIDQ1607291

Cristian S. Calude

Publication date: 31 July 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Random realChaitin machineComputably enumerable realInformation-theoretic incompleteness

Mathematics Subject Classification ID

Related Items

Is complexity a source of incompleteness? ⋮ Simplicity via provability for universal prefix-free Turing machines ⋮ EXACT APPROXIMATIONS OF OMEGA NUMBERS ⋮ Selection by Recursively Enumerable Sets ⋮ Information: The Algorithmic Paradigm ⋮ Computing a Glimpse of Randomness ⋮ From Heisenberg to Gödel via Chaitin ⋮ From Heisenberg to Gödel via Chaitin

Cites Work

• Classical recursion theory. The theory of functions and sets of natural numbers
• Presentations of computably enumerable reals.
• Randomness and Recursive Enumerability
• Algorithmic Information Theory
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic Information Theory
• A characterization of c. e. random reals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item