dc.contributor.author |
Calude, C.S |
en |
dc.contributor.author |
Juergensen, H |
en |
dc.date.accessioned |
2009-04-16T23:11:36Z |
en |
dc.date.available |
2009-04-16T23:11:36Z |
en |
dc.date.issued |
2004-06 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-241 (2004) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3748 |
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 |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial |
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 |
http://purl.org/eprint/accessRights/OpenAccess |
en |