Re: Computing Randomness

From: <>
Date: Fri, 13 Apr 2001 11:46:48 -0700

Hal writes:
> 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?

No, I don't think you have done so. Keep in mind that Chaitin's
"assertions" in this context means potential theorems of the FAS (Formal
Axiomatic System, right?), that is, well-formed strings which might turn
out to be true or false. "Being fully described" is not a well-formed
string. It is not a potential theorem of the FAS. So pointing at a
number and saying that it is not "fully described" (because the FAS
can't numerically determine its complexity) does not represent a true,
unprovable assertion in the FAS.

> 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.

Sure. Most of the strings almost certainly have greater complexity
than that of the FAS. We may even be able to prove that they do so,
outside the system, by using assumptions which are stronger than the FAS.
But the FAS itself will not be able to prove that the complexity of
any string is greater than itself (plus a constant). This is shown by
a trivial program which reaches a contradiction if it were possible.
Basically you would have a small program which outputs a string of large
complexity, which violates the definition of complexity (the size of
the smallest program which outputs it).

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

It doesn't reach "unprovable assertions [strings]"; the
assertions/theorems are just as provable at this size as they were at
the smaller size. Rather, the FAS can no longer compute how complex
the strings are. That's the only difference.

I wonder if you are confusing the idea that the strings have unprovable
complexity with the idea that the strings themselves, as theorems,
are unprovable. These are two different matters.

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.

What Chaitin says is that the FAS can't PROVE that a string has greater
complexity than what the FAS itself starts with. It is a limitation on
the power of the FAS to PROVE complexity, not on the power of the FAS
to GENERATE complexity.

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

Why is there a need for a "cure"?

Hal (the other Hal)
Received on Fri Apr 13 2001 - 12:12:14 PDT

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