Вывод вероятности для нижней границы алгоритмической сложности

[mns2012]

Событие сучайного возникновения конфигураций материи Х, характеризующихся значениями алгоритмической сложности ASC(X,C,P) ≥ α, экспоненциально редко:

Pr[ASC(X,C,P) ≥ α] ≤ 2^−α.

Доказательство. По определению, алгоритмическая сложность есть разница информации в Х и колмогоровской сложности Х в контексте С:

ASC(X,C,P) = I(X) − K(X|C).

Наша цель состоит в том, чтобы доказать, что вероятность некоторого события ограничена сверху. Это событие состоит в том, что алгоритмическая сложность конфигурации Х в контексте С при заданной стохастической модели (распределении вероятностей переменных модели) P больше или равна α бит:

ASC(X,C,P) ≥ α.

Распишем это условие:

I(X) − K(X|C) ≥ α.

−log₂P(X) − K(X|C) ≥ α.

−log₂P(X) ≥ α + K(X|C).

P(X) ≤ 2^{−(α + K(X|C))}.

P(X) ≤ 2^−α * 2^−K(X|C).

Смысл этого неравенства в том, чтобы задать условие, при котором отдельно взятый исход (конкретная конфигурация Х) характеризуется алгоритмической сложностью. Для того, чтобы аргумент дизайна имел вес, необходимо показать, что вероятность не только отдельного исхода, но суммарная вероятность всех подобных исходов, очень мала. Таким образом мы сможем отклонить "лотерейный" аргумент, когда оппоненты говорят нам: "кому-то ведь должен был выпасть счастливый билет". Этот аргумент неприложим к случаю распознавания дизайна, поскольку он не учитывает наличия спецификации, заранее задающей, кому именно должен выпасть счастливый билет. Таким образом, нам нужно показать малость вероятности не только отдельного исхода, но целого множества исходов, для которых ASC(X,C,P) ≥ α. Для этого необходимо просуммировать полученное неравенство по всем возможным Х, для которых ASC(X,C,P) ≥ α:

Pr[ASC(X,C,P) ≥ α] = Σ P(X).

Pr[ASC(X,C,P) ≥ α] ≤ Σ 2^−α * 2^−K(X|C).

Pr[ASC(X,C,P) ≥ α] ≤ 2^−α * Σ 2^−K(X|C).

K(X|C) представляет собой длину кратчайшей программы (в контексте С), которая генерирует конфигурацию Х и останавливается. Величину 2^−K(X|C) можно рассматривать как вероятность того, что случайно выбранная программа длиной K(X|C) генерирует Х.

• Такое рассмотрение корректно лишь при условии использования префиксных кодов, то есть таких кодов, которые предполагают при написании инструкций вычислительной машине использование кодовых слов, ни одно из которых не является префиксом другого. Например, слова 0, 10 и 11 являются префиксными, позволяющими разбить инструкцию 01001101110 на слова единственным способом. Код, состоящий из слов 0, 10, 11 и 100, префиксным не является: слово 10 — префикс слова 100. Использование префиксных кодов важно для обеспечения самодостаточности инструкций: программа подаётся на вход вычислительной машине в качестве битовой строки, которая однозначно интерпретируется машиной единственным способом, не нуждаясь в разделителях между словами, выводит интересующую нас конфигурацию Х и останавливается.

Можно показать, что:

• Перевод с одного языка программирования на другой не сильно меняет длины программ и поэтому колмогоровская сложность K не зависит от языка реализации программ;


• Любую программу можно перевести на язык префиксных кодов, используя в качестве символов такие, которые не являются префиксами других.


• Неравенство Крафта — это необходимое и достаточное условие, определяющее, можно ли построить эффективный префиксный код с заданным набором длин кодовых слов (l₁ ≤ l₂ ≤ l₃ ... ≤ l_n); оно гласит, что сумма величин r^−l_i по всем длинам l_i должна быть меньше или равна 1, что гарантирует отсутствие взаимного перекрытия в "дереве кодов", где r — число символов кодирующего алфавита, например в булевом алфавите 2 символа: {0,1}. Строки, составленные из символов булева алфавита называют бинарными или битовыми, так как каждый символ в строке "весит" ровно 1 бит информации.


• По построению, в множестве кратчайших программ, выводящих конфигурации Х и останавливающихся, каждая программа представляет собой битовую строку, закодированную префиксным кодом.


• Использование префиксных кодов важно с той точки зрения, что обсуждение вероятностей генерации конфигурации Х программами, представляющими собой битовые строки, становится математически строгим. В частности, именно использование префиксных кодов позволяет утверждать верность доказываемого нами неравенства. В противном случае, если бы мы разрешили использовать любую бинарную строку в качестве программы, выводящей Х и останавливающейся, тогда не было бы возможности ограничить пространство возможных исходов и мы не смогли бы гарантировать того, сумма величин 2^−K(X|C) по всем возможным программам ограничена сверху единицей и может быть проинтерпретирована как вероятность. Это рассуждение связано с понятием константы Чейтина Ω — вероятности того, что случайно выбранная битовая строка окажется корректной останавливающейся программой для универсальной беспрефиксной (prefix-free) машины Тьюринга.

В силу неравенства Крафта сумма по всем Х: Σ 2^−K(X|C) ≤ 1. Следовательно, неравенство Σ 2^−K(X|C) ≤ 1 также справедливо и для подмножества всех возможных Х, для которого: ASC(X,C,P) ≥ α.

Поэтому:

Pr[ASC(X,C,P) ≥ α] ≤ 2^−α * Σ 2^−K(X|C).

Pr[ASC(X,C,P) ≥ α] ≤ 2^−α * 1.

Pr[ASC(X,C,P) ≥ α] ≤ 2^−α.

Ч.т.д.

Можно было бы задаться вопросом: не будет ли короче доказательство с учётом того наблюдения, что 2^−K(X|C) — вероятность того, что выбранная наугад программа длиной K(X|C) выдаст Х и остановится? Это верно, но лишь при условии использования префиксных кодов.