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

Колмогоровскую сложность (англ. Kolmogorov complexity) можно рассматривать как способ измерения количества информации в строке.

Но как понять, какое количество информации содержит в себе строка? Один из классических способов — это подсчет количества битов (число, пропорциональное длине строки). Рассмотрим следующий пример:

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов.

Можем дать следующее определение. Количество информации, которое несет строка — это размер файла, полученного сжатием строки каким-то конкретным компрессором (например, LZW). Но мы по-прежнему можем придумать строку, которая явно несет в себе мало информации, но которую компрессор тем не менее не сожмет.

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

Определения

Декомпрессор

Определение:

Назовём декомпрессором (англ. decompressor) $D : \{0, 1\}^* \to \left[\begin{array}{l}\{0, 1\}^* \\ \bot\end{array}\right.$ алгоритм, восстанавливающий разжатый текст из сжатого.

Примечание: для простоты мы будем рассматривать бинарный алфавит, но все утверждения мы можем обобщить на строки произвольного алфавита.

Относительно каждого декомпрессора мы можем определить понятие сложности строки:

Определение:

Пусть $x \in \{0, 1\}^*$, тогда назовем колмогоровской сложностью строки $K_D(x) = \min \limits_{y}\ \{|y|\ |\ D(y) = x \}$, размер минимальной строки $y$, такой, что $D(y) = x$. Если такого $y$ не существует, тогда $K_D(x) = +\infty$.

Примеры

• $D(x) = x$, тогда $K_D(x) = |x|$
• $D(x) = xx$, тогда $K_D(0000) = 2, K_D(01) = +\infty$

Определение:

Будем говорить, что декомпрессор $D_1$ не хуже, чем декомпрессор $D_2$, если $\exists c \gt 0:\forall x \in \{0, 1\}^*\ K_{D_1}(x) \leqslant K_{D_2}(x) + c$.

Теорема:

Существует оптимальный декомпрессор (англ. optimal decompressor) $U$, который не хуже всех остальных.

Доказательство:

$\triangleright$

Пусть $p$ — некоторая строка, $|p| = n$. Обозначим за $\hat{p}$ строку $p_1 p_1 p_2 p_2 \dots p_n p_n 0 1$ (мы удвоили каждый бит строки $p$ и добавили в конце $01$). Оптимальный декомпрессор будет работать следующим образом: $U(\hat{p}x) = \langle p \rangle(x)$, т.е. он интерпретирует $p$ как программу, а $x$ как входные данные и запускает $p$ на входе $x$. Покажем, что такой декомпрессор будет не хуже любого другого. Пусть $D$ — другой декомпрессор. По определению $D$ — это алгоритм, значит есть программа, которая исполняет $D$. $p$ — номер алгоритма $D,\ p = \#D$. Тогда: $K_U(x) \leqslant K_D(x) + 2|p| + 2$, т.к. $K_D(x)$ достигается на $D(y) = U(\hat{p}y) = x$, т.е. для этого $y$ есть строка $\hat{p}y$, которая даёт тот же самый результат и имеет длину не больше, чем на $2|p| + 2$. Нетрудно заметить, что $2|p| + 2$ зависит только от $D$, но никак не зависит от $x$, т.е. является константой. Следовательно, $U$ — оптимальный декомпрессор.

$\triangleleft$

Определение:

Пусть $D$ — это оптимальный декомпрессор, тогда колмогоровская сложность $KS(x) = K_D(x)$.

Утверждение:

Очевидно, что если $D_1$ и $D_2$ — оптимальные декомпрессоры, то $\exists c_1, c_2: \forall x: \left\{ \begin{array}{l l} K_{D_1}(x) \leqslant K_{D_2}(x) + c_1 \\ K_{D_2}(x) \leqslant K_{D_1}(x) + c_2 \end{array} \right.$

Свойства

Тривиальные свойства

• $KS(x) \leqslant |x| + c$
• $KS(x,y) \leqslant KS(x) + KS(y) + 2\lceil \log_2 KS(x) \rceil + 2$
• Если $A$ — алгоритм, то $KS(A(x)) \leqslant KS(x) + c_A$
  ($A(x)$ запишем как пару — информация об алгоритме $A$ и информация о строке $x$, по предыдущему пункту нам нужно закодировать только сложность первого аргумента, что есть константа)
• Принцип несжимаемости: $\exists x \in \{0,1\}^n : KS(x) \geqslant n$
  (Какой бы у нас ни был компрессор, он не может все строки фиксированной длины делать меньше. Строк длины меньшей, чем $n$ — $(2^n-1)$, мы не сможем декомпрессировать)
• $KS$ — невычислимая функция.

Докажем последнее свойство:

Невычислимость

Утверждение (Лемма):

Если $f:\{0,1\}^* \rightarrow N$ — вычислимая функция, такая, что $\forall x : f(x) \leqslant KS(x)$, тогда $f = O(1)$.

$\triangleright$

Пусть $A(n) = \arg\min \limits_{x} f(x) \geqslant n$, где $n \in N$, тогда $A(n)$ — вычислимая (т.к $f(x)$ — вычислима и ограничена), всюду определенная функция. По свойству невозрастания $KS(x)$ при алгоритмических преобразованиях, $KS(A(n)) \leqslant KS(n) + c_1 \leqslant \log_2 n + c_2$. Вспомним, что $f(x) \leqslant KS(x)$, следовательно $KS(A(n)) \geqslant f(A(n)) \geqslant n$. Отсюда: $\forall n : \log_2 n + c_2 \geqslant n$, но ясно, что при больших $n$ это неравенство не выполняется. Противоречие.

$\triangleleft$

---

Примечание: если функция $f(x)$ определена только на $M \subset \{0,1\}^*$, то лемма остается в силе с единственным отличием, что $x$ пробегает все значения из $M$ в порядке перечисления.

Утверждение (следствие из леммы):

$KS(x)$ невычислима.

Пусть $KS(x)$ вычислима. Возьмем вместо $f(x)\ KS(x)$. Очевидно, что $\forall x : f(x) \leqslant KS(x)$, но из принципа несжимаемости ясно, что $KS(x)$ неограничена. Противоречие. Следовательно, $KS(x)$ невычислима.

$\forall x \gt x_0: K(x) \gt f(x)$, если только $f \leqslant const$ или $f$ — невычислима.

Альтернативное доказательство с использованием теоремы о рекурсии

Функция $K(x)$ — это минимальная длина программы $p : p(\varepsilon) = x$. Допустим, что $K$ вычислима, тогда напишем такую программу:

 [math]p(\varepsilon){:}[/math]
   foreach [math]x\in ~ \Sigma^* [/math] //перебираем слова по возрастанию длины
     if [math] K(x) \gt  |p|[/math] //теорема о рекурсии используется здесь
       return[math](x)[/math]     

Длина этой программы меньше длины минимальной программы, которая возвращает $x$ на пустом входе. Поэтому возникает противоречие. Следовательно $K$ невычислима.

Применение

Альтернативное доказательство теоремы Гёделя о неполноте

Г. Хайтин заметил следующее:

Утверждение:

В данной фиксированной системе вывода существует недоказуемое утверждение вида $KS(x) \geqslant n$

$\triangleright$

Выпишем множество пар $\{(x,n) |\ $ утверждение $KS(x) \geqslant n$ доказуемо $\}$. Возможны два варианта: Все $n \leqslant n_0$. Это означает, что для всех строк будет доказуемо только $KS(x) \geqslant n_0$. Но т.к. мы знаем, что $KS(x)$ неограничена, то существуют истинные, но недоказуемые утверждения. В этом множестве встречаются сколь угодно большие $n$, т.е. есть бесконечная последовательность $(x_i, n_i)$, в которой $n_{i+1} \gt n_i$. Заметим, что эта последовательность задает график какой-то функции. А если график функции перечислим, то сама функция является вычислимой. Также заметим, что всегда выполняется условие $KS(x_i) \geqslant n_i$, т.е. эта вычислимая функция является нижней оценкой на $KS(x)$, а мы знаем, что такие функции обязаны быть ограниченными. Противоречие.

$\triangleleft$

Заметим, что во всех множествах пар все $n$ ограничены какой-то константой, следовательно существует огромное число истинных, но недоказуемых утверждений вида $KS(x) \geqslant n$

Доказательство бесконечности простых чисел

Утверждение:

Простых чисел бесконечно много.

$\triangleright$

Предположим, что простых чисел конечное число. Тогда любое число $n = {p_1}^{\alpha_1}{p_2}^{\alpha_2}\dots{p_k}^{\alpha_k}$, где $k$ — это некоторая константа. Возьмём $n$ наибольшей колмогоровской сложности. Тогда $KS(n) \geqslant \log_2 n$, но также $KS(n) \leqslant 2 k \log_2 \log_2 n + c$, т.к. $\alpha_i \leqslant \log_2 n$. Но это неравенство не будет выполняться на достаточно больших $n$, противоречие.

$\triangleleft$

См. также

• Busy beaver

Источники информации

• Лекция Дмитрия Ицыксона в CS центре
• Wikipedia — Колмогоровская сложность