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