Math ∩ Programming

Kolmogorov Complexity

And yet, by the immutable laws of probability, each string has an equal chance (2^{-50}) in being chosen at random from all sequences of 50 binary digits. So in a sense, the huge body of mathematics underlying probability has already failed us at this basic juncture because we cannot speak of how random one particular outcome of an experiment is. We need a new notion that overcomes this difficulty.

Definition: The Kolmogorov complexity of a string w, denoted K(w) is the length of the shortest program which outputs w given no input.


Fast Lane Literacy by sedso