Information-theoretic incompleteness

DOI10.1016/0096-3003(92)90099-MzbMath0776.68065OpenAlexW1969403659MaRDI QIDQ1200218

Gregory J. Chaitin

Publication date: 17 January 1993

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0096-3003(92)90099-m

zbMATH Keywords

randomnessalgorithmic entropycomplexity of a formal axiomatic systemincompleteness theorem for diophantine equations

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Proof theory and constructive mathematics (03F99)

Related Items (9)

Is complexity a source of incompleteness? ⋮ Responses to ``Theoretical Mathematics: Toward\\ a cultural synthesis of mathematics and\\ theoretical physics, by A. Jaffe and F. Quinn ⋮ Randomness as an invariant for number representations ⋮ Epistemic horizons and the foundations of quantum mechanics ⋮ On chaotic and random sequences ⋮ Quantum principles and mathematical computability ⋮ Is independence an exception? ⋮ From Heisenberg to Gödel via Chaitin ⋮ From Heisenberg to Gödel via Chaitin

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Incompleteness theorems for random reals
• Algorithmic entropy of sets
• Gödel's theorem and information
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• Proof of Recursive Unsolvability of Hilbert's Tenth Problem
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic Information Theory
• RANDOMNESS AND COMPLEXITY IN PURE MATHEMATICS
• Information-theoretic computation complexity
• Information-Theoretic Limitations of Formal Systems

This page was built for publication: Information-theoretic incompleteness