David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Philosophical Logic 27 (6):569-586 (1998)
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
George Boolos, John Burgess, Richard P. & C. Jeffrey (2007). Computability and Logic. Cambridge University Press.
Joseph R. Shoenfield (1967). Mathematical Logic. Reading, Mass.,Addison-Wesley Pub. Co..
W. V. Quine (1951). Mathematical Logic. Cambridge, Harvard University Press.
Piergiorgio Odifreddi (1989). Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers. Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
Citations of this work BETA
Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson & Keita Yokoyama (2014). Propagation of Partial Randomness. Annals of Pure and Applied Logic 165 (2):742-758.
Jörgen Sjögren (2008). On Explicating the Concept the Power of an Arithmetical Theory. Journal of Philosophical Logic 37 (2):183 - 202.
Shingo Ibuka, Makoto Kikuchi & Hirotaka Kikyo (2011). Kolmogorov Complexity and Characteristic Constants of Formal Theories of Arithmetic. Mathematical Logic Quarterly 57 (5):470-473.
Similar books and articles
Michiel Van Lambalgen (1989). Algorithmic Information Theory. Journal of Symbolic Logic 54 (4):1389 - 1400.
Yi-Zhuang Chen (2004). Edgar Morin's Paradigm of Complexity and Gödel's Incompleteness Theorem. World Futures 60 (5 & 6):421 – 431.
Panu Raatikainen (2005). On the Philosophical Relevance of Gödel's Incompleteness Theorems. Revue Internationale de Philosophie 59 (4):513-534.
Gregory J. Chaitin (1970). Computational Complexity and Godel's Incompleteness Theorem. [Rio De Janeiro,Centro Técnico Científico, Pontifícia Universidade Católica Do Rio De Janeiro.
Panu Raatikainen (2000). Algorithmic Information Theory and Undecidability. Synthese 123 (2):217-225.
Added to index2009-01-28
Total downloads71 ( #59,409 of 1,796,214 )
Recent downloads (6 months)22 ( #33,599 of 1,796,214 )
How can I increase my downloads?