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

2016-11-25T21:07:18Z

95.140.92.34: /* Примеры */

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

Но как понять, какое ''количество информации'' содержит в себе строка? Один из классических способов {{---}} это подсчет количества битов (число, пропорциональное длине строки). Рассмотрим следующий пример:
<pre>00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000</pre>
Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов.

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

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

==Определения==
===Декомпрессор===
{{Определение
|definition=
Назовём '''декомпрессором''' (англ. ''decompressor'') <tex>D : \{0, 1\}^* \to
\left[\begin{array}{l}\{0, 1\}^* \\
\bot\end{array}\right.</tex> алгоритм, восстанавливающий разжатый текст из сжатого.
}}
Примечание: для простоты мы будем рассматривать бинарный алфавит, но все утверждения мы можем обобщить на строки произвольного алфавита.

Относительно каждого декомпрессора мы можем определить понятие сложности строки:
{{Определение
|definition=
Пусть <tex>x \in \{0, 1\}^* </tex>, тогда назовем '''колмогоровской сложностью''' строки <tex>K_D(x) = \min \limits_{y}\ \{|y|\ |\ D(y) = x \}</tex>, размер минимальной строки <tex>y</tex>, такой, что <tex>D(y) = x</tex>. Если такого <tex>y</tex> не существует, тогда <tex>K_D(x) = +\infty</tex>.
}}

===Примеры===
* <tex>D(x) = x</tex>, тогда <tex>K_D(x) = |x|</tex>
* <tex>D(x) = xx</tex>, тогда <tex>K_D(0000) = 2, K_D(01) = +\infty </tex>
{{Определение
|definition=
Будем говорить, что декомпрессор <tex>D_1</tex> не хуже, чем декомпрессор <tex>D_2</tex>, если <tex>\exists c > 0:\forall x \in \{0, 1\}^*\ K_{D_1}(x) \leqslant K_{D_2}(x) + c</tex>.
}}

{{Теорема
|statement = Существует '''оптимальный декомпрессор''' (англ. ''optimal decompressor'') <tex>U</tex>, который не хуже всех остальных.
|proof = Пусть <tex>p</tex> {{---}} некоторая строка, <tex>|p| = n</tex>. Обозначим за <tex>\hat{p}</tex> строку <tex>p_1 p_1 p_2 p_2 \dots p_n p_n 0 1</tex> (мы удвоили каждый бит строки <tex>p</tex> и добавили в конце <tex>01</tex>). 
Оптимальный декомпрессор будет работать следующим образом: <tex>U(\hat{p}x) = \langle p \rangle(x)</tex>, т.е. он интерпретирует <tex>p</tex> как программу, а <tex>x</tex> как входные данные и запускает <tex>p</tex> на входе <tex>x</tex>.
Покажем, что такой декомпрессор будет не хуже любого другого. Пусть <tex>D</tex> {{---}} другой декомпрессор. По определению <tex>D</tex> {{---}} это алгоритм, значит есть программа, которая исполняет <tex>D</tex>. 
<tex>p</tex> {{---}} номер алгоритма <tex>D,\ p = \#D</tex>. Тогда: 
<tex>K_U(x) \leqslant K_D(x) + 2|p| + 2</tex>, т.к. <tex>K_D(x)</tex> достигается на <tex>D(y) = U(\hat{p}y) = x</tex>, т.е. для этого <tex>y</tex> есть строка <tex>\hat{p}y</tex>, которая даёт тот же самый результат и имеет длину не больше, чем на <tex>2|p| + 2</tex>. 
Нетрудно заметить, что <tex>2|p| + 2</tex> зависит только от <tex>D</tex>, но никак не зависит от <tex>x</tex>, т.е. является константой. 
Следовательно, <tex>U</tex> {{---}} оптимальный декомпрессор.
}}
{{Определение
|definition=
Пусть <tex>D</tex> {{---}} это оптимальный декомпрессор, тогда '''колмогоровская сложность''' <tex>KS(x) = K_D(x)</tex>.
}}
{{Утверждение
|statement= Очевидно, что если <tex>D_1</tex> и <tex>D_2</tex> {{---}} оптимальные декомпрессоры, то <tex>\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.
</tex>
}}

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

Докажем последнее свойство:
===Невычислимость===
{{Лемма
|statement=
Если <tex>f:\{0,1\}^* \rightarrow N</tex> {{---}} [[Вычислимые функции|вычислимая функция]], такая, что <tex>\forall x : f(x) \leqslant KS(x)</tex>, тогда <tex>f = O(1)</tex>.
|proof=
Пусть <tex>A(n) = \arg\min \limits_{x} f(x) \geqslant n</tex>, где <tex>n \in N</tex>, тогда <tex>A(n)</tex> {{---}} вычислимая (т.к <tex>f(x)</tex> {{---}} вычислима и ограничена), всюду определенная функция. 
По свойству невозрастания <tex>KS(x)</tex> при алгоритмических преобразованиях, <tex>KS(A(n)) \leqslant KS(n) + c_1 \leqslant \log_2 n + c_2</tex>. Вспомним, что <tex>f(x) \leqslant KS(x)</tex>, следовательно <tex>KS(A(n)) \geqslant f(A(n)) \geqslant n</tex>. Отсюда: <tex>\forall n : \log_2 n + c_2 \geqslant n</tex>, но ясно, что при больших <tex>n</tex> это неравенство не выполняется. Противоречие.
}}
<hr>
Примечание: если функция <tex>f(x)</tex> определена только на <tex>M \subset \{0,1\}^*</tex>, то лемма остается в силе с единственным отличием, что <tex>x</tex> пробегает все значения из <tex>M</tex> в порядке перечисления.

{{Утверждение
|about=следствие из леммы
|statement=
<tex>KS(x)</tex> невычислима.
|proof=
Пусть <tex>KS(x)</tex> вычислима. Возьмем вместо <tex>f(x)\ KS(x)</tex>. Очевидно, что <tex>KS(x) \leqslant KS(x)</tex>, но из принципа несжимаемости ясно, что <tex>KS(x)</tex> неограничена. Противоречие. Следовательно, <tex>KS(x)</tex> невычислима.
}}

==Применение==
===Альтернативное доказательство теоремы Гёделя о неполноте===
Г. Хайтин<ref name=chaitin/> заметил следующее:
{{Утверждение
|statement= В данной фиксированной системе вывода существует недоказуемое утверждение вида <tex>KS(x) \geqslant n</tex>
|proof=
Выпишем множество пар <tex>\{(x,n) |\ </tex> утверждение <tex>KS(x) \geqslant n</tex> доказуемо <tex>\}</tex>. Возможны два варианта:
* Все <tex>n \leqslant n_0</tex>. Это означает, что для всех строк будет доказуемо только <tex>KS(x) \geqslant n_0</tex>. Но т.к. мы знаем, что <tex>KS(x)</tex> неограничена, то существуют истинные, но недоказуемые утверждения.
* В этом множестве встречаются сколь угодно большие <tex>n</tex>, т.е. есть бесконечная последовательность <tex>(x_i, n_i)</tex>, в которой <tex>n_{i+1} > n_i</tex>. Заметим, что эта последовательность задает график какой-то функции. А если график функции перечислим, то сама функция является вычислимой. Также заметим, что всегда выполняется условие <tex>KS(x_i) \geqslant n_i</tex>, т.е. эта вычислимая функция является нижней оценкой на <tex>KS(x)</tex>, а мы знаем, что такие функции обязаны быть ограниченными. Противоречие.
}}
Заметим, что во всех множествах пар все <tex>n</tex> ограничены какой-то константой, следовательно существует огромное число истинных, но недоказуемых утверждений вида <tex>KS(x) \geqslant n</tex>

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

== См. также ==
* [[Busy beaver]]

== Примечания ==
<references>
<ref name=chaitin> [https://ru.wikipedia.org/wiki/%D0%A5%D0%B0%D0%B9%D1%82%D0%B8%D0%BD,_%D0%93%D1%80%D0%B5%D0%B3%D0%BE%D1%80%D0%B8 Грегори Джон Хайтин] {{---}} аргентино-американский математик и информатик, внёс вклад в метаматематику, совместно с Андреем Колмогоровым считается основателем алгоритмической теории информации. </ref>
</references>

== Источники информации ==
* [https://www.lektorium.tv/lecture/13494?id=13494 Лекция Дмитрия Ицыксона в CS центре]
* [https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BB%D0%BC%D0%BE%D0%B3%D0%BE%D1%80%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C Wikipedia — Колмогоровская сложность]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]

Викиконспекты - Вклад участника [ru]

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