# On interpreting Chaitin's incompleteness theorem

*Journal of Philosophical Logic*27 (6):569-586 (1998)

**Abstract**

The aim of this paper is to comprehensively question the validity of the standard way of interpreting Chaitin's famous incompleteness theorem, which says that for every formalized theory of arithmetic there is a finite constant c such that the theory in question cannot prove any particular number to have Kolmogorov complexity larger than c. The received interpretation of theorem claims that the limiting constant is determined by the complexity of the theory itself, which is assumed to be good measure of the strength of the theory. I exhibit certain strong counterexamples and establish conclusively that the received view is false. Moreover, I show that the limiting constants provided by the theorem do not in any way reflect the power of formalized theories, but that the values of these constants are actually determined by the chosen coding of Turing machines, and are thus quite accidental

**Categories**

(categorize this paper)

**Reprint years**

2004

**PhilPapers/Archive ID**

RAAOIC

**Revision history**

Archival date: 2017-04-11

View upload history

View upload history

References found in this work BETA

Mathematical Logic.Shoenfield, Joseph R.

Classical Recursion Theory.Hinman, Peter G.

View all 15 references / Add more references

Citations of this work BETA

Propagation of Partial Randomness.Higuchi, Kojiro; Hudelson, W. M. Phillip; Simpson, Stephen G. & Yokoyama, Keita

Algorithmic Information Theory and Undecidability.Raatikainen, Panu

Gedankenexperimente in der Philosophie.Cohnitz, Daniel

Exploring Randomness.Raatikainen, Panu

Incompleteness, Complexity, Randomness and Beyond.Calude, Cristian S.

View all 8 citations / Add more citations

**Added to PP index**

2009-01-28

**Total views**

403 ( #9,948 of 47,363 )

**Recent downloads (6 months)**

45 ( #17,790 of 47,363 )

How can I increase my downloads?

**Downloads since first upload**

*This graph includes both downloads from PhilArchive and clicks to external links.*