- 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 15:46:47 -0700

Hal writes:

*> Here is a direct quote from page 24 of Chaitin's "The Unknowable":
*

*> "The general flavor of my work is like this. You compare the complexity of
*

*> the axioms to the complexity of the result you're trying to derive, and if
*

*> the result is more complex than the axioms, then you can not get it from
*

*> those axioms."
*

I think Chaitin is paraphrasing his results here. As he says, this just

gives the flavor of it.

*> Here is the second quote. It is from Chaitin's "The Limits of Mathematics"
*

*> page 90.
*

*>
*

*> "The first of these theorems states that an N-bit formal axiomatic system
*

*> cannot enable one to exhibit any specific object with a program-size
*

*> complexity greater than N + c."
*

When you look at this in detail, he means that the FAS cannot exhibit a

specific object that it can PROVE to have large complexity. This article

is online at http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html and

the statement above is found in the third paragraph. But when we read

farther down we find, a more formal statement:

"Now consider a formal axiomatic system A of complexity N, i.e.,

with a set of theorems T_A that considered as an r.e. set as above has

self-delimiting program-size complexity H(TA) = N. We show that A cannot

enable us to exhibit a specific S-expression s with self-delimiting

complexity H(s) greater than N+c. Here c = 4872. See godel2.r."

And if we follow the link to godel2.r, which is the lisp program that

establishes the result, it says,

"Show that a formal system of complexity N can't prove that a specific

object has complexity > N + 4872."

That's what is actually proven. The FAS cannot PROVE that a specific

object has high complexity. The earlier statements were attempts to

paraphrase this result and were perhaps somewhat misleading. When he

said the FAS would not enable us to exhibit a specific s-expression with

high complexity, he meant that the FAS was not able to supply us with

a proof of this fact.

The whole thrust of Chaitin's result, when you follow it closely and

study the LISP code as I did for several hours last night, is that the

FAS is limited in the complexity it can prove, not in the complexity of

what it can produce.

Hal

Received on Fri Apr 13 2001 - 15:54:22 PDT

Date: Fri, 13 Apr 2001 15:46:47 -0700

Hal writes:

I think Chaitin is paraphrasing his results here. As he says, this just

gives the flavor of it.

When you look at this in detail, he means that the FAS cannot exhibit a

specific object that it can PROVE to have large complexity. This article

is online at http://www.cs.auckland.ac.nz/CDMTCS/chaitin/rov.html and

the statement above is found in the third paragraph. But when we read

farther down we find, a more formal statement:

"Now consider a formal axiomatic system A of complexity N, i.e.,

with a set of theorems T_A that considered as an r.e. set as above has

self-delimiting program-size complexity H(TA) = N. We show that A cannot

enable us to exhibit a specific S-expression s with self-delimiting

complexity H(s) greater than N+c. Here c = 4872. See godel2.r."

And if we follow the link to godel2.r, which is the lisp program that

establishes the result, it says,

"Show that a formal system of complexity N can't prove that a specific

object has complexity > N + 4872."

That's what is actually proven. The FAS cannot PROVE that a specific

object has high complexity. The earlier statements were attempts to

paraphrase this result and were perhaps somewhat misleading. When he

said the FAS would not enable us to exhibit a specific s-expression with

high complexity, he meant that the FAS was not able to supply us with

a proof of this fact.

The whole thrust of Chaitin's result, when you follow it closely and

study the LISP code as I did for several hours last night, is that the

FAS is limited in the complexity it can prove, not in the complexity of

what it can produce.

Hal

Received on Fri Apr 13 2001 - 15:54:22 PDT

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