Is complexity a source of incompleteness?

DOI10.1016/j.aam.2004.10.003zbMath1086.03047arXivmath/0408144OpenAlexW2081148745WikidataQ57001671 ScholiaQ57001671MaRDI QIDQ2386137

Cristian S. Calude, Helmut Jürgensen

Publication date: 22 August 2005

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

Full work available at URL: https://arxiv.org/abs/math/0408144

zbMATH Keywords

incompletenessGödel numberingcomplexity of sentencesunprovabilitycomplexity measurecomplexity of a theory

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of proofs (03F20) Gödel numberings and issues of incompleteness (03F40)

Related Items (13)

Invariance and Universality of Complexity ⋮ Some Transfinite Generalisations of Gödel’s Incompleteness Theorem ⋮ Is there a universal image generator? ⋮ COMPLEXITY, INFORMATION, ENERGY ⋮ Quantum Experiments Can Test Mathematical Undecidability ⋮ Epistemic horizons and the foundations of quantum mechanics ⋮ Revisiting Chaitin's incompleteness theorem ⋮ The scope of Gödel's first incompleteness theorem ⋮ Most programs stop quickly or never halt ⋮ Logical independence and quantum randomness ⋮ Quantum complementarity and logical indeterminacy ⋮ Information: The Algorithmic Paradigm ⋮ Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness

Cites Work

• Incompleteness theorems for random reals
• Information-theoretic incompleteness
• LISP program-size complexity. II
• Theories of computational complexity
• On interpreting Chaitin's incompleteness theorem
• Chaitin \(\Omega\) numbers, Solovay machines, and Gödel incompleteness.
• Is independence an exception?
• Gödel's theorem and information
• Does Gödel's Theorem Matter to Mathematics?
• Algorithmic Randomness and Complexity
• Algorithmic information theory
• A Theory of Program Size Formally Identical to Information Theory
• An addendum to “The work of Kurt Gödel”
• The Source of Chaitin's Incorrectness
• Information-Theoretic Limitations of Formal Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Is complexity a source of incompleteness?