# Difference between revisions of "Kolmogorov complexity"

(Minor cleanup) |
|||

Line 1: | Line 1: | ||

− | Intuitively | + | Intuitively, the '''Kolmogorov complexity''' of an integer <math>n</math> is the least number of bits one needs to describe <math>n</math> in some suitable language. For instance, one could use the language of Turing machines: an integer <math>n</math> has Kolmogorov complexity at most <math>k</math> if there exists a Turing machine with length at most <math>k</math> which, when run, produces <math>n</math> as the 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 <math>k</math>-bit integer has Kolmogorov complexity at most <math>k+O(1)</math> (the <math>O(1)</math> overhead being for the trivial program that outputs the remaining <math>k</math> 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 <math>k</math> (we'll refer to this as the ''counting argument''). As a consequence, most <math>k</math>-bit integers have Kolmogorov complexity close to <math>k</math>. |

− | 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). | + | On the other hand, a deterministic algorithm which takes <math>k</math> as input and runs in time polynomial in <math>k</math> 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 <math>O(1)</math> 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 <math>k</math> is). |

* [[wikipedia:Kolmogorov_complexity|The Wikipedia entry for Kolmogorov complexity]] | * [[wikipedia:Kolmogorov_complexity|The Wikipedia entry for Kolmogorov complexity]] |

## Latest revision as of 06:23, 28 August 2009

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

Thus, for instance, any [math]k[/math]-bit integer has Kolmogorov complexity at most [math]k+O(1)[/math] (the [math]O(1)[/math] overhead being for the trivial program that outputs the remaining [math]k[/math] 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 [math]k[/math] (we'll refer to this as the *counting argument*). As a consequence, most [math]k[/math]-bit integers have Kolmogorov complexity close to [math]k[/math].

On the other hand, a deterministic algorithm which takes [math]k[/math] as input and runs in time polynomial in [math]k[/math] 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 [math]O(1)[/math] 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 [math]k[/math] is).