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 an universal Turing
machine with a constant increase in program length this doesn't matter much).
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 an universal Turing
machine with a constant increase in program length this doesn't matter much).
See An Introduction to Kolmogorov Complexity and
Its Applications
for more information.
