Chaitin Elegance

Mathematician GregoryChaitin defines elegance in computer programming in this way: A computer program written in a given language is elegant if no smaller program written in the same language has the same output. He goes on to prove that it is impossible to prove that a given program above a certain very low level of complexity is elegant.

His precise theorem is this: Define "LISP program-size complexity" to be the size of a LISP subroutine that examines a proof, determines whether it is correct, and returns either the theorem established by the proof (if the proof is correct) or an error message (if the proof is incorrect). Then, given a formal axiomatic system A, with LISP program-size complexity N, A cannot be used to prove that any LISP expression longer than N + 356 characters is elegant.

The proof of this (rather inelegant) theorem involves constructing a LISP expression B which returns the value of the first LISP expression larger than B that can be proved to be elegant in A. When B is constructed, it turns out to be N+356 characters long. Note that if B ever returns a value, the value will be of an "elegant" expression longer than B; but this is a contradiction. The conclusion is that either A proves false theorems or A cannot prove that any LISP expression longer than N+356 is elegant.

See http://www.cs.umaine.edu/~chaitin/unknowable/index.html for more on this, and the relations between this and Goedel's and Turing's incompleteness theorems.

A couple of impertinent remarks. Firstly, the variety of Lisp Chaitin uses is (deliberately) lobotomized; I wish he'd given it some other name so as not to encourage the widespread but false belief that Lisp is an outdated language with no data types other than linked lists and symbols. Secondly, it's probably almost impossible for a program to be "elegant" in Chaitin's sense and also "elegant" in the everyday sense. Maximally compressed programs are seldom pleasant to read. :-)

• Chaitin's LISP is hardly "lobotomized", he reduces it to bare essentials, that is all -- is that not part of the spirit of LISP after all? And in no way is he suggesting that LISP is an outdated language.

A further irony. In philosophy of science, a construct is "indispensable" if getting rid of it makes your theory uglier.

---

I seriously doubt that Chaitin has ever seen PerlGolf. -- DaveSmith

---

Shouldn't the concept of elegance have something to do with how code looks to humans, and not just how small it is?

Absolutely. I think "elegance" is a horrible name for this property. For one thing, it could be argued that elegance can't be described mathematically (think QualityWithoutaName). Furthermore, using the term "elegance" here really obscures what is being dealt with. Some books use the term "descriptive complexity"; others say "KolmogorovComplexity", after another mathematician who studied the concept; others say "Kolmogorov-Chaitin complexity"; in the spirit of full attribution, there are even those who say "Kolmogorov-Chaitin-Solomonoff complexity". Talk about inelegance... =) -- JosephDale

See LaynesLaw