# Difference between revisions of "Kolmogorov complexity"

(add a link to Kolmogorov complexity as explained on wikipedia) |
|||

Line 1: | Line 1: | ||

− | Intuitively speaking, the Kolmogorov complexity of an integer n is the least number of bits one needs to describe n in some suitable language. For instance, one could use the language of Turing machines: an integer n has Kolmogorov complexity at most k if there exists a Turing machine with length at most k which, when run, will halt to produce n as output. | + | Intuitively speaking, the '''Kolmogorov complexity''' of an integer n is the least number of bits one needs to describe n in some suitable language. For instance, one could use the language of Turing machines: an integer n has Kolmogorov complexity at most k if there exists a Turing machine with length at most k which, when run, will halt to produce n as output. |

Thus, for instance, any k-bit integer has Kolmogorov complexity at most k+O(1) (the O(1) overhead being for the trivial program that outputs the remaining k bits of the Turing machine). On the other hand, it is obvious that there are at most <math>2^k</math> integers of Kolmogorov complexity at most k (we'll refer to this as the ''counting argument''). As a consequence, most k-bit integers have Kolmogorov complexity close to k. | Thus, for instance, any k-bit integer has Kolmogorov complexity at most k+O(1) (the O(1) overhead being for the trivial program that outputs the remaining k bits of the Turing machine). On the other hand, it is obvious that there are at most <math>2^k</math> integers of Kolmogorov complexity at most k (we'll refer to this as the ''counting argument''). As a consequence, most k-bit integers have Kolmogorov complexity close to k. |

## Revision as of 16:09, 19 August 2009

Intuitively speaking, the **Kolmogorov complexity** of an integer n is the least number of bits one needs to describe n in some suitable language. For instance, one could use the language of Turing machines: an integer n has Kolmogorov complexity at most k if there exists a Turing machine with length at most k which, when run, will halt to produce n as output.

Thus, for instance, any k-bit integer has Kolmogorov complexity at most k+O(1) (the O(1) overhead being for the trivial program that outputs the remaining k bits of the Turing machine). On the other hand, it is obvious that there are at most [math]2^k[/math] integers of Kolmogorov complexity at most k (we'll refer to this as the *counting argument*). As a consequence, most k-bit integers have Kolmogorov complexity close to k.

On the other hand, a deterministic algorithm which takes k as input and runs in time polynomial in k can only produce integers of Kolmogorov complexity [math]O(\log k)[/math], since any number produced can be described by a Turing machine of length [math]O(\log k) + O(1)[/math] (the O(1) is to describe the algorithm, and the [math]O(\log k)[/math] bits are to describe how long the program is to run and what k is).