Re: Computing Randomness

From: Hal Ruhl <hjr.domain.name.hidden>
Date: Thu, 12 Apr 2001 21:21:41 -0700

Dear Russell:

At 4/13/01, you wrote:
>Bounded complexity does not imply bounded length. Examples include an
>infinite sting of '0's, and the string '1234...9101112...'

That was part of the old debate and one of my initial mistakes. I am not
now talking about the length of theorems but the length of their proofs.


>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?

With this I agree. There are however only a finite number of theorems
with a finite complexity. So number theory is either finite in theorem
count or it is infinite in complexity.

Hal
Received on Thu Apr 12 2001 - 18:26:57 PDT