Re: Computing Randomness

From: Russell Standish <>
Date: Fri, 13 Apr 2001 10:46:31 +1000 (EST)

Hal Ruhl wrote:
> >Basically, Hal believes a finite FAS by definition implies that each
> >theorem is constrained to be no more than N-bits in length.
> Well more precisely that the shortest possible proof chain of any theorem
> of a finite FAS can not be more complex than the limit which Chaitin
> provides. Is this not Chaitin's position? Given that, then there are only
> a finite number of theorems that satisfy this limit on the complexity of
> their shortest proof chains.

Bounded complexity does not imply bounded length. Examples include an
infinite sting of '0's, and the string '1234...9101112...'

It must be true that the set of all theorems derivable from a finite
set of axioms contains no more information (or complexity) than is
contained in the set of axioms itself. However, as pointed out, this
doesn't imply the theorems are bounded in length, merely that their
complexity is bounded.

Does this shed light on this issue?


Dr. Russell Standish Director
High Performance Computing Support Unit, Phone 9385 6967
UNSW SYDNEY 2052 Fax 9385 6965
Room 2075, Red Centre
Received on Thu Apr 12 2001 - 18:19:39 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:07 PST