Re: Computing Randomness

From: Hal Ruhl <>
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

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)


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

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.

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

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