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

##
Advertising

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