• search hit 17 of 41
Back to Result List

Is complexity a source of incompleteness?

  • In this paper we prove Chaitin's "heuristic principle," the theorems of a finitely-specified theory cannot be significantly more complex than the theory itself, for an appropriate measure of complexity. We show that the measure is invariant under the change of the Godel numbering. For this measure, the theorems of a finitely-specified, sound, consistent theory strong enough to formalize arithmetic which is arithmetically sound (like Zermelo-Fraenkel set theory with choice or Peano Arithmetic) have bounded complexity, hence every sentence of the theory which is significantly more complex than the theory is unprovable. Previous results showing that incompleteness is not accidental, but ubiquitous are here reinforced in probabilistic terms: the probability that a true sentence of length n is provable in the theory tends to zero when n tends to infinity, while the probability that a sentence of length n is true is strictly positive. (c) 2004 Elsevier Inc. All rights reserved

Export metadata

Additional Services

Search Google Scholar Statistics
Metadaten
Author details:C. S. Calude, Helmut Jurgensen
ISSN:0196-8858
Publication type:Article
Language:English
Year of first publication:2005
Publication year:2005
Release date:2017/03/24
Source:Advances in Applied Mathematics. - ISSN 0196-8858. - 35 (2005), 1, S. 1 - 15
Organizational units:Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science
Peer review:Referiert
Institution name at the time of the publication:Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik
Accept ✔
This website uses technically necessary session cookies. By continuing to use the website, you agree to this. You can find our privacy policy here.