On explicating the concept `the power of an arithmetical theory'

DOI10.1007/s10992-007-9077-8zbMath1146.03004OpenAlexW2091409696MaRDI QIDQ2481252

Jörgen Sjögren

Publication date: 9 April 2008

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

Full work available at URL: https://doi.org/10.1007/s10992-007-9077-8

zbMATH Keywords

computational complexityalgorithmic information theoryrandomnessrecursion theoryaxiomatic set theory

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Consistency and independence results (03E35) Applications of computability and recursion theory (03D80) Ordinal and cardinal numbers (03E10)

Related Items

Revisiting Chaitin's incompleteness theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On interpreting Chaitin's incompleteness theorem
• Classical recursion theory. Vol. II
• Sharp estimates for the non-centered maximal operator associated to Gaussian and other radial measures.
• Gödel's theorem and information
• Algorithmic information theory
• Extremely undecidable sentences
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic Information Theory
• Information-Theoretic Limitations of Formal Systems
• Algorithmic information theory and undecidability