Gregory Chaitin has coined the term

*elegant* to describe a

program which is the shortest possible one that will produce a given

string as output.

In Chaitin's work (he is a founder of the field of Algorithmic Information Theory) the measure of the information content of a string is given by the length of the shortest program that can output that string.

Thus an elegant program for string `S` will have a length that is the same as the algorithmic information quantity (or Kolmogorov complexity) of `S`. We could express this as E(`P`,`S`) ("program `P` is elegant for string `S`.")

Since the complexity of the program "run P, take its output, and then run that" is not that great (in a unix shell it's just a couple of `*backticks*`) we can say that if program `P'` is elegant for the string `P` (since any program is also a string), then `P'` may be at most a small constant shorter than `P`, otherwise `P` is not truly elegant for `S`, since the program that ran `P'`, took its output, and then ran that would be the elegant one.

That is, if E(`P`,`S`) and

(1) E(`P'`,`P`)

then

(2) length(`P'`) + `C` >= length(`P`)

(where

`C` is a small constant.)

If we go along with Chaitin's definition of a random string `R` as one for which

(3) E(`P`,`R`)

and

(4)
length(`P`) >= length(`R`)

for some program,

`P`, then, paradoxically, any program which is (Chaitin) elegant for some complex string is also guaranteed to be virtually (Chaitin)

random under the given definition. To see this, check that

`P'` and

`P` play the same roles in (1) and (2) that

`P` and

`R` have in (3) and (4) (modulo the small constant

`C`).

This has often bothered me, though I have seen plenty of source code which has every appearance of being random, but which I have been assured is truly *elegant*.