3622
правки
Изменения
м
|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> невычислима.
[http://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 name=chaitin/> заметил следующее:
→Альтернативное доказательство с использованием теоремы о рекурсии
'''Колмогоровскую сложность ''' (англ. ''Kolmogorov complexity)''' ) можно рассматривать как способ измерения количества информации в строке.
Но как понять, какое ''количество информации'' содержит в себе строка? Один из классических способов {{---}} это подсчет количества битов (число, пропорциональное длине строки). Рассмотрим следующий пример:
Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов.
Можем дать следующее определение. ''Количество информации'', которое несет строка {{---}} это размер архивафайла, полученного сжатием строки каким-то конкретным архиватором компрессором (например, [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_LZW [Алгоритм LZW|LZW]]). Это более нетривиальная задача, но Но мы по-прежнему можем придумать строку, которая явно несет в себе мало информации, но которую архиватор компрессор тем не менее не сожмет.
Еще более сильное определение. ''Количество информации'', которое несет строка {{---}} это размер архивафайла, сжатого максимальным образом, самым лучшим архиваторомкомпрессором. Но тогда встает вопрос, почему такой архиватор компрессор существует. На самом деле он есть, и в некотором смысле '''колмогоровская сложность''' строки {{---}} это размер наименьшей программы, которая печатает эту строку.
==Определения==
{{Определение
|definition=
Назовём '''декомпрессором''' (англ. ''decompressor'') <tex>D : \{0, 1\}^* \to
\left[\begin{array}{l}\{0, 1\}^* \\
\bot\end{array}\right.</tex> алгоритм, восстанавливающий разжатый текст из сжатого.
Пусть <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>
{{Определение
|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>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>
|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> невычислима.
==Применение==
===Альтернативное доказательство теоремы Гёделя о неполноте===
{{Утверждение
|statement= В данной фиксированной системе вывода существует недоказуемое утверждение вида <tex>KS(x) \geqslant 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 — Колмогоровская сложность]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
