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

Материал из Викиконспекты
Версия от 17:24, 2 января 2017; ExileHell (обсуждение | вклад) (Доказательство)
Перейти к: навигация, поиск

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

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

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

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

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

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

Определения

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

Определение:
Назовём декомпрессором (англ. decompressor) D:{0,1}[{0,1} алгоритм, восстанавливающий разжатый текст из сжатого.

Примечание: для простоты мы будем рассматривать бинарный алфавит, но все утверждения мы можем обобщить на строки произвольного алфавита.

Относительно каждого декомпрессора мы можем определить понятие сложности строки:

Определение:
Пусть x{0,1}, тогда назовем колмогоровской сложностью строки KD(x)=miny {|y| | D(y)=x}, размер минимальной строки y, такой, что D(y)=x.
Если такого y не существует, тогда KD(x)=+.


Примеры

  • D(x)=x, тогда KD(x)=|x|
  • D(x)=xx, тогда KD(0000)=2,KD(01)=+
Определение:
Будем говорить, что декомпрессор D1 не хуже, чем декомпрессор D2, если c>0:x{0,1} KD1(x)KD2(x)+c.


Теорема:
Существует оптимальный декомпрессор (англ. optimal decompressor) U, который не хуже всех остальных.
Доказательство:

Пусть p — некоторая строка, |p|=n. Обозначим за ˆp строку p1p1p2p2pnpn01 (мы удвоили каждый бит строки p и добавили в конце 01).
Оптимальный декомпрессор будет работать следующим образом: U(ˆpx)=p(x), т.е. он интерпретирует p как программу, а x как входные данные и запускает p на входе x. Покажем, что такой декомпрессор будет не хуже любого другого.
Пусть D — другой декомпрессор. По определению D — это алгоритм, значит есть программа, которая исполняет D.
p — номер алгоритма D, p=#D. Тогда:
KU(x)KD(x)+2|p|+2, т.к. KD(x) достигается на D(y)=U(ˆpy)=x, т.е. для этого y есть строка ˆpy, которая даёт тот же самый результат и имеет длину не больше, чем на 2|p|+2.
Нетрудно заметить, что 2|p|+2 зависит только от D, но никак не зависит от x, т.е. является константой.

Следовательно, U — оптимальный декомпрессор.
Определение:
Пусть D — это оптимальный декомпрессор, тогда колмогоровская сложность KS(x)=KD(x).
Утверждение:
Очевидно, что если D1 и D2 — оптимальные декомпрессоры, то c1,c2:x:{KD1(x)KD2(x)+c1KD2(x)KD1(x)+c2

Свойства

Тривиальные свойства

  • KS(x)|x|+c
  • KS(x,y)KS(x)+KS(y)+2log2KS(x)+2
  • Если A — алгоритм, то KS(A(x))KS(x)+cA
    (A(x) запишем как пару — информация об алгоритме A и информация о строке x, по предыдущему пункту нам нужно закодировать только сложность первого аргумента, что есть константа)
  • Принцип несжимаемости: x{0,1}n:KS(x)n
    (Какой бы у нас ни был компрессор, он не может все строки фиксированной длины делать меньше. Строк длины меньшей, чем n(2n1), мы не сможем декомпрессировать)
  • KS — невычислимая функция.

Докажем последнее свойство:

Невычислимость

Утверждение (Лемма):
Если f:{0,1}Nвычислимая функция, такая, что x:f(x)KS(x), тогда f=O(1).

Пусть A(n)=argminxf(x)n, где nN, тогда A(n) — вычислимая (т.к f(x) — вычислима и ограничена), всюду определенная функция.

По свойству невозрастания KS(x) при алгоритмических преобразованиях, KS(A(n))KS(n)+c1log2n+c2.
Вспомним, что f(x)KS(x), следовательно KS(A(n))f(A(n))n.
Отсюда: n:log2n+c2n, но ясно, что при больших n это неравенство не выполняется. Противоречие.

Примечание: если функция f(x) определена только на M{0,1}, то лемма остается в силе с единственным отличием, что x пробегает все значения из M в порядке перечисления.

Утверждение (следствие из леммы):
KS(x) невычислима.

Доказательство

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

x>x0:K(x)>f(x), если только fconst или f — невычислима.

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

Функция K(x) равна минимальной длине программы p:p(ε)=x. Допустим, что K вычислима, тогда напишем такую программу:

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

Начиная с x0, f(x)>|p|.

Применение

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

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

Утверждение:
В данной фиксированной системе вывода существует недоказуемое утверждение вида KS(x)n

Выпишем множество пар {(x,n)|  утверждение KS(x)n доказуемо }. Возможны два варианта:

  • Все nn0. Это означает, что для всех строк будет доказуемо только KS(x)n0. Но т.к. мы знаем, что KS(x) неограничена, то существуют истинные, но недоказуемые утверждения.
  • В этом множестве встречаются сколь угодно большие n, т.е. есть бесконечная последовательность (xi,ni), в которой ni+1>ni. Заметим, что эта последовательность задает график какой-то функции. А если график функции перечислим, то сама функция является вычислимой. Также заметим, что всегда выполняется условие KS(xi)ni, т.е. эта вычислимая функция является нижней оценкой на KS(x), а мы знаем, что такие функции обязаны быть ограниченными. Противоречие.

Заметим, что во всех множествах пар все n ограничены какой-то константой, следовательно существует огромное число истинных, но недоказуемых утверждений вида KS(x)n

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

Утверждение:
Простых чисел бесконечно много.
Предположим, что простых чисел конечное число. Тогда любое число n=p1α1p2α2pkαk, где k — это некоторая константа. Возьмём n наибольшей колмогоровской сложности. Тогда KS(n)log2n, но также KS(n)2klog2log2n+c, т.к. αilog2n. Но это неравенство не будет выполняться на достаточно больших n, противоречие.

См. также

Примечания

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

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