Колмогоровская сложность — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства)
м (rollbackEdits.php mass rollback)
 
(не показано 37 промежуточных версий 6 участников)
Строка 1: Строка 1:
'''Колмогоровскую сложность''' можно рассматривать как способ измерения количества информации в строке.
+
'''Колмогоровскую сложность''' (англ. ''Kolmogorov complexity'') можно рассматривать как способ измерения количества информации в строке.
  
 
Но как понять, какое ''количество информации'' содержит в себе строка? Один из классических способов {{---}} это подсчет количества битов (число, пропорциональное длине строки). Рассмотрим следующий пример:
 
Но как понять, какое ''количество информации'' содержит в себе строка? Один из классических способов {{---}} это подсчет количества битов (число, пропорциональное длине строки). Рассмотрим следующий пример:
Строка 5: Строка 5:
 
Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов.
 
Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов.
  
Можем дать следующее определение. ''Количество информации'', которое несет строка {{---}} это размер архива, полученного сжатием строки каким-то конкретным архиватором (например, LZW). Это более нетривиальная задача, но мы можем придумать строку, которая явно несет в себе мало информации, но которую архиватор тем не менее не сожмет.
+
Можем дать следующее определение. ''Количество информации'', которое несет строка {{---}} это размер файла, полученного сжатием строки каким-то конкретным компрессором (например, [[Алгоритм LZW|LZW]]). Но мы по-прежнему можем придумать строку, которая явно несет в себе мало информации, но которую компрессор тем не менее не сожмет.
  
Еще более сильное определение. ''Количество информации'', которое несет строка {{---}} это размер архива, сжатого максимальным образом, самым лучшим архиватором. Но тогда встает вопрос, почему такой архиватор существует. На самом деле он есть, и в некотором смысле '''колмогоровская сложность''' строки {{---}} это размер наименьшей программы, которая печатает эту строку.
+
Еще более сильное определение. ''Количество информации'', которое несет строка {{---}} это размер файла, сжатого максимальным образом, самым лучшим компрессором. Но тогда встает вопрос, почему такой компрессор существует. На самом деле он есть, и в некотором смысле '''колмогоровская сложность''' строки {{---}} это размер наименьшей программы, которая печатает эту строку.
  
 
==Определения==
 
==Определения==
 +
===Декомпрессор===
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Назовём '''декомпрессором''' <tex>D : \{0, 1\}^* \to
+
Назовём '''декомпрессором''' (англ. ''decompressor'') <tex>D : \{0, 1\}^* \to
 
\left[\begin{array}{l}\{0, 1\}^* \\
 
\left[\begin{array}{l}\{0, 1\}^* \\
 
\bot\end{array}\right.</tex> алгоритм, восстанавливающий разжатый текст из сжатого.
 
\bot\end{array}\right.</tex> алгоритм, восстанавливающий разжатый текст из сжатого.
Строка 23: Строка 24:
 
Пусть <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>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) = x</tex>, тогда <tex>K_D(x) = |x|</tex>  
Строка 28: Строка 30:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Будем говорить, что декомпрессор <tex>D_1</tex> '''лучше''', чем декомпрессор <tex>D_2</tex>, если <tex>\exists c:\forall x \in \{0, 1\}^*\ K_{D_1}(x) \leqslant K_{D_2}(x) + c</tex>.
+
Будем говорить, что декомпрессор <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 = Существует оптимальный декомпрессор <tex>U</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 ... p_n p_n 0 1</tex> (мы удвоили каждый бит строки <tex>p</tex> и добавили в конце <tex>01</tex>).<br>
+
|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>.
 
Оптимальный декомпрессор будет работать следующим образом: <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>
+
Покажем, что такой декомпрессор будет не хуже любого другого. <br> Пусть <tex>D</tex> {{---}} другой декомпрессор. По определению <tex>D</tex> {{---}} это алгоритм, значит есть программа, которая исполняет <tex>D</tex>. <br>
 
<tex>p</tex> {{---}} номер алгоритма <tex>D,\ p = \#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>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>
Строка 55: Строка 57:
 
</tex>
 
</tex>
 
}}
 
}}
 +
 
==Свойства==
 
==Свойства==
 +
===Тривиальные свойства===
 
* <tex>KS(x) \leqslant |x| + c</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>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>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>\exists x \in \{0,1\}^n : KS(x) \geqslant n</tex> <br> (Какой бы у нас ни был компрессор, он не может все строки фиксированной длины делать меньше. Строк длины меньшей, чем <tex>n</tex> {{---}} <tex>(2^n-1)</tex>, мы не сможем декомпрессировать)
 
* <tex>KS</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://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 — Колмогоровская сложность]
 
* [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 — Колмогоровская сложность]
 
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория вычислимости]]
 
[[Категория: Теория вычислимости]]

Текущая версия на 19:26, 4 сентября 2022

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

Но как понять, какое количество информации содержит в себе строка? Один из классических способов — это подсчет количества битов (число, пропорциональное длине строки). Рассмотрим следующий пример:

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Понятно, что эту строку можно описать более компактно на естественном языке, "128 нулей", всего 9 символов.

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

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

Определения

Декомпрессор

Определение:
Назовём декомпрессором (англ. decompressor) [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 \gt 0:\forall x \in \{0, 1\}^*\ K_{D_1}(x) \leqslant K_{D_2}(x) + c[/math].


Теорема:
Существует оптимальный декомпрессор (англ. optimal decompressor) [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 \dots 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]KS(x)[/math] вычислима. Возьмем вместо [math]f(x)\ KS(x)[/math]. Очевидно, что [math]\forall x : f(x) \leqslant KS(x)[/math], но из принципа несжимаемости ясно, что [math]KS(x)[/math] неограничена. Противоречие. Следовательно, [math]KS(x)[/math] невычислима.

[math] \forall x \gt x_0: K(x) \gt f(x)[/math], если только [math]f \leqslant const [/math] или [math] f [/math] — невычислима.

Альтернативное доказательство с использованием теоремы о рекурсии

Функция [math] K(x) [/math] — это минимальная длина программы [math] p : p(\varepsilon) = x [/math]. Допустим, что [math] K [/math] вычислима, тогда напишем такую программу:

 [math]p(\varepsilon){:}[/math]
   foreach [math]x\in ~ \Sigma^* [/math] //перебираем слова по возрастанию длины
     if [math] K(x) \gt  |p|[/math] //теорема о рекурсии используется здесь
       return[math](x)[/math]     

Длина этой программы меньше длины минимальной программы, которая возвращает [math]x[/math] на пустом входе. Поэтому возникает противоречие. Следовательно [math] K [/math] невычислима.

Применение

Альтернативное доказательство теоремы Гёделя о неполноте

Г. Хайтин[1] заметил следующее:

Утверждение:
В данной фиксированной системе вывода существует недоказуемое утверждение вида [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]

Доказательство бесконечности простых чисел

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

См. также

Примечания

  1. Грегори Джон Хайтин — аргентино-американский математик и информатик, внёс вклад в метаматематику, совместно с Андреем Колмогоровым считается основателем алгоритмической теории информации.

Источники информации