On interpreting Chaitin's incompleteness theorem

DOI10.1023/A:1004305315546zbMath0921.03004MaRDI QIDQ1277329

Raatikainen, Panu

Publication date: 29 September 1999

Published in: Journal of Philosophical Logic (Search for Journal in Brave)

zbMATH Keywords

algorithmic information theoryKolmogorov complexityGödel numberingsChaitin's incompleteness theoremcodings of Turing machinesquantum communications theorystrength of a theory

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) First-order arithmetic and fragments (03F30) Turing machines and related notions (03D10)

Related Items

Observation of Unbounded Novelty in Evolutionary Algorithms is Unknowable ⋮ Is complexity a source of incompleteness? ⋮ Randomness? What randomness? ⋮ Propagation of partial randomness ⋮ On Characteristic Constants of Theories Defined by Kolmogorov Complexity ⋮ Revisiting Chaitin's incompleteness theorem ⋮ The scope of Gödel's first incompleteness theorem ⋮ On explicating the concept `the power of an arithmetical theory' ⋮ Kolmogorov complexity and characteristic constants of formal theories of arithmetic ⋮ Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classical recursion theory. The theory of functions and sets of natural numbers
• Gödel's theorem and information
• Algorithmic information theory
• Gödel numberings of partial recursive functions
• Algorithmic Information Theory
• Information-theoretic computation complexity
• Information-Theoretic Limitations of Formal Systems
• Reflection Principles and their Use for Establishing the Complexity of Axiomatic Systems
• On notation for ordinal numbers