Kolmogorov complexity
Complejidad algorítmica (Kolmogórov-Solomonoff-Chaitin)
- Date
- 1965 · confidence high
- Place
- Moscow, USSR
- Credited to
- Andrey Kolmogorov (1965), Ray Solomonoff (1960) and Gregory Chaitin (1966), independent
- People
- 👤 Andréi Kolmogórov1903–1987👤 Gregory Chaitin1947–👤 Ray Solomonoff1926–2009
- Field
- Knowledge & symbols
⚠️ Disputed: the sources disagree.
What was discovered
The complexity of a string is the length of the shortest program that produces it; it rigorously defines randomness and is uncomputable. It unites information, computation and probability.
A threefold independent discovery in the USSR and the United States.
What it led to
- algorithmic information theory
- inductive inference and the minimum description length principle
- Chaitin's incompleteness theorem
Built on
- Turing machine (universal computation)1936
- Shannon's information theory
Made possible
- Chaitin's constant1975
- compression and compression-based classification