Изменения

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

Можем дать следующее определение. ''Количество информации'', которое несет строка {{---}} это размер архивафайла, полученного сжатием строки каким-то конкретным архиватором компрессором (например, [[Алгоритм 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> '''return'''<tex>(x)</tex> </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 — Колмогоровская сложность] [[Категория: Теория формальных языков]][[Категория: Теория вычислимости]]