A Theory of Program Size Formally Identical to Information Theory
Gregory J. Chaitin · Journal of the ACM · 1975
A new definition of program-size complexity is made.H(A,B/C,D) is defined to be the size in bits of the shortest self-delimiting program for calculating strings A and B if one is given a minimal-size self-delimiting program for calculating strings C and D. This differs from previous definitions: (1) programs are required to be self-delimiting, i.e. no program is a prefix of another, and (2) instead of being given C and D directly, one is given a program for calculating them that is minimal in size.Unlike previous definitions, this one has precisely the formal properties of the entropy concept of information theory.For example, H(A,B) = H(A) + H(B/A) -~ 0(1).Also, if a program of length k is assigned measure 2 -k, then H(A) = -log2 (the probability that the standard universal computer will calculate A) -{-0(1).