Re: Computing Randomness

From: Hal Ruhl <hjr.domain.name.hidden>
Date: Wed, 11 Apr 2001 20:21:05 -0700

Dear Juergen:

At 4/11/01, you wrote:
>Hal, Chaitin just says "you cannot prove 20 pound theorems with 10 pound
>axioms".

Please refer to Chaitin's "The Unknowable" generally and page 25, Chapter
V, and note 10 at the bottom of page 97 in particular.

>But the infinite cascade of all provable theorems of number
>theory collectively does not convey more information than the axioms.

Do you consider the following as being a reasonable AIT expression of a
theorem cascade "j"?

1) Pj(i) = {Rules(Pj(i -1)) + Self-delimiter(i)} is the shortest AIT
program that computes Tj(i)

where:

Tj(i) = the "i"th theorem in the cascade
Self-delimiter(i) = the required AIT self contained length of Pj(i)
Pj(i -1) = the compressed form of Tj(i - 1)
Rules(Pj(i -1)) = the rules of the FAS acting on the previous theorem as data

If so and the cascade is the only way to arrive at any Tj(i) [which I think
is inherent in the idea of theorem cascade] then each theorem Tj(i) in the
cascade is more complex than its preimage Tj(i - 1) since Pj(i) contains
Pj(i - 1) and thus Tj(i - 1) as data plus its own Self-delimiter's bit
string making it longer than Pj(i -1). Actually the increase in complexity
with each step just accelerates because the Self-delimiter has to grow in
length. With the right class of isomorphism this can be interpreted as a
universe with an accelerating expansion.

> > But what if you declare theorems which say the same thing to be the
> > _same theorem_, rewritten?
> > Duraid
>
>Since a theorem is a symbol string, different strings cannot be the same
>theorem.

Yes and to quote Chaitin's note on page 97 referenced above "More
precisely, the number of N-bit strings X such that H(X) < [N + H(N) - K]
is less than 2^(N - K + c)".

>Perhaps you mean you can easily derive certain theorems from
>others stating "the same thing, rewritten". But this is vague - you can
>derive all theorems from the axioms stating "the same thing, rewritten".

Then perhaps you will agree that we need not add to the above those strings
shorter than N since they are just "the same thing, rewritten" without a
long boring prefix.

Hal
Received on Wed Apr 11 2001 - 17:34:09 PDT