Kolmogorov Complexity

/ˌkɒl.mə.ˈɡɒ.rɒf kəmˈplɛk.sɪ.ti/ · Noun · Development · Origin: 1965

Definitions

  1. The length of the shortest program (in a fixed universal programming language) that produces a given string as output. A measure of the inherent information content of data — incompressible strings have high Kolmogorov complexity. Crucially, it is uncomputable.

    In plain English: How long is the shortest program that can generate a piece of data? Simple patterns are easy to describe; truly random data can't be compressed at all. And here's the kicker: you can never be sure you've found the shortest program.

    Example: "The string of a million 1s has low Kolmogorov complexity — just print("1" * 1000000). A truly random string of the same length? Its shortest description is itself."

Related Terms