Kolmogorovkomplexitást

Kolmogorovkomplexitás, also known as algorithmic complexity or descriptive complexity, is a concept in theoretical computer science and information theory that measures the complexity of an object by the length of the shortest computer program that can produce it. Introduced independently by Andrey Kolmogorov, Ray Solomonoff, and Gregory Chaitin, it provides a formal way to define randomness and information content.

The Kolmogorov complexity of a string is defined as the length of the shortest binary program that, when run on a universal Turing machine, outputs that string and then halts. This length is measured in bits. For example, a string of a million 'a' characters has low Kolmogorov complexity because a short program can generate it (e.g., "print 'a' one million times"). Conversely, a seemingly random string of the same length would have high Kolmogorov complexity, as the shortest program to generate it would essentially be the string itself, requiring many bits to describe.

A key aspect of Kolmogorov complexity is its incompressibility. Objects with high Kolmogorov complexity are considered algorithmically random, as they cannot be significantly compressed by any algorithmic means. While the theoretical definition relies on a universal Turing machine, the exact value of Kolmogorov complexity is generally uncomputable. However, it serves as a fundamental theoretical tool for understanding information, randomness, and the limits of computation. It has applications in areas like pattern recognition, data compression, and statistical inference.