On interpreting Chaitin's incompleteness theorem (Q1277329)

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.