Is complexity a source of incompleteness?
From MaRDI portal
Publication:2386137
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
incompletenessGödel numberingcomplexity of sentencesunprovabilitycomplexity measurecomplexity of a theory
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?