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)
(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)
(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.

Log in or register to write something here or to contact authors.