Revisiting Chaitin's incompleteness theorem

DOI10.1215/00294527-2021-0006MaRDI QIDQ1982000zbMATH OpenOpenAlexFDO

Authors 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

algorithmic randomnessincompleteness theoremsKolmogorov complexity

Mathematics Subject Classification ID

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

Recommendations

• On interpreting Chaitin's incompleteness theorem
• scientific article; zbMATH DE number 6845503
• On the incompleteness theorems
• scientific article; zbMATH DE number 2222027
• Another look at the second incompleteness theorem
• Remarks on the Incompleteness Proof
• The second incompleteness theorem: reflections and ruminations
• The incompleteness theorems after 70 years
• A reformulation of Chichilnisky's impossibility theorem
• Gödel's incompleteness theorems from a paraconsistent perspective

Cites work

• Algorithmic information theory
• Algorithmic randomness and complexity.
• Algorithms and Randomness
• An introduction to Kolmogorov complexity and its applications
• Computability and randomness
• Gödel's theorem and information
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1327755 (Why is no real title available?)
• scientific article; zbMATH DE number 2198106 (Why is no real title available?)
• Inexhaustibility: A non-exhaustive treatment
• Information-Theoretic Limitations of Formal Systems
• Is complexity a source of incompleteness?
• Meta math! The quest for omega
• On analogues of the Church-Turing thesis in algorithmic randomness
• On explicating the concept `the power of an arithmetical theory'
• On interpreting Chaitin's incompleteness theorem
• Randomness Is Unpredictability
• Stationary algorithmic probability
• The axiomatic power of Kolmogorov complexity
• The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity
• The definition of random sequences
• The equivalence of definitions of algorithmic randomness
• The Source of Chaitin's Incorrectness
• Turing computability. Theory and applications

Cited in

(4)

• The incompleteness of Misra and Chandy's proof systems
• Non-erasing Variants of the Chomsky–Schützenberger Theorem
• scientific article; zbMATH DE number 6845503 (Why is no real title available?)
• The incompleteness theorems after 70 years

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1982000)