Re: Computing Randomness

From: Hal Ruhl <hjr.domain.name.hidden>
Date: Thu, 12 Apr 2001 19:50:36 -0700

Dear Juergen:

You demonstrate my point.

At 4/12/01, you wrote:

>Hal, here is an infinite chain of provable unique theorems:
>1+1=2, 2+1=3, 3+1=4, 4+1=5, ...

First these are not theorems they are proof chains ending in theorems.
For example:

"4 + 1 =" is a proof chain and the theorem proved is: "5" is a number.

The base or data for the proof chain is "4 is a number" which has just been
proven by the previous step in the cascade.

Now notice that the data or base theorem [a well formed base 10 string] for
each proof chain in the cascade counts up in value. Therefore it must
inexorably increase in length. Since most strings of length L are not
compressible and have a complexity on the order of L + H(L) eventually the
cascade will encounter a base theorem string that makes the proof chain
itself too complex to fit into a number theory of a given finite
complexity. The cascade must then stop or number theory must become more
complex. Cascades do not have an internal stop rule. Here we have a
contradiction. To cure it the applicable FAS must become more complex.

Below I say the same thing in a more formal way.

xxxxxxxxxxxxx

Let us first arbitrarily call this theorem cascade #27 in number theory. So
an individual theorem in cascade #27 is identified as T27(i).

Let us look at say T27(4) in this cascade. Its decompressed proof program
looks like:

(1) P27(4) = {RULES27(T27(3)) + Self-delimiter27(4)} computes T27(4) [which
is the base ten string "5"]

Where:
RULES27 = Add 1 to the base ten string that is the current data
T27(3) = is the data for the proof program of T27(4) [which is just the
base ten string "4"]

The most compressed version of its proof program would be:

(2) P27'(4) = {RULES27(P27'(3)) + Self-delimiter27'(4)} computes T27(4)
[which is the base ten string "5"]

Where:
P27'(3) = the max compression of T27(3)

Now let cascade #27 continue. Eventually the complexity of the data: P27'(i
- 1) plus the complexity of RULES27 plus the complexity of
Self-delimiter27'(i) when combined into P27'(i) makes P27'(i) exceed the
complexity of number theory if number theory has a finite complexity.

Then what happens?

This cascade has no internal stop but it must stop [there is no rule of the
cascade saying it can hop over unacceptably complex n(i) and even so the
hop computation would become more and more complex as the base string gets
more complex] or the FAS must get more complex.

If the FAS gets more complex where does the added information come from?

Does that not look a lot like:

"If a FAS is consistent and finite and doing arithmetic it is incomplete"?

So Godel is already a corollary of Turing and perhaps of Chaitin as well.

Going a step further when looking at universes in general I currently see
no need for the new information to preserve a FAS. It just gets a running
cascade to the next iteration at which point more new information may be
needed.

So perhaps an essential dash of random oracle finishes the entree we call
our universe.

Hal
Received on Thu Apr 12 2001 - 17:02:05 PDT