Information-theoretic incompleteness

DOI10.1016/0096-3003(92)90099-MMaRDI QIDQ1200218zbMATH OpenOpenAlexFDO

Authors 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

algorithmic entropycomplexity of a formal axiomatic systemincompleteness theorem for diophantine equationsrandomness

Mathematics Subject Classification ID

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

Review text

In this interesting note the author continues his many investigations of the incompleteness of basic topological systems. Several fundamental incompleteness theorems in his book on algorithmic information theory [Algorithmic information theory (1987; Zbl 0655.68003)] are reformulated based upon an improved definition of the complexity of a formal axiomatic system. The value added comes from measuring the complexity of a formal system in terms of the program-size complexity of enumerating its infinite set of theorems rather than in terms of the program-size complexity of the finite strings of axioms. Included is an incompleteness theorem for diophantine equations.

Recommendations

• scientific article; zbMATH DE number 6845503
• Algorithmic Information Theory
• Gödel's theorem and information
• scientific article; zbMATH DE number 44959
• Is complexity a source of incompleteness?

Cites work

• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic entropy of sets
• Algorithmic Information Theory
• Gödel's theorem and information
• scientific article; zbMATH DE number 412253 (Why is no real title available?)
• scientific article; zbMATH DE number 44959 (Why is no real title available?)
• scientific article; zbMATH DE number 53540 (Why is no real title available?)
• scientific article; zbMATH DE number 976355 (Why is no real title available?)
• Incompleteness theorems for random reals
• Information-theoretic computation complexity
• Information-Theoretic Limitations of Formal Systems
• Proof of Recursive Unsolvability of Hilbert's Tenth Problem
• RANDOMNESS AND COMPLEXITY IN PURE MATHEMATICS
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets

Cited in

(18)

• Incompleteness theorems for random reals
• Incompleteness in a topos
• Epistemic horizons and the foundations of quantum mechanics
• Is independence an exception?
• Gödel's theorem and information
• To the problem of incompleteness of theoretical constructs (illustrated by examples of formalization of some problems of natural sciences)
• Is complexity a source of incompleteness?
• Quantum principles and mathematical computability
• scientific article; zbMATH DE number 5158914 (Why is no real title available?)
• Algorithmic Information Theory
• Responses to ``Theoretical Mathematics: Toward\\ a cultural synthesis of mathematics and\\ theoretical physics, by A. Jaffe and F. Quinn
• Infinite Divisibility of Information
• scientific article; zbMATH DE number 5046294 (Why is no real title available?)
• From Heisenberg to Gödel via Chaitin
• From Heisenberg to Gödel via Chaitin
• Incomplete information: Structure, inference, complexity
• Randomness as an invariant for number representations
• On chaotic and random sequences

This page was built for publication: Information-theoretic incompleteness

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