Is Complexity a Source of Incompleteness?

About this item

Title

Is Complexity a Source of Incompleteness?

Content partner

The University of Auckland Library

Collection

ResearchSpace@Auckland

Description

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)...

Read more

Format

Research paper

Research format

Report

Date created

2004-06

Creator

Calude, C.S / Juergensen, H

URL

http://hdl.handle.net/2292/3748

Related subjects

Information, Computing and Communication Sciences

What is the copyright status of this item?

All Rights Reserved

This item is all rights reserved, which means you'll have to get permission from The University of Auckland Library before using it.

More Information

The University of Auckland Library has this to say about the rights status of this item:

https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm

You can learn more about the rights status of this item at:

• https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
• http://purl.org/eprint/accessRights/OpenAccess

What can I do with this item?

You must always check with The University of Auckland Library to confirm the specific terms of use, but this is our understanding:

Non-infringing use

NZ Copyright law does not prevent every use of a copyright work. You should consider what you can and cannot do with a copyright work.

No sharing

You may not copy and/or share this item with others without further permission. This includes posting it on your blog, using it in a presentation, or any other public use.

No modifying

You are not allowed to adapt or remix this item into any other works.

No commercial use

You may not use this item commercially.