has coined the term elegant
to describe a program
which is the shortest possible one that will produce a given string
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
(2) length(P') + C >= length(P)
is a small constant.)
If we go along with Chaitin's definition of a random string R as one for which
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'
play the same roles in (1) and (2) that P
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.