Материал из Викиконспекты
Колмогоровскую сложность можно рассматривать как способ измерения количества информации в строке.
Но как понять, какое количество информации содержит в себе строка? Один из классических способов — это подсчет количества битов (число, пропорциональное длине строки). Рассмотрим следующий пример:
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов.
Можем дать следующее определение. Количество информации, которое несет строка — это размер архива, полученного сжатием строки каким-то конкретным архиватором (например, LZW). Это более нетривиальная задача, но мы можем придумать строку, которая явно несет в себе мало информации, но которую архиватор тем не менее не сожмет.
Еще более сильное определение. Количество информации, которое несет строка — это размер архива, сжатого максимальным образом, самым лучшим архиватором. Но тогда встает вопрос, почему такой архиватор существует. На самом деле он есть, и в некотором смысле колмогоровская сложность строки — это размер наименьшей программы, которая печатает эту строку.
Декомпрессор
| Определение: |
| Назовём декомпрессором [math]D : \{0, 1\}^* \to
\left[\begin{array}{l}\{0, 1\}^* \\
\bot\end{array}\right.[/math] алгоритм, восстанавливающий разжатый текст из сжатого. |
Примечание: для простоты мы будем рассматривать бинарный алфавит, но все утверждения мы можем обобщить на строки произвольного алфавита.
Относительно каждого декомпрессора мы можем определить понятие сложности строки:
| Определение: |
Пусть [math]x \in \{0, 1\}^* [/math], тогда назовем колмогоровской сложностью строки [math]K_D(x) = \min \limits_{y}\ \{|y|\ |\ D(y) = x \}[/math], размер минимальной строки [math]y[/math], такой, что [math]D(y) = x[/math].
Если такого [math]y[/math] не существует, тогда [math]K_D(x) = +\infty[/math]. |
Примеры
- [math]D(x) = x[/math], тогда [math]K_D(x) = |x|[/math]
- [math]D(x) = xx[/math], тогда [math]K_D(0000) = 2, K_D(01) = +\infty [/math]
| Определение: |
| Будем говорить, что декомпрессор [math]D_1[/math] лучше, чем декомпрессор [math]D_2[/math], если [math]\exists c:\forall x \in \{0, 1\}^*\ K_{D_1}(x) \leqslant K_{D_2}(x) + c[/math]. |
| Теорема: |
Существует оптимальный декомпрессор [math]U[/math], который лучше всех остальных. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть [math]p[/math] — некоторая строка, [math]|p| = n[/math]. Обозначим за [math]\hat{p}[/math] строку [math]p_1 p_1 p_2 p_2 ... p_n p_n 0 1[/math] (мы удвоили каждый бит строки [math]p[/math] и добавили в конце [math]01[/math]).
Оптимальный декомпрессор будет работать следующим образом: [math]U(\hat{p}x) = \langle p \rangle(x)[/math], т.е. он интерпретирует [math]p[/math] как программу, а [math]x[/math] как входные данные и запускает [math]p[/math] на входе [math]x[/math].
Покажем, что такой декомпрессор будет лучше любого другого.
Пусть [math]D[/math] — другой декомпрессор. По определению [math]D[/math] — это алгоритм, значит есть программа, которая исполняет [math]D[/math].
[math]p[/math] — номер алгоритма [math]D,\ p = \#D[/math]. Тогда:
[math]K_U(x) \leqslant K_D(x) + 2|p| + 2[/math], т.к. [math]K_D(x)[/math] достигается на [math]D(y) = U(\hat{p}y) = x[/math], т.е. для этого [math]y[/math] есть строка [math]\hat{p}y[/math], которая даёт тот же самый результат и имеет длину не больше, чем на [math]2|p| + 2[/math].
Нетрудно заметить, что [math]2|p| + 2[/math] зависит только от [math]D[/math], но никак не зависит от [math]x[/math], т.е. является константой.
Следовательно, [math]U[/math] — оптимальный декомпрессор. |
| [math]\triangleleft[/math] |
| Определение: |
| Пусть [math]D[/math] — это оптимальный декомпрессор, тогда колмогоровская сложность [math]KS(x) = K_D(x)[/math]. |
| Утверждение: |
Очевидно, что если [math]D_1[/math] и [math]D_2[/math] — оптимальные декомпрессоры, то [math]\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.
[/math] |
Свойства
Тривиальные свойства
- [math]KS(x) \leqslant |x| + c[/math]
- [math]KS(x,y) \leqslant KS(x) + KS(y) + 2\lceil log_2 KS(x) \rceil + 2[/math]
- Если [math]A[/math] — алгоритм, то [math]KS(A(x)) \leqslant KS(x) + c_A[/math]
([math]A(x)[/math] запишем как пару — информация об алгоритме [math]A[/math] и информация о строке [math]x[/math], по предыдущему пункту нам нужно закодировать только сложность первого аргумента, что есть константа)
- Принцип несжимаемости: [math]\exists x \in \{0,1\}^n : KS(x) \geqslant n[/math]
(Какой бы у нас ни был архиватор, он не может все строки фиксированной длины делать меньше. Строк длины меньшей, чем [math]n[/math] — [math](2^n-1)[/math], мы не сможем деархивировать)
- [math]KS[/math] — невычислимая функция.
Докажем последнее свойство:
Невычислимость
| Лемма: |
Если [math]f:\{0,1\}^* \rightarrow N[/math] — вычислимая функция, такая, что [math]\forall x : f(x) \leqslant KS(x)[/math], тогда [math]f = O(1)[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть [math]A(n) = \arg\min \limits_{x} f(x) \geqslant n[/math], где [math]n \in N[/math], тогда [math]A(n)[/math] — вычислимая (т.к [math]f(x)[/math] — вычислима и ограничена), всюду определенная функция.
По свойству невозрастания [math]KS(x)[/math] при алгоритмических преобразованиях, [math]KS(A(n)) \leqslant KS(n) + c_1 \leqslant log_2 n + c_2[/math].
Вспомним, что [math]f(x) \leqslant KS(x)[/math], следовательно [math]KS(A(n)) \geqslant f(A(n)) \geqslant n[/math].
Отсюда: [math]\forall n : log_2 n + c_2 \geqslant n[/math], но ясно, что при больших [math]n[/math] это неравенство не выполняется. Противоречие. |
| [math]\triangleleft[/math] |
Примечание: если функция [math]f(x)[/math] определена только на [math]M \subset \{0,1\}^*[/math], то лемма остается в силе с единственным отличием, что [math]x[/math] пробегает все значения из [math]M[/math] в порядке перечисления.
| Утверждение (следствие из леммы): |
[math]KS(x)[/math] невычислима. |
| [math]\triangleright[/math] |
|
Пусть [math]KS(x)[/math] вычислима. Возьмем вместо [math]f(x)\ KS(x)[/math]. Очевидно, что [math]KS(x) \leqslant KS(x)[/math], но из принципа несжимаемости ясно, что [math]KS(x)[/math] неограничена. Противоречие. Следовательно, [math]KS(x)[/math] невычислима. |
| [math]\triangleleft[/math] |
Применение
Альтернативное доказательство теоремы Гёделя о неполноте
Г. Хайтин заметил следующее:
| Утверждение: |
В данной фиксированной системе вывода существует недоказуемое утверждение вида [math]KS(x) \geqslant n[/math] |
| [math]\triangleright[/math] |
|
Выпишем множество пар [math]\{(x,n) |\ [/math] утверждение [math]KS(x) \geqslant n[/math] доказуемо [math]\}[/math]. Возможны два варианта:
- Все [math]n \leqslant n_0[/math]. Это означает, что для всех строк будет доказуемо только [math]KS(x) \geqslant n_0[/math]. Но т.к. мы знаем, что [math]KS(x)[/math] неограничена, то существуют истинные, но недоказуемые утверждения.
- В этом множестве встречаются сколь угодно большие [math]n[/math], т.е. есть бесконечная последовательность [math](x_i, n_i)[/math], в которой [math]n_{i+1} \gt n_i[/math]. Заметим, что эта последовательность задает график какой-то функции. А если график функции перечислим, то сама функция является вычислимой. Также заметим, что всегда выполняется условие [math]KS(x_i) \geqslant n_i[/math], т.е. эта вычислимая функция является нижней оценкой на [math]KS(x)[/math], а мы знаем, что такие функции обязаны быть ограниченными. Противоречие.
|
| [math]\triangleleft[/math] |
Заметим, что во всех множествах пар все [math]n[/math] ограничены какой-то константой, следовательно существует огромное число истинных, но недоказуемых утверждений вида [math]KS(x) \geqslant n[/math]
Источники
