Is Complexity a Source of Incompleteness?

Show simple item record Calude, C.S en Juergensen, H en 2009-04-16T23:11:36Z en 2009-04-16T23:11:36Z en 2004-06 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-241 (2004) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri en
dc.description.abstract In this paper we prove Chaitin’s “heuristic principle”, the theorems of a finitelyspecified 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 G¨odel 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. en
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights.uri en
dc.source.uri en
dc.title Is Complexity a Source of Incompleteness? en
dc.type Technical Report en
dc.subject.marsden Fields of Research::280000 Information, Computing and Communication Sciences en
dc.rights.holder The author(s) en
dc.rights.accessrights en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace