On interpreting Chaitin's incompleteness theorem

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

Panu Raatikainen
University of Tampere
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
Keywords algorithmic information theory  incompleteness  Kolmogorov complexity
Categories (categorize this paper)
Reprint years 2004
DOI 10.1023/A:1004305315546
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

References found in this work BETA

Mathematical Logic.Joseph R. Shoenfield - 1967 - Reading, Mass., Addison-Wesley Pub. Co..
Computability and Logic.George S. Boolos, John P. Burgess & Richard C. Jeffrey - 2003 - Bulletin of Symbolic Logic 9 (4):520-521.
Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.

View all 17 references / Add more references

Citations of this work BETA

Exploring Randomness.Panu Raatikainen - 2001 - Notices of the AMS 48 (9):992-6.

View all 8 citations / Add more citations

Similar books and articles


Added to PP index

Total views
414 ( #14,425 of 2,309,716 )

Recent downloads (6 months)
40 ( #19,201 of 2,309,716 )

How can I increase my downloads?


My notes

Sign in to use this feature