Re: Computing Randomness

From: Hal Ruhl <hjr.domain.name.hidden>
Date: Fri, 13 Apr 2001 14:20:06 -0700

Dear Hal

Since I was previously convinced by another that side bar discussions
should be avoided I will respond to this on the list.

At 4/12/01, you wrote:
>Hal writes:
> > You are writing programs and they have a complexity. Chaitin limits this
> > complexity to no more than the complexity of the FAS plus a
> constant. Thus
> > there can not be an infinite number of such constructions.
>
>This is not quite right.

Well lets see if I can better explain my view and eliminate the unspoken parts.

>Chatin limits how much complexity these programs
>can be *proven* to have using the FAS. The FAS is unable to show that
>an object has more complexity than what is in the FAS itself (plus a
>constant).

Yes but then the object is not fully describable by the FAS since one of
its properties remains a mystery. If a FAS is to "prove" a specific object
is a "well formed formula" then the FAS should be able to fully describe it.

Here is a more careful description of my view.

See pages 24 and 25 of Chaitin's "The Unknowable".

This is my interpretation:

Paraphrasing the middle of page 24:

Chaitin claims that his results demonstrate an incompleteness. That there
is an ocean of true but unprovable assertions.

How does he get this?

Definition from page 24:

"Let's call a program elegant if no smaller program written in the same
programming language has the same output."

He claims that his approach demonstrates that [quote from page 25]

"If a formal axiomatic system A has LISP program size complexity N, then
you can't use A to prove that any LISP expression more than N + 356
characters long is elegant. So A can only prove that finitely many
expressions are elegant!"

How does this get you an ocean of true but unprovable assertions?

Well any assertion [object] with a LISP elegant program size greater than N
+ 356 can not be fully described by A since you can not identify its
elegant program with A.

Now Chaitin says on page 24 that he can not exhibit specific true,
unprovable assertions.

But can we indeed point to some?

I consider evolving universes - at first examination - to be theorem
cascades in finite FAS.

So let us look at Juergen's example:

1+1=2, 2+1=3, 3+1=4, 4+1=5, ...............2873465+1=2873466, ............

As the iterations proceed numerous added steps to the computing program
unavoidably contain longer strings [most strings are incompressible] than
those in any previous iteration and thus these steps have more program
length complexity. This complexity will eventually exceed any finite
limit. We will have arrived at strings whose properties are not fully
describable by any finite FAS.

What happens to the cascade when it reaches unprovable assertions [strings]?
Cascades do not have internal stop rules.

IMO the issue is cured by the FAS itself becoming more complex. A bit of
incompleteness is resolved.

I apply this to examine evolving universes.

It might be wrong but that is the current state of the idea.

Hal
Received on Fri Apr 13 2001 - 11:34:59 PDT