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

---

В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта.

Колмогоровская сложность также известна как описательная сложность, сложность Колмогорова — Хайтина, стохастическая сложность, алгоритмическая энтропия или алгоритмическая сложность.

К примеру, рассмотрим две строки длиной 64 символа, содержащие только символы в нижнем регистре и цифры:

Первая строка имеет простое описание на естественном языке, а именно ab 32 раза, состоящее из 10 символов. Вторая строка не имеет очевидного простого описания с использованием того же набора символов, кроме собственно самой этой строки, длина которой составляет 64 символа.

Более формально, сложность строки — это длина описания этой строки на некотором универсальном языке описания. Способность сложности к изменению относительно выбора языка описания обсуждается ниже. Колмогоровская сложность любой строки не может быть более, чем на несколько байт больше, чем длина самой этой строки, так как программа может выглядеть как одна команда "напечатать строку", где строка указана в явном виде. Строки, чья колмогоровская сложность слабо зависит от размера самой строки, не считаются сложными.

Чтобы определить колмогоровскую сложность, мы должны сначала задать язык описания строк. Такой язык описания может быть основан на любом языке программирования, таком как Lisp, Pascal или Java. Если ${\displaystyle P}$ — программа, выходом которой является строка ${\displaystyle x}$, то ${\displaystyle P}$ — описание ${\displaystyle x}$. Длиной описания является длина ${\displaystyle P}$ как строки. В ходе определения длины ${\displaystyle P}$ должны быть вычислены дли́ны подпрограмм, использующихся в ${\displaystyle P}$. Длина любой целой константы ${\displaystyle n}$, которая появляется в ${\displaystyle P}$ — это количество битов, требующихся для представления ${\displaystyle n}$, равное (грубо) ${\displaystyle \log _{2}n}$.

---