Редактирование: Колмогоровская сложность

'''Колмогоровскую сложность''' (англ. ''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>. <br> Если такого <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>).<br>
Оптимальный декомпрессор будет работать следующим образом: <tex>U(\hat{p}x) = \langle p \rangle(x)</tex>, т.е. он интерпретирует <tex>p</tex> как программу, а <tex>x</tex> как входные данные и запускает <tex>p</tex> на входе <tex>x</tex>.
Покажем, что такой декомпрессор будет не хуже любого другого. <br> Пусть <tex>D</tex> {{---}} другой декомпрессор. По определению <tex>D</tex> {{---}} это алгоритм, значит есть программа, которая исполняет <tex>D</tex>. <br>
<tex>p</tex> {{---}} номер алгоритма <tex>D,\ p = \#D</tex>. Тогда:<br>
<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>. <br>
Нетрудно заметить, что <tex>2|p| + 2</tex> зависит только от <tex>D</tex>, но никак не зависит от <tex>x</tex>, т.е. является константой. <br>
Следовательно, <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> <br> (<tex>A(x)</tex> запишем как пару {{---}} информация об алгоритме <tex>A</tex> и информация о строке <tex>x</tex>, по предыдущему пункту нам нужно закодировать только сложность первого аргумента, что есть константа)
* '''Принцип несжимаемости:''' <tex>\exists x \in \{0,1\}^n : KS(x) \geqslant n</tex> <br> (Какой бы у нас ни был компрессор, он не может все строки фиксированной длины делать меньше. Строк длины меньшей, чем <tex>n</tex> {{---}} <tex>(2^n-1)</tex>, мы не сможем декомпрессировать)
* <tex>KS</tex> {{---}} невычислимая функция.

Докажем последнее свойство:
===Невычислимость===
{{Утверждение
|about=Лемма
|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> {{---}} вычислима и ограничена), всюду определенная функция. <br>
По свойству невозрастания <tex>KS(x)</tex> при алгоритмических преобразованиях, <tex>KS(A(n)) \leqslant KS(n) + c_1 \leqslant \log_2 n + c_2</tex>. <br> Вспомним, что <tex>f(x) \leqslant KS(x)</tex>, следовательно <tex>KS(A(n)) \geqslant f(A(n)) \geqslant n</tex>. <br> Отсюда: <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> невычислима.
}}

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

<tex> \forall x > x_0: K(x) > f(x)</tex>, если только <tex>f \leqslant const </tex> или <tex> f </tex> {{---}} невычислима.

====Альтернативное доказательство с использованием теоремы о рекурсии====
Функция <tex> K(x) </tex> {{---}} это минимальная длина программы <tex> p : p(\varepsilon) = x </tex>.
Допустим, что <tex> K </tex> вычислима, тогда напишем такую программу:
<code>
  <tex>p(\varepsilon){:}</tex>
    '''foreach''' <tex>x\in ~ \Sigma^* </tex> <span style="color:Green">//перебираем слова по возрастанию длины</span>
      '''if''' <tex> K(x) > |p|</tex> <span style="color:Green">//теорема о рекурсии используется здесь</span>
        '''print'''<tex>(x)</tex>
        '''exit'''     
</code>

Длина этой программы меньше длины минимальной программы, которая возвращает <tex>x</tex> на пустом входе. Поэтому возникает противоречие.  Следовательно <tex> K </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 — Колмогоровская сложность]

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