The Kolmogorov complexity of a string of bits is the length of the smallest Turing machine program which produces the bit string as output. It is therefore somewhat dependent on one's choice of Turing machine, but since every Turing machine can be emulated by a universal Turing machine with a constant increase in program length this doesn't matter much.

-Back to the Transhumanist Terminology metanode

Kolmogorov complexity is better described as the size of the algorithm needed to compute a given number. For the sake of comparison this is minimized -- the smallest possible algorithm is chosen for each computation to be measured. It's interesting because it describes the complexity of a number in a way that's completely independent from the number itself. Since it doesn't use any external measurements on the number, its much less prone to miscalculation than pattern-based methods of determining complexity. Also, a number doesn't even have to be computed to determine its Kolmogorov complexity, so its useful for comparing the complexities of huge numbers.

An often cited example is the comparison of a million digits of pi to a million statistically random digits. Pi has low Kolmogorov complexity as it can be specified by a short algorithm, whether it's Gauss's summation or one of the newer digit-specifying algorithms. On the other side of the spectrum, the million random digits can't be derived in any other way besides specifying them in their entirety. The algorithm used to compute pi doesn't change in size depending on how many digits are needed, it has a constant Kolmogorov complexity. Since the algorithm used to determine the random digits is in fact the digits themselves, it gets larger with each additional digit -- it has a linearly increasing Kolmogorov complexity. With this comparison we can tell that even though pi looks imposingly random to most methods of calculating complexity, it's much much less complex than a truly random number.

Also, modern measurements of Kolmogorov complexity don't necessarily use Turing machines at all. Since universal Turing machines are the common denominator of computation, they were used by Kolmogorov in his work. However, other ways of encoding algorithms, such as combinatory logic, are perfectly reasonable and have been successfully used for the purpose.

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