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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
Bar-Hillel, Y. (1964). Language and Information: Selected Essays on Their Theory and Application, Addison-Wesley and The Jerusalem Academic Press, Reading, MA and Jerusalem.
Boolos, G. S. and Jeffrey, R. C. (1989). Computability and Logic, third edition, Cambridge University Press, Cambridge.
Chaitin, G. J. (1974a). Information-theoretic computational complexity, IEEE Transactions on Information Theory IT-20, 10–15.
Chaitin, G. J. (1974b). Information-theoretic limitations of formal systems, J. of the ACM 21, 403–424.
Chaitin, G. J. (1975). Randomness and mathematical proof, Scientific American 232(5), 47–52.
Chaitin, G. J. (1977). Algorithmic information theory, IBM Journal of Research and Development 21, 350–359, 496.
Chaitin, G. J. (1982). Gödel's theorem and information, Internat. J. Theoret. Phys. 22, 941–954.
Davis, M. (1978). What is a computation?, in Mathematics Today (L. A. Stern, ed.), Springer-Verlag, Berlin, 241–267.
Delahaye, J.-P. (1989). Chaitin's equation: an extension of Gödel's theorem, Notices of the A.M.S. 36(8), 984–7.
Kleene, S. K. (1938). On notations for ordinal numbers, J. Symbolic Logic 3, 150–155.
Kreisel, G. and Levy, A. (1968). Reflection principles and their uses for establishing the complexity of axiomatic systems, Z. Math. Logik Grundlag. Math. 14, 97–142.
van Lambalgen, M. (1989). Algorithmic information theory, J. Symbolic Logic 54, 1389–1400.
Odifreddi, P. (1989). Classical Recursion Theory, North-Holland, Amsterdam.
Quine, W. V. (1940). Mathematical Logic, W. W. Norton, New York.
Rogers, H. (1958). Gödel numbering of partial recursive functions, J. Symbolic Logic 23, 331–341.
Rogers, H. (1967). Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York.
Rucker, R. (1987). Mind Tools, Houghton Mifflin, Boston.
Ruelle, D. (1991). Chance and Chaos, Princeton University Press, Princeton.
Shoenfield, J. R. (1967). Mathematical Logic, Addison-Wesley, Reading, MA.
Stewart, I. (1992). The Problems of Mathematics, Oxford University Press, Oxford.
Tymoczko, T. (ed.) (1986). New Directions in the Philosophy of Mathematics, Birkhäuser, Boston.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Raatikainen, P. On Interpreting Chaitin's Incompleteness Theorem. Journal of Philosophical Logic 27, 569–586 (1998). https://doi.org/10.1023/A:1004305315546
Issue Date:
DOI: https://doi.org/10.1023/A:1004305315546