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