# Kolmogorov complexity

Consider flipping a coin 50 times to obtain the binary string 000101000001010100010000010101000100000001010000010. Can we call this random? The string has rather an abundance of 0s, and on closer inspection every other bit is 0. We wouldnâ€™t expect even a biased coin to come up with such a pattern. Still, this string has probability ${2}^{-50}$, just like any other binary string of the same length, so how can we call it any less random?

Kolmogorov Complexity^{} provides an answer to these questions in the form
of a measure of information content in individual objects. Objects with low
information content may be considered non-random.
The topic was founded in the 1960s independently by three people:
Ray Solomonoff, Andrei Kolmogorov, and Gregory Chaitin.

See Kolmogorov complexity function and invariance theorem for more details.

Title | Kolmogorov complexity |
---|---|

Canonical name | KolmogorovComplexity |

Date of creation | 2013-03-22 13:43:41 |

Last modified on | 2013-03-22 13:43:41 |

Owner | tromp (1913) |

Last modified by | tromp (1913) |

Numerical id | 9 |

Author | tromp (1913) |

Entry type | Topic |

Classification | msc 68Q30 |

Synonym | algorithmic information theory |

Synonym | algorithmic entropy |