- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: <hal.domain.name.hidden>

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

Agreed.

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

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

Hal writes:

Agreed.

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.

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

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.

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
*