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
