Revisiting Chaitin's incompleteness theorem

DOI10.1215/00294527-2021-0006OpenAlexW3172899346MaRDI QIDQ1982000

Christopher P. Porter

Publication date: 7 September 2021

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1215/00294527-2021-0006

zbMATH Keywords

Kolmogorov complexityalgorithmic randomnessincompleteness theorems

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) Gödel numberings and issues of incompleteness (03F40) Algorithmic randomness and dimension (03D32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stationary algorithmic probability
• On interpreting Chaitin's incompleteness theorem
• Gödel's theorem and information
• The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity
• Is complexity a source of incompleteness?
• The axiomatic power of Kolmogorov complexity
• On explicating the concept `the power of an arithmetical theory'
• Turing Computability
• Algorithmic Randomness and Complexity
• Algorithmic information theory
• Algorithms and Randomness
• The Source of Chaitin's Incorrectness
• Information-Theoretic Limitations of Formal Systems
• The Equivalence of Definitions of Algorithmic Randomness†
• Randomness Is Unpredictability
• The definition of random sequences
• ON ANALOGUES OF THE CHURCH–TURING THESIS IN ALGORITHMIC RANDOMNESS
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Revisiting Chaitin's incompleteness theorem