How short can you make a computer program that generates a specific string?
In short: Kolmogorov complexity measures the computational resources required to define an object. It defines the complexity of a string as the length of the shortest computer program capable of producing it. If a string has a simple, repeating pattern, its complexity is low; if it is random, its complexity is high.
First published by Andrey Kolmogorov in 1963, this concept is a cornerstone of algorithmic information theory. It provides a formal way to quantify the information content of an object. For instance, a string consisting of the same two characters repeated sixteen times is far less complex than a random string of the same length because the former can be generated by a very short instruction set, while the latter essentially requires the entire string to be written out in the code.
The theory relies on the concept of a universal description language. While the exact length of the shortest program depends on the language chosen, the invariance theorem ensures that the difference between any two languages is bounded by a constant. This means the fundamental measure of complexity remains consistent regardless of whether you use a language like Java, Lisp, or a specific encoding for Turing machines.
Researchers distinguish between plain and prefix-free complexity. Plain complexity is intuitive but suffers from a technical defect: it lacks a clear way to signal where a program ends, often requiring extra information to be 'sneaked' into the code. Prefix-free complexity solves this by using self-delimiting programs, where no valid program is a prefix of another. This refinement is essential for rigorous mathematical analysis and proving impossibility results, such as those related to Gödel's incompleteness theorem or Turing's halting problem.
Ultimately, Kolmogorov complexity reveals the limits of computation. It has been proven that no single program can calculate the exact complexity for an infinite number of strings. Because a program cannot compute a lower bound for a string's complexity that is significantly larger than its own length, we are left with a profound realization: some truths about information are inherently beyond the reach of any universal algorithm.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Kolmogorov complexity
To cite this card, link to https://intellectplus.co.uk/app/science-kolmogorov-complexity.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Algebra · More in Science · Latest · A–Z · All topics