On interpreting Chaitin's incompleteness theorem (Q1277329)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On interpreting Chaitin's incompleteness theorem |
scientific article |
Statements
On interpreting Chaitin's incompleteness theorem (English)
0 references
29 September 1999
0 references
The author undertakes a detailed explication of the usual interpretation of Chaitin's incompleteness theorem of algorithmic information theory, viz., for each formalized theory of arithmetic there exists a bounded constant \(c\) such that the theory cannot prove any particular number has Kolmogorov complexity exceeding \(c\). The usual interpretation claims that the constant is determined by the complexity of the theory and measures the strength of the theory. It is argued, by means of counterexamples, that the usual interpretation is false, in general. The usual interpretation results from a confusion of syntactical form and semantical content. Indeed, (1) the usual measure of strength of a theory depends on accidental features of Gödel numberings and codings of Turing machines and (2) Chaitin's techniques cannot provide the basic minimal constant, in general. Interesting special cases where the constant is computable would have implications for quantum communications theory.
0 references
Chaitin's incompleteness theorem
0 references
algorithmic information theory
0 references
Kolmogorov complexity
0 references
strength of a theory
0 references
Gödel numberings
0 references
codings of Turing machines
0 references
quantum communications theory
0 references
0 references