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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references