Kolmogorov Complexity

 

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).

Source

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.

Source


___________________

Refer to this page:

___________________

Related Terms:

 

Note: If a company/institute/site doesn't want to present its own information in nanodic.com, it can sent one e-mail to info@nanodic.com.