Re: Computing Randomness

From: Hal Ruhl <hjr.domain.name.hidden>
Date: Fri, 13 Apr 2001 17:45:12 -0700

Dear Hal

At 4/13/01, you wrote:

>An FAS with a given complexity CAN and DOES produce theorems with
>greater complexity. You should not misread Chaitin to think that he
>says otherwise. There is NO LIMIT on the complexity of a theorem which
>can be produced using an FAS, any more than there is a limit to the
>complexity of a string that can be produced with a finite alphabet.

Here is a direct quote from page 24 of Chaitin's "The Unknowable":

"The general flavor of my work is like this. You compare the complexity of
the axioms to the complexity of the result you're trying to derive, and if
the result is more complex than the axioms, then you can not get it from
those axioms."

I have seen the same general statement using slightly different words
elsewhere in his work but can not locate it just yet.

Hal
Received on Fri Apr 13 2001 - 14:52:09 PDT