Колмогоровская сложность

Колмогоровской сложностью или сложностью описания слова w (то есть конечной последовательности из нулей и единиц) относительно способа описания D (частичной вычислимой функции из {0,1}* в {0,1}) называется минимальная длина такого слова x, что значение функции D на аргументе x равно w: D(x) = w.

Способ описания D называется оптимальным, если для любого другого способа описания D' существует такое число C, что сложность всякого слова w относительно D не больше его сложности относительно D' плюс C. Наконец, колмогоровская сложность слова w обозначается как KS(w) и определяется как сложность относительно некоторого оптимального способа описания. Можно показать, что от выбора такого оптимального способа описания колмогоровская сложность «почти» не зависит, а именно, меняется не более чем на аддитивную константу.

Неформально говоря, колмогоровская сложность последовательности из нулей и единиц — это длина самой короткой программы, которая может породить эту последовательность.

Несложно видеть, что колмогоровская сложность всякого слова w не превосходит длины слова w (с точностью до аддитивной константы), то есть существует такая константа C, что для любого слова w имеет место неравенство KS(w) < |w| + C.

Имеет место следующая важная теорема: функция KS(w) не является вычислимой.