если В есть объединение перечислимого семейства интервалов, то и В' имеет такой вид, и бернуллиева мера В' не превосходит равномерной меры В. См. также доказательство более общего утверждения (теорема 123, с. 206).]

Интересно понять, какова может быть «сложность» МЛ-случайной (по равномерной мере) последовательности с точки зрения теории вычислимых функций. Мы уже видели, что такая последовательность не может быть вычислимой. Она также не может быть характеристикой функцией перечислимого множества.

**Теорема 36.** Пусть А — перечислимое множество натуральных чисел. Тогда его характеристическая последовательность $a_0 a_1 a_2 ...$, где $a_i = 0$ при $i \notin A$ и $a_i = 1$ при $i \in A$, не является МЛ-случайной по равномерной мере.

◀ Пусть $k$ — произвольное натуральное число. Будем перечислять множество А, следя за первыми $k$ членами его характеристикической последовательности. По мере перечисления среди этих членов появляются всё новые и новые единицы и мы получаем всё новые и новые варианты $k$-битового начала характеристикской последовательности (какой-то из них окажется окончательным, но у нас нет способа узнать об этом). Но так или иначе этих вариантов не больше $k+1$ штук (число единиц может меняться от 0 до $k$). И если мы все эти слова включим в покрытие, то общая мера интервалов покрытия будет не больше $(k+1)/2^k$ и таким образом может быть сделана сколь угодно малой. (Заметим, что в определении эффективно нулевого множества как раз требуется перечислять элементы покрытия, не указывая момента окончания такого перечисления.) ►

Возникает вопрос, можно ли вообще в каком-то смысле указать конкретную служайную по Мартин-Лёфу последовательность. Следующий результат (приводимый для читателей, знакомых с началами теории вычислимых функций, о которых можно прочесть, например, в [175]), показывает, что случайную последовательность можно найти в классе $\Sigma_2 \cap \Pi_2$ арифметической иерархии (другое описание последовательностей этого класса — вычислимые относительно $0'$ последовательности).

**Теорема 37.** Существует вычислимая относительно $0'$ последовательность, МЛ-случайная по равномерной мере.

◀ Достаточно показать, что для любого перечислимого множества слов $x_0, x_1, x_2, ...$, у которого $\sum 2^{-l(x_i)} < 1/2$, существует вычислимая относительно $0'$ последовательность, для которой ни одно из слов $x_i$ не является началом. (Максимальное эффективно нулевое множество имеет покрытие с суммой мер меньше $1/2$, и всякая последовательность вне этого покрытия будет МЛ-случайной.)

Посмотрим, как интервалы $\Omega_{x_i}$ распределяются между двумя половинами множества $\Omega$ (какие из них начинаются на нуль, а какие на единицу).

В сумме мера тех и других не превосходит $1/2$, значит, мера интервалов, приходящихся на одну из половин, не больше $1/4$. Правда, наблюдая за последовательностью $x_i$, мы не можем с уверенностью выбрать нужную половину (вдруг потом объявится короткое слово, которое попадёт в эту половину).

Но если у нас есть оракул для $0'$, то с его помощью такой выбор можно сделать (поскольку превышение меры над $1/4$ есть перечислимое событие). Соответствующую половину разделим на две четверти и посмотрим, в какой из них мера
интервалов покрытия будет не больше $1/8$. И так далее. Тем самым мы получим вычислимую (относительно $0'$) последовательность нулей и единиц с таким свойством: над любым её началом интервалы покрытия заполняют не более половины всех продолжений. В частности, никакое начало этой последовательности не может войти в покрытие, что нам и требовалось. ►

Похожее, но более геометрически наглядное рассуждение получится, если говорить о точках отрезка $[0, 1]$ вместо двоичных последовательностей. Такую точку называют МЛ-случайной относительно меры Лебега на $[0, 1]$, если её двоичная запись МЛ-случайна относительно равномерной меры на $\Omega$. (Наличие двух двоичных записей тут не важно, так как в этой ситуации обе они не случайны.) Случайность в этом смысле можно эквивалентно определить и геометрически. Множество $X \subset [0, 1]$ объявим эффективно нулевым подмножеством $[0, 1]$, если существует алгоритм, который по рациональному $\epsilon > 0$ перечисляет покрытие этого множества рациональными интервалами, сумма длин которых меньше $\epsilon$. Случайными будут точки, не покрытые никакими эффективно нулевыми множествами. Всё это является простой переформулировкой соответствующих понятий для канторовского пространства (поскольку оно отличается от $[0, 1]$ лишь наличием двух копий для двоично-рациональных точек, что не сказывается на нулевых множествах). В частности, верно такое свойство:

**85** Показайте, что существует максимальное эффективно нулевое множество, и оно состоит из точек, двоичные записи которых не случайны в канторовском пространстве.

Теперь можно указать «конкретную» случайную точку. Возьмём перечислимое семейство интервалов суммарной длины меньше 1, покрывающее все неслучайные точки. Они в объединении дают открытое множество, не совпадающее со всем отрезком. Дополнение этого открытого множества будет замкнутым множеством. Наименьшая точка этого множества будет (по построению) случайной.

**86** Доказите, что наименьшая точка отрезка $[0, 1]$, не покрытая некоторым перечислимым семейством интервалов, является перечислимой снизу, то есть пределом возрастающей вычислимой последовательности рациональных чисел (и потому вычислима с оракулом $0'$).

Ещё одна конструкция последовательности с таким свойством (задающей случайное перечислимое снизу число) приведена в разделе 5.7 на с. 179.

Приведённое нами доказательство теоремы 37 представляет собой релятивизованный вариант такой задачи:

**87** Пусть имеется вычислимая последовательность слов $x_0, x_1, x_2, \dots$, причём сумма ряда

$$ \sum_i 2^{-l(x_i)} $$

меньше 1 и является вычислимым действительным числом. Тогда существует вычислимая последовательность нулей и единиц, для которой ни одно из слов $x_i$ не является началом.
[Указание. Пусть сумма этого ряда меньше рационального числа $S$, меньшего единицы. Тогда можно по индукции построить вычислимую последовательность $\omega_0\omega_1\omega_2...$ с таким свойством: доля множества $U = \bigcup \Omega_{x_i}$ среди продолжений слова $\omega_0...\omega_k$ составляет менее $S$.]

Последняя задача связана с модификацией определения случайности по Мартин-Лёфу, предложенной Шнорром [143]. А именно, в определении эффективно нулевого множества можно дополнительно потребовать, чтобы для каждого $\epsilon > 0$ ряд из мер покрывающих интервалов (сумма которого не должна превосходить $\epsilon$) вычислимо сходился. Это означает, что для каждого $\epsilon > 0$ и $\delta > 0$ можно алгоритмически указать конечное число членов ряда $\sum_i p(x(\epsilon, i))$, которые все определены и приближают сумму всего ряда с ошибкой не более $\delta$. (Поскольку члены ряда неотрицательны, это эквивалентно тому, что его сумма является вычислимым действительным числом, которое можно указать по $\epsilon$.) Эффективно нулевые множества, для которых выполнено это дополнительное условие, будем называть эффективно нулевыми по Шнорру. (Шнорр называет их total rekursive Nullmenge, см. определение 8.1 в [143], в отличие от эффективно нулевых в смысле Мартин-Лёфа, которые называются у Шнорра rekutive Nullmenge, см. там же определение 4.1.)

88 Показите, что если в определении эффективно нулевого множества требовать, чтобы суммарная мера покрывающих интервалов в точности равнялась $\epsilon$, то получится определение, эквивалентное определению Шнорра. (Можно также вместо суммарной меры покрывающих интервалов говорить о мере их объединения.)

Задача 87 показывает, что для любого эффективно нулевого по Шнорру множества существует вычислимая последовательность, ему не принадлежащая. (Для простоты мы ограничиваемся случаем равномерной меры, хотя это и не существенно.) Поскольку вычислимая последовательность образует одноэлементное эффективно нулевое по Шнорру множество, отсюда следует, что среди эффективно нулевых по Шнорру множеств нет наибольшего (другими словами, объединение нулевых по Шнорру множеств не является нулевым по Шнорру). Тем не менее можно назвать последовательность, не входящую ни в одно нулевое по Шнорру множество, **случайной по Шнорру** (или **типической по Шнорру**).

Полученный класс последовательностей оказывается более широким: как показывает следующая задача (и результаты главы 5), существуют случайные по Шнорру последовательности, не являющиеся случайными по Мартин-Лёфу.

89 Показите, что существует случайная по Шнорру последовательность $\omega = \omega_0\omega_1\omega_2...$, у которой сложность начальных отрезков растёт логарифмически, то есть $KS(\omega_0...\omega_{n-1}) = O(\log n)$.

[Указание. В задаче 87 мы видели, как строить вычислимую последовательность, не принадлежащую заданному эффективно нулевому по Шнорру множеству. Если в какой-то момент мы захотим ввести в это построение другое эффективно нулевое по Шнорру множество, это вполне возможно, надо только выбрать достаточно малое покрытие (исходя из имеющегося на данный момент запаса). Так можно вводить эффективно нулевые множества одно за другим. Это не даст вычислимой случайной по Шнорру последовательности (которой быть не может), поскольку нам нужна дополнительная информация о том, какие алгоритмы задают эффективно нулевые
по Шнорру множества, а какие нет. Но если вводить новые алгоритмы постепенно, когда построенный кусок последовательности уже длинен, то эта дополнительная информация будет логарифмической по сравнению с длиной последовательности.

Мы вернёмся к определению случайности по Шнорру в разделе 9.8, где будет дана его переформулировка в терминах вычислимых мартингалов.

**90** Покажите, что последовательность $\omega$ не является случайной по Шнорру тогда и только тогда, когда существует вычислимая последовательность слов $x_0, x_1, \dots$, для которой ряд $\sum_i p(x_i)$ вычислимо сходится и среди $x_i$ имеется бесконечное много начал последовательности $\omega$.) [Указание. Это утверждение является аналогом критерия Соловея случайности по Мартин-Лёфу, теоремы 31, и может быть доказано аналогичным образом. В данном случае, впрочем, работает и стандартное доказательство леммы Бореля – Кантелли.]

Ещё один вариант случайности возникает, если в определении эффективно нулевого множества рассматривать конечные покрытия (заданные списком) вместо бесконечных: по рациональному $\varepsilon > 0$ надо указывать список интервалов общей меры меньше $\varepsilon$, покрывающий множество. (Это соответствует продолжению меры по Жордану в курсах математического анализа.) При этом получается меньший класс нулевых множеств (например, нельзя покрыть все рациональные числа).

**91** Покажите, что множество является нулевым в этом смысле тогда и только тогда, когда оно содержится в дополнении эффективно открытого множества полной меры.

Последовательности, не содержащиеся в таких множествах ($= входящие в любое эффективно открытое множество полной меры), называют случайными по Курцу (Kurtz random). Поскольку нулевых множеств в этом определении меньше, чем у Мартин-Лёфа, и даже меньше, чем у Шнорра, то случайных последовательностей будет больше, и даже строго больше, как показывает следующая задача.

**92** Покажите, что случайная по Шнорру (относительно равномерной меры) последовательность всегда удовлетворяет усиленному закону больших чисел. Покажите, что случайная по Курцу последовательность может не удовлетворять усиленному закону больших чисел. [Указание. Построенное при доказательстве усиленного закона больших чисел множество имеет вычислимую меру, поскольку ряд экспоненциально сходится. Во втором случае можно рассмотреть генерические последовательности, см. раздел 5.9, с. 203.]

## 3.5. Дефект случайности

Согласно определению Мартин-Лёфа, для эффективно нулевого множества А по любому $\varepsilon > 0$ можно эффективно указать покрытие А семейством интервалов, суммарная мера которых не превосходит $\varepsilon$. Объединение интервалов этого семейства будет открытым множеством меры не более $\varepsilon$.

Вообще объединения вычислимых последовательностей интервалов называют эффективно открытыми множествами. Как и в определении эффективно нулевого множества (с. 70), мы разрешаем не всюду определённые последовательности,
так что пустое множество тоже эффективно открыто. Переформулировка: эффективно открытое множество есть объединение перечислимого семейства интервалов (появляющихся на выходе перечисляющего их алгоритма).

Определение эффективно нулевого множества можно теперь переформулировать:

**Теорема 38.** Множество А является эффективно нулевым относительно метры µ тогда и только тогда, когда $A \subset \bigcap_n U_n$, где $U_n$ — равномерно эффективно открытые множества и $µ(U_n) \le 2^{-n}$. При этом можно дополнительно предполагать, что $U_1 \supset U_2 \supset \dots$.

Говоря о равномерности, мы имеем в виду существование алгоритма, который на вход получает $n$ и перечисляет интервалы, объединение которых составляет $U_n$.

◀ Это определение отличается от данного нами раньше в нескольких отношениях. Во-первых, в качестве $\varepsilon$ выбираются числа вида $2^{-n}$ (которыми, очевидно, можно ограничиться).

Во-вторых, мы говорим здесь о мере эффективно открытых множеств, а о не сумме мер интервалов, объединениями которых они являются. Но это не важно, так как интервалы можно считать непересекающимися: добавляя новый интервал канторовского пространства, мы вычитаем из него все старые, разбивая остаток в сумму непересекающихся интервалов. Тогда сумма мер не отличается от меры суммы.

Наконец, мы требуем вложенности множеств. Этого легко добиться, перейдя к последовательности $U_1, U_1 \cap U_2, U_1 \cap U_2 \cap U_3, \dots$ — надо только убедиться, что пересечение конечного числа эффективно открытых множества эффективно открыто (и соответствующий алгоритм может быть эффективно указан). В самом деле, пусть даны два алгоритма, перечисляющих интервалы для $U_1$ и $U_2$. Тогда в каждый момент текущие приближения для $U_1$ и $U_2$ можно пересечь, это будет конечное объединение интервалов, и все эти интервалы можно добавить в перечисление для $U_1 \cap U_2$ (их даже можно сделать непересекающимися, как описано выше). ►

Именно так и выглядело оригинальное определение Мартин-Лёфа [97]; семейства множеств $U_n$ с указанными свойствами он называл тестами. Имея такой тест $U_1, U_2, \dots$, можно определить функцию «дефект случайности», ему соответствующую: дефект последовательности $\omega$ определяется как наибольшее $i$, при котором $\omega \in U_i$. Дефект бесконечен, когда $\omega$ принадлежит всем $U_i$. При таком определении тест не только отбраковывает последовательности из $\bigcap_n U_n$, но и для остальных последовательностей указывает, насколько они близки к опасной зоне (чем ближе, тем больше дефект).

Наибольшему эффективному множеству соответствует тест, который отбраковывает максимальное число последовательностей. Мартин-Лёф заметил, что можно построить универсальный тест даже и в более сильном смысле:

**Теорема 39.** Существует тест случайности, для которого функция дефекта является максимальной с точностью до аддитивной константы.
◀ Описанное выше построение покрытий для максимального нулевого множества даёт такой тест: мы можем соединить тесты

$$U^1: U_1^1 \supset U_2^1 \supset U_3^1 \supset \dots$$

$$U^2: U_1^2 \supset U_2^2 \supset U_3^2 \supset \dots$$

$$U^3: U_1^3 \supset U_2^3 \supset U_3^3 \supset \dots$$

....................

в единый тест

$$(U_2^1 \cup U_3^2 \cup \dots \cup U_{k+1}^k \cup \dots) \supset (U_3^1 \cup U_4^2 \cup \dots \cup U_{k+2}^k \cup \dots) \supset \dots$$

В этом тесте меры оцениваются как $1/4 + 1/8 + \dots \le 1/2$ для первого множества, $1/8 + 1/16 + \dots \le 1/4$ для второго и т. д.; функция дефекта для результирующего теста не меньше $d^i - i$, где $d^i$ — функция дефекта для i-го теста. ▶

Функция дефекта может рассматриваться как компактный способ представления теста: мы рассматриваем функции на Ω, значениями которых являются натуральные числа и бесконечность, при этом множество $U_n$ тех ω, на которых дефект превосходит n, должно быть эффективно открытым (равномерно по n).

Не обязательно ограничиваться функциями с целыми значениями. Будем говорить, что функция u, определённая на Ω и принимающая неотрицательные значения (возможно, бесконечные), является *перечислимой снизу*, если для любого рационального r множество тех последовательностей ω, где $u(ω) > r$, эффективно открыто равномерно по r. Следующая теорема позволяет дать эквивалентный вариант определения перечислимости снизу. Будем называть базисной функцией на канторовском пространстве функцию с рациональными значениями, зависящую только от некоторого начального отрезка последовательности-аргумента. Такая функция задаётся длиной этого отрезка, некоторым числом m, и таблицей из $2^m$ рациональных значений, соответствующих $2^m$ вариантам этого отрезка, поэтому базисные функции можно считать конструктивными объектами и говорить о вычислимых последовательностях таких функций.

**Теорема 40.** Следующие свойства функции v, определённой на канторовском пространстве и принимающей неотрицательные (возможно, бесконечные) значения, равносильны:

(а) v перечислима снизу;

(б) v является точной верхней гранью вычислимой последовательности базисных функций;

(в) v является поточечным пределом вычислимой неубывающей последовательности базисных функций;

(г) v является поточечной суммой вычислимого ряда, составленного из неотрицательных базисных функций.

◀ Два последних свойства эквивалентны, так как разность и сумма двух базисных функций является базисной функцией.
Чтобы перейти от точной верхней грани к пределу возрастающей последовательности, достаточно заметить, что максимум конечного числа базисных функций является базисной функцией.

Остаётся доказать, что первое свойство равносильно остальным (например, второму). Пусть $v = \sup_i v_i$. Заметим, что $\sup_i v_i(\omega) > r$ тогда и только тогда, когда $v_i(\omega) > r$ при некотором $i$, так что множество $\{\omega | v(\omega) > r\}$ оказывается (равномерно) эффективно открытым.

Наконец, если при каждом $r$ можно алгоритмически перечислять интервалы, на которых $u(\omega) > r$, то функция $u$ есть точная верхняя грань базисных функций, которые равны $r$ внутри таких интервалов и нулю в остальных местах. ►

Отбросив ограничение целочисленными значениями и переходя к экспоненциальной шкале, можно дать такое определение: ограниченным по вероятности testом случайности относительно вычислимой меры $\mu$ на $\Omega$ называется перечислимая снизу функция $u$, для которой

$$ \mu(\{\omega | u(\omega) > c\}) < 1/c $$

для любого положительного рационального $c$. Это определение соответствует интуиции: последовательностей, в которых тест находит много закономерностей (значение теста больше $c$), не должно быть много (вероятность случайно получить такое большое значение не превосходит $1/c$).

**Теорема 41.** Среди ограниченных по вероятности тестов относительно вычислимой меры $\mu$ существует максимальный (с точностью до постоянного множителя); двоичный логарифм такого теста совпадает с универсальным testом из теоремы 39 с точностью до $O(1)$.

◄ Произвольный тест можно заменить на тест со значениями вида $2^n$, заменив $u(\omega)$ на максимальную целую степень двойки, меньшую $u(\omega)$; это изменит тест не более чем в константу раз, сохранив перечислимость снизу. Тест с такими значениям соответствует набору эффективно открытых множеств, и условие на тест соответствует условиям на эти множества. Остаётся сослаться на теорему 39. ►

Есть и другой класс тестов, которые называют ограниченными в среднем тестами. В этом варианте ограничение на перечислимую снизу неотрицательную функцию $u$ более сильное: $\int u(\omega) d\mu(\omega) \le 1$.

**Теорема 42.** Среди ограниченных в среднем тестов относительно вычислимой меры $\mu$ существует максимальный (с точностью до постоянного множителя).

◄ Семейство всех перечислимых снизу функций можно эффективно перечислять (например, исходя из их представления в виде точной верхней грани перечислимого множества базисных функций). Далее, их можно корректировать, добиваясь, чтобы интеграл был не больше (скажем) 2 и оставляя тесты без изменений. (Здесь важно, что мера $\mu$ вычисlimа.) Получится равномерно перечислимая снизу последовательность $u_1, u_2, \dots$, составленная из тестов и почти тестов (с точностью до множителя 2). Из неё делаем универсальный тест, сложив $u_i$ с вычислимыми коэффициентами, образующими ряд с суммой $1/2$ или меньше. ►
Логарифмы максимальных тестов (ограниченных в среднем и по вероятности) будем называть дефектами случайности относительно вычислимой меры μ (с дополнительным уточнением «ограниченный в среднем» или «ограниченный по вероятности») и обозначать соответственно $d^E$ и $d^P$, от слов “expectation” и “probability”. (Вычислимую меру μ мы предполагаем фиксированной и в обозначение не включаем.)

**Теорема 43.**

$$d^P(\omega) - 2 \log d^P(\omega) \le d^E(\omega) \le d^P(\omega).$$

Оба неравенства понимаются с точностью до $O(1)$-слагаемого (и входящие в них величины определены с такой точностью).

◀ Второе неравенство следует из того, что всякий ограниченный в среднем тест ограничен и по вероятности. Чтобы доказать первое неравенство, убедимся в том, что $2$ в степени $d^P - 2 \log d^P$ имеет ограниченный интеграл (перечислимость снизу следует из того, что функция $x - 2 \log x$ монотонно возрастает; это не так для малых значений, но они всё равно не важны, так как дают только конечный вклад в интеграл, и там функцию можно заменить на возрастающую). В самом деле, множество тех последовательностей, где $d^P(\omega)$ находится между $n$ и $n+1$, имеет меру не больше $1/2^n$, поскольку тест $2^{d^E}$ там превосходит $2^n$, а подынтегральное выражение на этом множестве равно $O(2^n/n^2)$; остаётся заметить, что ряд $1/n^2$ сходится. ▶

**93** Покажите, что константу $2$ в теореме 43 можно заменить на любое число, большее $1$.

Из доказанной теоремы, в частности следует, что любой вид тестов можно использоваться для определения случайности по Мартин-Лёфу (для ограниченных по вероятности тестов мы это уже обсуждали): случайны те и только те последовательности, у которых дефект конечен.

Разница в определениях двух видов тестов напоминает различие между простой колмогоровской сложностью (которую мы рассматривали раньше) и префиксной сложностью (см. следующую главу).

Тесты случайности были определены и изучены ещё в 1960-е и 1970-е годы (ограниченные по вероятности тесты по существу были определены уже в самой первой работе Мартин-Лёфа; ограниченные в среднем тесты изучались в работах Л.А. Левина и П. Фача), но потом они (до недавнего времени) использовались мало. Более подробно об их применениях можно прочесть в [8].
# 4. Априорная вероятность и префиксная сложность

## 4.1. Вероятностные машины и полумеры на $N$

Рассмотрим алгоритм (машину, программу) с датчиком случайных битов. Такой алгоритм содержит операции

$$b := \text{random}$$

при которых переменной $b$ присваивается нуль или единица с равными вероятностями. (Встретив такую команду, мы прерываем выполнение алгоритма, бросаем честную монету и результат бросания записываем в переменную $b$.) Такие алгоритмы называют вероятностными.

Результат работы вероятностного алгоритма зависит не только от его входа, но и от результатов бросаний монеты (случайных битов). Таким образом, при данном входе выход (результат работы) алгоритма является случайной величиной.

Более формально вероятность того или иного выхода вероятностного алгоритма $A$ определяется так. На пространстве $\Omega$ всех бесконечных последовательностей нулей и единиц рассматривается равномерная бернуллиева мера. При этом мера множества $\Omega_u$ всех бесконечных продолжений данного конечного слова $u$ равна $2^{-l(u)}$.

Для данного входа $x$ и последовательности $\omega \in \Omega$ через $A(x, \omega)$ обозначим результат работы $A$ на входе $x$, если в качестве случайных битов берутся биты из последовательности $\omega$ (каждый вызов random берёт новый бит). Значение $A(x, \omega)$ — некоторый конструктивный объект (число, слово); оно может быть не определено при некоторых $x$ и $\omega$. Для каждого возможного выхода у алгоритма рассмотрим множество $\{\omega | A(x, \omega) = y\}$. Это множество измеримо (и даже открыто в смысле естественной топологии в $\Omega$); оно является объединением интервалов $\Omega_z$ для всех слов $z$, которые являются результатами бросаний монеты к моменту появления выхода $y$. Мера этого множества и называется вероятностью выхода у при входе $x$.

В этом разделе мы будем рассматривать вероятностные машины без входа, выходами которых являются натуральные числа. Пример: машина бросает монету, пока не появится единица, и выдаёт на выход число нулей перед первой единицей. Для этого алгоритма распределение вероятностей на возможных выходах такое: вероятность $p_i$ появления числа $i$ равна $2^{-(i+1)}$. В самом деле, $p_0$ есть вероятность того, что первое бросание монеты дало единицу, $p_1$ — вероятность того, что первое бросание дало нуль, а второе — единицу и так далее.
В данном конкретном случае сумма ряда $\sum p_i$ равна единице: вероятность того, что машина так ничего и не напечатает (так случится, если всё время будут выпадать нули) равна нулю. Но для других алгоритмов эта сумма может быть и меньше единицы.

Итак, каждой вероятностной машине без входа, выдающей натуральные числа на выходе, соответствует последовательность $p_0, p_1, \dots$, где $p_i$ есть вероятность появления числа $i$. Какие последовательности действительных чисел $p_0, p_1, \dots$ могут получиться таким образом? Одно условие очевидно: $\sum p_i \le 1$. Но, конечно, это условие не является достаточным: вероятностных машин счётное число, а возможных последовательностей $p_0, p_1, \dots$ — континуум.

Начнём с более простого вопроса: какова может быть вероятность остановки вероятностной машины (без входа)? Чтобы сформулировать ответ, введём понятие перечислимого снизу действительного числа.

Говорят, что действительное число $\alpha$ перечислимо снизу, если оно есть предел вычислимой неубывающей последовательности рациональных чисел.

**94** Докажите, что если действительное число $\alpha$ вычислимо (существует алгоритм, который по любому рациональному $\varepsilon > 0$ указывает приближение к $\alpha$ с погрешностью не более $\varepsilon$), то $\alpha$ перечислимо снизу. [Указание. Последовательность приближений снизу можно переделать в возрастающую.]

**95** Докажите, что действительное число $\alpha$ вычислимо тогда и только тогда, когда оба числа $\alpha$ и $-\alpha$ перечислимы снизу.

Вот эквивалентное определение перечислимости снизу: число $\alpha$ перечислимо снизу, если множество всех рациональных чисел, меньших $\alpha$, перечислимо.

В самом деле, если $\alpha$ есть предел неубывающей вычислимой последовательности $a_0 \le a_1 \le a_2 \le \dots$, то перечисляя все числа, меньшие какого-либо из $a_i$, мы перечислим все числа, меньшие $\alpha$. Напротив, умея перечислять все рациональные числа, меньшие $\alpha$, мы можем составить из них последовательность. Затем эту последовательность надо сделать неубывающей, выбрасывая из неё члены, меньшие уже встречавшихся.

Понятие перечислимого снизу действительного числа даёт ответ на поставленный нами вопрос:

**Теорема 44.** (а) Пусть $M$ — произвольная вероятностная машина (без входа). Тогда вероятность её остановки есть перечислимое снизу действительное число.

(б) Всякое перечислимое снизу действительное число есть вероятность остановки некоторой вероятностной машины.

◀ (а) Вероятность $p_n$ остановки машины в течение $n$ (или менее) шагов есть некоторое рациональное число: за $n$ шагов можно сделать не более $n$ бросаний монеты, поэтому каждый исход имеет вероятность, кратную $1/2^n$, и вероятность остановки также кратна $1/2^n$.

Число $p_n$ можно найти, моделируя работу машины при всех вариантах бросаний. С ростом $n$ оно возрастает (точнее, не убывает) и стремится к вероятности остановки машины (без ограничения числа шагов).
(б) Пусть $q$ — произвольное перечислимое снизу число. Это означает, что $q = \lim q_n$ для некоторой вычислимой последовательности

$$q_0 \le q_1 \le q_2 \le \dots$$

рациональных чисел. Построим машину, вероятность остановки которой равна $q$. Машина бросает монету и воспринимает полученные биты $b_0, b_1, b_2, \dots$ как последовательные знаки двоичного числа $\beta = 0, b_0 b_1 b_2 \dots$; параллельно она вычисляет рациональные числа $q_0, q_1, q_2, \dots$ и останавливается, как только имеющейся у неё информации достаточно, чтобы утверждать, что $\beta < q$. Другими словами, она останавливается, как только $0, b_0 b_1 \dots b_i 111 \dots$ (текущая верхняя оценка для числа $\beta$) оказывается меньше $q_i$ (текущей нижней оценки для числа $q$). Символически этот процесс изображён на рис. 4.1.

<figure><img src="image_11.png" /><figcaption>Рис. 4.1. Сравнение $\beta = 0, b_0 b_1 \dots$ и $q = \lim q_i$.</figcaption></figure>

Построенная машина останавливается тогда и только тогда, когда $\beta < q$. Убедимся в этом. Если число $\beta$ меньше $q$, то машина остановится. В самом деле, числа $q_i$ стремятся к $q$, а верхние оценки для числа $\beta$ стремятся к $\beta$, и потому в какой-то момент $q_i$ превысит текущую верхнюю оценку. С другой стороны, в случае остановки $\beta < q$ по построению.

Таким образом, вероятность остановки есть вероятность события $\beta < q$, то есть длина промежутка $[0, q)$, то есть $q$ (число $\beta$, составленное из случайных битов, равномерно распределено на отрезке $[0, 1]$). ►

Вернёмся к вопросу о том, каким может быть распределение вероятностей на выходах вероятностной машины. Нам понадобится следующее определение. Говорят, что последовательность действительных чисел $p_0, p_1, p_2, \dots$ перечислима снизу, если существует вычислимая всюду определённая функция $p$ двух натуральных аргументов с рациональными значениями (разрешается также дополнительное значение $-\infty$), для которой

$$p(i, 0) \le p(i, 1) \le p(i, 2) \le \dots$$

и

$$p_i = \lim_{n \to \infty} p(i, n)$$

для любого $i$.
Можно сказать, что в этом определении мы требуем перечислимости снизу чисел $p_i$ «равномерно по $i$». Можно было бы определить перечислимость снизу и по-другому, как показывает следующая теорема:

**Теорема 45.** Последовательность $p_0, p_1, p_2, \dots$ перечислима снизу тогда и только тогда, когда множество пары $\langle r, i \rangle$, где $i$ — натуральное число, а $r$ — рациональное число, меньше $p_i$, перечислимо.

◀ Перечислимость множества означает, что существует алгоритм, перечисляющий его элементы (в произвольном порядке, с произвольными промежутками; алгоритм может никогда не завершать работу, даже если множество конечно).

Предположим, что последовательность $p_0, p_1, p_2, \dots$ перечислима снизу и $p_i = \lim_n p(i, n)$. Алгоритм перебирает все пары $\langle r, i \rangle$, возвращаясь к каждой паре бесконечное число раз. При $n$-м обращении к паре $\langle r, i \rangle$ мы сравниваем $r$ с $p(i, n)$; если оказывается, что $r < p(i, n)$, то пара $\langle r, i \rangle$ включается в перечисление. Ясно, что таким образом мы перечислим все нужные пары и только их ($r < \lim_n p(i, n)$ тогда и только тогда, когда $r < p(i, n)$ для некоторого $n$).

Напротив, пусть свойство $r < p_i$ перечислимо. Возьмём алгоритм, перечисляющий такие пары. Чтобы вычислить $p(i, n)$, сделаем $n$ шагов перечисления; отберём все пары $\langle r, i \rangle$ с данным $i$ и возьмём в них максимальное $r$. Положим $p(i, n)$ равным этому $r$ (если пар с нужным значением $i$ не окажется, то $p(i, n) = -\infty$). Легко понять, что с ростом $n$ пар становится больше и значение $p(i, n)$ может только возрасти, а предел $\lim_n p(i, n)$ равен $p_i$ (поскольку в перечислении появляются все рациональные числа, меньшие $p_i$). ▶

Теперь можно дать обещанную характеристизацию распределений вероятностей, соответствующих вероятностным машинам.

**Теорема 46.** (а) Пусть $M$ — произвольная вероятностная машина без входа, возможными выходами которой являются натуральные числа. Пусть $p_i$ — вероятность появления числа $i$ на выходе. Тогда последовательность $p_i$ перечислима снизу и $\sum_i p_i \le 1$.

(б) Пусть $p_0, p_1, \dots$ — перечислимая снизу последовательность неотрицательных действительных чисел, причём $\sum_i p_i \le 1$. Тогда существует вероятностная машина $M$, для которой вероятность появления числа $i$ на выходе равна $p_i$.

◀ Первая часть доказательства (что вероятности перечислимы снизу) проходит точно так же, как и раньше, только вместо единственной вероятности остановки мы оцениваем снизу вероятность остановки с ответом $i$ (для каждого $i$).

Вторая часть на самом деле тоже мало меняется. Раньше у нас выделялась всё большая часть пространства под область остановки. Теперь область остановки будет поделена на счётное число подобластей; для каждого $i$ есть область остановки с ответом $i$. Возрастающие приближения снизу к $p_i$ составляют требования к размеру соответствующей области. Наша задача — распределять пространство между всеми требованиями. Это можно делать самым простым способом, выделяя каждому новому требованию кусок отрезка (слева направо) в соответствии с увеличением его заказа. Таким образом отрезок (не обязательно весь!) распределяется
между различными возможными выходами. Заметим, что область остановки с выходом $i$ не является связанной (она состоит из отдельных промежутков, число которых увеличивается по ходу процесса).

Параллельно с распределением отрезка по областям мы порождаем биты следующего числа $\beta$, и как только становится ясно, в чью область попадёт $\beta$, соответствующее число выдаётся на выход.

Более формально можно сказать это следующим образом. Пусть $p_i = \lim_{n \to \infty} p(i, n)$ в соответствии с определением перечислимости снизу. Без ограничения общности можно считать, что все $p(i, n)$ неотрицательны (заменим отрицательные на нуль), и что для каждого $n$ лишь конечное число значений $p(i, n)$ отличны от нуля (положим $p(i, n) = 0$ при $i > n$). Будем откладывать от нуля слева направо отрезки, помечая каждый натуральным числом. При этом мы хотим, чтобы к $n$-му шагу суммарная длина всех отрезков, помеченных числом $i$, равнялась $p(i, n)$. Поэтому при увеличении $n$ на единицу мы смотрим, насколько увеличились значения $p(i, n)$ при разных $i$, и добавляем отрезки недостающего размера с нужными пометками.

За пределы отрезка $[0, 1]$ мы не выйдем, поскольку $p(i, n) \le p_i$ и $\sum p_i \le 1$.

Вероятностная машина действует следующим образом: мы останавливаемся с выходом $i$, если полученные к данному моменту случайные биты $b_0 b_1 \dots b_k$ тако- вы, что отрезок на действительной прямой, состоящий из чисел, двоичные записи которых начинаются на $b_0 b_1 \dots b_k$, целиком содержится во внутренности одного из отрезков, помеченного числом $i$. (Внутренность отрезка $[u, v]$ есть интервал $(u, v]$.) Легко проверить, что выход $i$ появится тогда и только тогда, когда $\beta$ принадле- жит внутренности одного из отрезков, помеченных числом $i$, а общая мера этого множества (объединения соответствующих интервалов) равна как раз $p_i$. ►

Будем называть **перечислимой снизу полумерой** на $\mathbb{N}$ любую последователь-ность чисел $p_i$, обладающую указанными в теореме свойствами. (Иногда мы будем также писать $p(i)$ вместо $p_i$.) Таким образом, у нас есть два определения перечи-слимых снизу полумер: (1) распределения вероятностей на выходах вероятностных машин; (2) перечислимые снизу ряды с неотрицательными членами и суммой не больше 1. Только что доказанная теорема утверждает, что эти два определения эквиваленты.

Слово «полумера» выглядит довольно странно (особенно учитывая обиходное выражение «ограничиться полумерами»), но другого употребительного термина нет. Если не требовать перечислимости, можно назвать **полумерой** на $\mathbb{N}$ любую функцию $i \mapsto p_i$, для которой $\sum_i p_i \le 1$. Такие функции можно рассматривать как распределения вероятностей на множестве $\mathbb{N} \cup \{\perp\}$, где $\perp$ — специальный символ «неопределённости». При этом вероятность числа $i$ есть $p_i$, а вероятность $\perp$ есть $1 - \sum_i p_i$. Но мы будем рассматривать лишь перечислимые снизу полумеры (если обратное не оговорено явно).

Мы определяли (перечислимые снизу) полумеры на множестве натуральных чисел. Но эти определения без всяких изменений переносятся и на двоичные слова (или любые другие конструктивные объекты). Например, если мы рассмотрим вероятностную машину, выходами которой являются двоичные слова, то она задаёт некоторую перечислимую снизу полумеру на множестве двоичных слов.
Важное замечание: в главе 5 мы будем рассматривать другое понятие полумеры на пространстве конечных и бесконечных двоичных последовательностей. Это понятие будет соответствовать машинам, которые порождают выход бит за битом и не обязаны останавливаться. Но пока что появление на выходе слова х означает, что машина напечатала все биты слова х и остановилась, так что двоичные слова ничем не отличаются в этом смысле от натуральных чисел.

Чтобы подчеркнуть различие между этими определениями, мы будем называть полумеры из этого раздела дискретными, в отличие от непрерывных полумер, или полумер на дереве, которые мы рассматриваем в главе 5.

### 4.2. Наибольшая полумера

Будем сравнивать полумеры на $N$ с точностью до мультипликативной константы. Назовём перечислимую снизу полумеру $M$ максимальной, или наибольшей, если для любой другой перечислимой снизу полумеры $m'$ выполнено равенство $m'(i) \le cm(i)$ для некоторого $c$ и для всех $i$. (Термин «наибольшая» более точен, поскольку речь идёт именно о наибольших элементах в некотором частично упорядоченном множестве, но чаще говорят о максимальной перечислимой полумере.) Иногда используется термин «универсальная полумера».

**Теорема 47.** Существует наибольшая перечислимая снизу полумера на $N$.

◀ Мы должны построить вероятностную машину $M$ с таким свойством: для любого другой машины $M'$ вероятность появления произвольного числа $i$ на выходе машины $M$ меньше такой же вероятности для $M'$ не более чем в константу раз.

Этого можно добиться так: пусть машина $M$ сначала случайно выберет вероятностную машину (вероятности выбрать ту или иную машину могут быть любыми, важно только, чтобы всякая вероятностная машина появлялась с положительной вероятностью), а потом моделирует выбранную машину. Если вероятность того, что машина $M'$ будет выбрана, равна $p$, то вероятность $m(i)$ появления $i$ на выходе машины $M$ не меньше $p \cdot m'(i)$, где $m'(i)$ — вероятность появления $i$ на выходе машины $M'$. Поэтому можно положить $c = 1/p$.

Случайный выбор можно реализовать, например, так. Перенумеруем все машины каким-либо естественным образом; получится последовательность $M_0, M_1, M_2, \dots$, включающая все вероятностные машины. Машина $M$ бросает монету, ожидая появления первой единицы. Далее она моделирует работу машины $M_i$, где $i$ — число нулей перед первой единицей. ►

Для сравнения проведём параллельно доказательство этой теоремы на языке перечислимых снизу рядов. Мы должны доказать, грубо говоря, что существует «самый плохо сходящийся» перечислимый снизу ряд, члены которого мажорируют (с точностью до умножения на константу) любой другой сходящийся перечислимый снизу ряд. (Точнее говоря, нас интересуют не просто сходящиеся ряды, а ряды с суммой не больше единицы, но это не имеет значения, так как всё равно мы разрешаем умножение на константу.)
Идея доказательства проста: возьмём все перечислимые снизу ряды с неотрицательными членами и суммой не больше 1, и сложим их с коэффициентами, которые образуют сходящийся ряд. Суммарный ряд, очевидно, будет наибольшим (с точностью до умножения на константу). Вопрос только в том, как сделать, чтобы получился перечислимый снизу ряд.

Произвольная перечислимая снизу полумера задаётся вычислимой функцией $p: \langle i, n \rangle \mapsto p(i, n)$. Таких функций счётное число (поскольку алгоритмов счётное число). Расположим их в последовательность $p^{(0)}, p^{(1)}, p^{(2)}, \dots$ и рассмотрим функцию

$$p(i, n) = \sum_{k=0}^{n} \lambda_k p^{(k)}(i, n),$$

где $\lambda_k$ — вычислимая последовательность рациональных чисел с $\sum_k \lambda_k \le 1$ (на пример, $\lambda_k = 2^{-k-1}$). Определённая таким образом функция $p$ возрастает с ростом $n$ (при фиксированном $i$), поскольку сумма включает всё больше членов и сами члены растут. При этом

$$\lim_{n \to \infty} p(i, n) = \sum_k \lambda_k \lim_{n \to \infty} p^{(k)}(i, n)$$

для любого $i$, то есть построенная полумера есть действительно сумма всех полумер с коэффициентами $\lambda_k$.

Это рассуждение, однако, содержит пробел. Проблема в том, что функция $p(i, n)$ должна быть вычислимой. Поэтому недостаточно просто расположить функции, задающие полумеры, в последовательность, нужно ещё, чтобы эта последовательность была вычислимой (как функция трёх аргументов). Мы не можем просто написать подряд все программы и сказать, что $p^{(k)}$ — это функция, вычисляющая $k$-й программой (для функций двух натуральных аргументов с рациональными значениями). Может случиться, что $k$-я программа не задаёт перечислимую снизу полумеру (вычисляет не всюду определённую функцию, или эта функция не монотонна по второму аргументу, или сумма пределов больше единицы).

Положение спасает такая

**Лемма.** Всякую программу $P$ для функции двух натуральных аргументов с неотрицательными рациональными значениями можно алгоритмически преобразовать в программу $P'$, которая вычисляет всюду определённую функцию того же типа, задающую некоторую перечислимую снизу полумеру. При этом, если сама программа $P$ задавала полумеру, то новая полумера (соответствующая $P'$) равна старой.

**Доказательство.** Пусть $P$ — данная нам программа (не обязательно всюду определённая). Для начала положим $P'(i, n)$ равным максимальному из неотрицательных чисел, которые получаются за $n$ шагов при вычислении значений $P(i, 0), \dots, P(i, n)$ (если за $n$ шагов ни одно из вычислений не даёт результата или все результаты отрицательны, то $P'(i, n) = 0$). Это уже гарантирует всюду-определённость $P'$, а также неотрицательность и монотонность по второму аргументу. При этом, если (для данного $i$) значения $P(i, n)$ определены при всех $n$, неотрицательны и не убывают по $n$, то $\lim_n P'(i, n) = \lim_n P(i, n)$.
Нам ещё нужно, чтобы $\sum p_i' \le 1$, где $p_i' = \lim_n P'(i, n)$. Для начала заметим, что можно полагать $P'(i, n)$ равным нулю при всех $n < i$. (Ясно, что такое преобразование не нарушит монотонности и не изменит предела $\lim_n P'(i, n)$.) Сумма $P'(i, n)$ по всем $i$ при фиксированном $n$ теперь будет конечной, и её можно вычислить. Нам нужно, чтобы эта сумма не превосходила единицы. Чтобы этого добиться, принудительно скорректируем $P'$: перестанем увеличивать $P'$ с ростом $n$, как только такое увеличение сделает сумму слишком большой. (Сперва мы корректируем все значения при $n=0$, потом при $n=1$ и так далее.) Лемма доказана.

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

Фиксируем некоторую наибольшую перечислимую снизу полумеру, которую будем обозначать $m$. Значение $m(i)$ этой полумеры на числе $i$ мы будем называть априорной вероятностью числа $i$. Смысл слов «априорная вероятность» такой. Пусть имеется некоторое устройство — чёрный ящик, при включении которого на выходе может появиться (через некоторое время) некоторое натуральное число. Не зная ничего об устройстве ящика, мы хотим до его включения (а priori, как сказали бы философы) оценить сверху вероятность появления на выходе числа $i$. Так вот, если ящик считать вероятностной машиной, а в качестве оценки выбрать число $m(i)$, то мы не сильно занимим оценку (максимум — в константу раз).

Как мы увидим, априорная вероятность числа $i$ тесно связана с его сложностью. Грубо говоря, она тем больше, чем число проще. Это утверждение имеет вполне точный смысл: мы вскоре покажем, что несколько модифицированная сложность (так называемая «префиксная» сложность) числа $i$ равна $-\log m(i)$.

## 4.3. Префиксные машины

Префиксная сложность отличается от обычной тем, что мы рассматриваем «самоограниченные описания»: декодирующей машине не сообщается, где кончается описание, а она решает это сама. Эту идею можно уточнять разными (и не эквивалентными) способами. Мы обсудим их подробно далее, а сейчас приведём формальные определения.

Пусть $f$ — функция, аргументами которой являются двоичные слова. Будем говорить, что функция $f$ является префиксно корректной, если выполнено такое свойство:

$$ (f(x) \text{ определено}) \text{ и } (x \text{ — начало } y) \Rightarrow f(y) \text{ определено и равно } f(x). $$

**Теорема 48.** Среди префиксно корректных способов описания имеется оптимальный.

◀ Напомним, что способом описания мы называем вычислимую функцию, аргументами и значениями которой являются двоичные слова. Теперь мы рассматриваем не все такие функции, как раньше, а лишь префиксно корректные, и сравниваем соответствующие меры сложности (сложность по-прежнему определяется как длина
кратчайшего описания). Теорема утверждает, что в классе префиксно корректных способов описания имеется оптимальный для этого класса способ *D*; оптимальность означает, что для любого префиксно корректного способа *D'* имеет место неравенство $\text{KP}_D(x) \le \text{KP}_{D'}(x) + O(1)$.

Здесь мы пишем $\text{KP}$ вместо $\text{KS}$, чтобы подчеркнуть, что мы рассматриваем только префиксно корректные способы описания, хотя для данного способа $\text{D}$ определение $\text{KP}_D(x)$ ничем не отличается от $\text{KS}_D(x)$.

Раньше (для обычной сложности) оптимальный способ описания строился так:

$$D(\hat{p}y) = p(y),$$

где $\hat{p}$ — какой-либо беспрефиксный код слова $p$ (например, $\hat{p} = \bar{p}01$, где в $\bar{p}$ удвоен каждый бит слова $p$), а $p(y)$ — результат применения программы $p$ к входу $y$ (слово $p$ понимается как программа в некотором универсальном языке программирования).

Будет ли $\text{D}$ префиксно корректным? Легко понять, что нет, поскольку среди программ $p$ есть всякие, в том числе и не префиксно корректные. Если какая-то программа $p$ некорректна и, скажем, $p(0) = a$ и $p(00) = b$ при $a \ne b$, то $D(\hat{p}0) = a$ и $D(\hat{p}00) = b$, что противоречит требованию корректности для $\text{D}$.

Поэтому мы принудительно «скорректируем» программы и вместо $p(y)$ будем рассматривать $[p](y)$, определяемое так:

(1) Параллельно применяем программу $p$ ко всех словам. Как только какое-то вычисление заканчивается, мы выписываем его аргумент и результат. Получаем последовательность пар $(y_i, z_i)$, у которых $z_i = p(y_i)$.

(2) Эта последовательность прореживается с учётом требования корректности. Удобно использовать такую терминологию: слова $y$ и $y'$ совместны, если одно из них является началом другого (равносильная формулировка: если оба они являются началом некоторого третьего слова). Прореживание состоит в следующем: если какая-то пара $(y_i, z_i)$ противоречит одной из предыдущих пар $(y_j, z_j)$ при $j < i$, то она выбрасывается. Слово «противоречит» означает, что $y_i$ совместно с $y_j$, но $z_i \ne z_j$. (Заметим, что можно было бы сравнивать очередную пару только с невыброшенными парами $(y_j, z_j)$, но это не важно.)

(3) Все эти построения не зависят от входа $y$. Вычисляя $[p](y)$, мы ожидаем появления (невыброшенной) пары $(y_i, z_i)$, у которой $y_i$ является началом $y$. Как только такая пара появляется, мы выдаём результат $z_i$ в качестве $[p](y)$.

Легко понять, что какова бы ни была программа $p$, функция $y \mapsto [p](y)$ является префиксно корректной. В самом деле, пусть $[p](y) = z$. Это значит, что в «прореженной» последовательности встретилась пара $(y_i, z_i)$, где $y_i$ является началом слова $y$. Пусть теперь $y$ является началом слова $y'$. При вычислении $[p](y')$ мы также можем воспользоваться парой $(y_i, z_i)$. Более ранние (невыброшенные) пары $(y_j, z_j)$ нам либо не подойдут (если $y_j$ не совместно с $y_i$, то $y_j$ не может быть началом слова $y'$), либо дадут тот же результат (если $y_j$ совместно с $y_i$, то $z_i = z_j$).

Если программа $p$ с самого начала была префиксно корректной, то её корректировка ничего не меняет, то есть $[p](y) = p(y)$ при всех $y$. В самом деле, выброшенных пар не будет, и значение $[p](y)$ совпадёт со значением $p$ на самом слове $y$ или на каком-то его начале (что одно и то же в силу корректности $p$).
Осталось проверить, что построенный способ описания D является префиксно корректным и оптимальным (в классе префиксно корректных).

В самом деле, мы должны сравнить $D(\hat{p}_1 y_1)$ и $D(\hat{p}_2 y_2)$ в случае, когда $\hat{p}_1 y_1$ является началом $\hat{p}_2 y_2$. В этом случае $\hat{p}_1$ и $\hat{p}_2$ (будучи началами слова $\hat{p}_2 y_2$) совместны, и по свойствам беспрефиксного кодирования $p_1 = p_2$. Следовательно, $y_1$ есть начало $y_2$, и можно воспользоваться корректностью $[p_1]$ (или, что то же самое, $[p_2]$).

Корректность D доказана. Оптимальность вытекает из того, что $[p](y) = p(y)$ для корректного $p$, и потому переход от произвольного корректного $D'$ (с программой $p$) к $D$ увеличивает сложность не более чем на длину слова $\hat{p}$. ►

Фиксировав произвольным образом оптимальный префиксно корректный способ описания, мы опускаем индекс и говорим о **префиксной сложности** $KP(x)$ слова $x$. Как обычно, надо иметь в виду, что замена способа описания приводит к изменению функции сложности (но только на ограниченное слагаемое).

Существует и другой вариант определения префиксной сложности, в котором требование корректности заменяется на другое. Будем называть функцию, аргументами которой являются двоичные слова, **беспрефиксной**, если никакие два слова в её области определения не сравнимы. Если беспрефиксная функция определена на каком-то слове, то она уже не может быть определена ни на его началах, ни на его продолжениях.

Будем рассматривать теперь только беспрефиксные способы описания, то есть беспрефиксные вычислимые функции, аргументами и значениями которых являются двоичные слова. Для них справедлива теорема, аналогичная теореме 48:

**Теорема 49.** Среди беспрефиксных способов описания имеется оптимальный.

◀ Доказательство следует той же схеме, но «корректировать» программы следует иначе. Для каждой программы $p$ построим беспрефиксную функцию $y \mapsto \{p\}(y)$ следующим образом:

(1) Как и раньше, параллельно применяем $p$ ко всем входам, получая последовательность пар $(y_i, z_i)$, у которых $z_i = p(y_i)$.

(2) Эта последовательность прореживается: если в какой-то паре $(y_i, z_i)$ слово $y_i$ совместно с каким-то из предыдущих $y_j$ (при $j < i$), то эта пара выбрасывается.

(3) Далее, имея вход $y$, мы ожидаем появления (невыброшенной) пары $(y_i, z_i)$ с первым членом $y_i = y$. Второй член этой пары и будет $\{p\}(y)$.

Легко проверить, что функция $y \mapsto \{p\}(y)$ является беспрефиксной и что описанное преобразование оставляет нетронутыми беспрефиксные функции.

Далее рассуждение в точности повторяет доказательство теоремы 48. ►

<figure><img src="image_12.png" /></figure>

Теперь можно фиксировать оптимальный беспрефиксный способ описания и рассмотреть соответствующую функцию сложности (обозначим её $KP'$).

Какая же из мер сложности $KP$ и $KP'$ является «правильной»? Это скорее дело вкуса. Мы увидим вскоре (см. раздел 4.5), что на самом деле эти меры совпадают с точностью до $O(1)$ (и совпадают с минус логарифмом априорной вероятности), так что скорее следует спрашивать не о том, какая мера сложности лучше, а о том, какое определение более естественно. Это тем более вопрос вкуса. Авторам представляется, что более естественно определение с префиксно-корректными
способами описания (не зря мы его привели первым). Вместе с тем в некоторых рассуждениях (например, при доказательстве теоремы о сложности пары в разделе 4.6) использование второго определения позволяет дать простое и короткое доказательство.

(Об истории появления префиксной сложности см. [11]; отметим, что в первых русских публикациях, начиная с диссертации Левина, использовались префиксно-корректные описания, а Чейтин использовал беспрефиксные. В современной англоязычной литературе для префиксной сложности используется обозначение $K(x)$.)

Насколько свойства префиксной сложности ($KP$, $KP'$) отличаются от свойств обычной? Что из ранее известных свойств остаётся в силе?

* Прежде всего отметим очевидное свойство:

$$KS(x) \le KP(x) + O(1) \quad \text{и} \quad KS(x) \le KP'(x) + O(1),$$

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

* Мы видели, что $KS(x) \le l(x) + O(1)$ (достаточно рассмотреть тождественный способ описания). Теперь это рассуждение не проходит, так как тождественный способ описания не является ни беспрефиксным, ни префиксно корректным. Как мы покажем в разделе 4.5, это не случайно: для префиксной сложности аналогичное неравенство неверно.

* Тем не менее можно дать оценки префиксной сложности в терминах длины. (Мы сделаем это для $KP'$, конструкции для $KP$ аналогичны.) Докажем, что $KP'(x) \le 2l(x) + O(1)$. В самом деле, способ описания $D$, определённый формулой

$$D(\bar{x}01) = x$$

($\bar{x}$ получается удвоением всех битов в $x$), является беспрефиксным. Выбирая более экономное беспрефиксное кодирование $\hat{x}$ вместо $\bar{x}01$, можно получить и лучшие оценки:

$$KP'(x) \le l(x) + 2 \log l(x) + O(1)$$

получится, если положить $\hat{x} = \text{bin}(l(x))01x$; итерируя эту конструкцию, получаем

$$KP'(x) \le l(x) + \log l(x) + 2 \log \log l(x) + O(1)$$

и так далее.

* Свойство невозрастания сложности при алгоритмическом преобразовании остаётся верным:

$$KP'(A(x)) \le KP'(x) + O(1)$$
(константа зависит от алгоритма А, но не от х). В самом деле, легко проверить, что если D — беспрефиксный способ описания, то композиция х ↦→ А(Д(х)) также является беспрефиксным способом описания. Заменив слово «беспрефиксный» на «префиксно корректный», получаем аналогичное утверждение для KP вместо KP'. Это свойство позволяет говорить о префиксной сложности произвольных конструктивных объектов (пар слов, натуральных чисел, конечных множеств слов и т. п.), не уточная способа их кодирования.

* Как мы увидим, неравенство для сложности пары слов с префиксной сложностью уже не требует логарифмической добавки:

$$KP(x, y) \le KP(x) + KP(y) + O(1)$$

(теорема 60 в разделе 4.6, с. 113).

* Применим свойство неврастарания сложности при алгоритмическом преобразовании, взяв в качестве А оптимальный способ описания D для обычной (не префиксной) колмогоровской сложности. Если р является кратчайшим описанием х относительно D, то D(p) = x и l(p) = KS(x), поэтому

$$ 
\begin{aligned}
KP(x) = KP(D(p)) &\le KP(p) + O(1) \le l(p) + 2 \log l(p) + O(1) = \\
&= KS(x) + 2 \log KS(x) + O(1).
\end{aligned}
$$

Мы воспользовались свойством KP(p) ≤ l(p) + 2 log l(p) + O(1), доказанным ранее; если использовать более точные оценки, то получим неравенство

$$KP(x) \le KS(x) + \log KS(x) + 2 \log \log KS(x) + O(1)$$

и аналогичные ему неравенства.

## 4.4. Отступление: машины с самоограниченным входом

Этот раздел почти не используется в дальнейшем. Мы попытаемся проанализировать идею «самоограниченного» входа и её возможные уточнения, тем самым мотивировав определения префиксно корректных и беспрефиксных способов описания.

Обычно, подавая на вход машины двоичное слово, мы указываем начало и конец этого слова. Например, при определении вычислимости на машине Тьюринга обычно предполагают, что машина изначально видит первый символ слова, а конец слова отмечен специальным указателем (им может быть, например, символ «пробел», который идёт за последним битом слова).

Говоря о самоограниченном входе, мы имеем в виду несколько другую ситуацию: машина получает биты слова один из другим (слева направо) и в некоторый момент выдаёт ответ.
### 4.4.1. Беспрефиксные функции

Вот одно из возможных уточнений. Будем считать, что у машины, помимо рабочей ленты, есть входная лента, на которой имеется односторонняя читающая головка. Крайняя левая клетка ленты содержит специальный маркер #, справа от которого записана бесконечная последовательность нулей и единиц (рис. 4.2).

<figure><img src="image_13.png" /><figcaption>Рис. 4.2. Односторонняя читающая головка на входной ленте.</figcaption></figure>

Изначально читающая головка стоит у левого края ленты (и видит специальный маркер). Поведение машины Тьюринга определяется символом, который видит читающая головка, а также (как всегда) символом, который видит головка на рабочей ленте. В зависимости от этих символов и текущего состояния машина предпринимает то или иное действие. Это действие состоит в изменении внутреннего состояния, записи нового символа на рабочей ленте, а также может включаться в себя сдвиг на рабочей ленте и сдвиг вправо читающей головки. Результат работы машины обычным образом записывается на рабочей ленте (изначально пустой).

Пусть $M$ — такая машина. Будем запускать её на всевозможных входных лентах. Как только машина останавливается, мы записываем два слова: ту часть входной ленты, которую она успела прочесть (слово $x$), и результат работы ($y$). Множество полученных таким образом пар $(x, y)$ обозначим $\Gamma_M$. Если две различные пары $(x_1, y_1)$ и $(x_2, y_2)$ принадлежат $\Gamma_M$, то слова $x_1$ и $x_2$ несравнимы. В самом деле, если $x_1$ является началом $x_2$, то вычисление с $x_2$ на входе должно протекать так же, как и вычисление с $x_1$ (поскольку символы на входе те же) и вместе с ним должно закончиться. Поэтому $y_1 = y_2$, а если $x_1 \neq x_2$, то часть слова $x_2$ останется непрочитанной, что противоречит определению множества $\Gamma_M$.

В частности, первые члены всех пар из $\Gamma_M$ различны, поэтому $\Gamma_M$ задаёт некоторую функцию $\gamma_M$, аргументами и значениями которой являются двоичные слова. Будем говорить, что машина $M$ беспрефиксно вычисляет эту функцию. Легко понять, что функция $\gamma_M$ вычислима в обычном смысле: чтобы вычислить $\gamma_M(x)$, надо запустить $M$ на $x$ и после остановки дополнительно проверить, что головка на входной ленте дошла до конца слова $x$, но не вышла за его пределы. Ясно также, что функция $\gamma_M$ является беспрефиксной (любые два слова из её области определения несравнимы). Верно и обратное утверждение:

**Теорема 50.** Любая беспрефиксная вычислимая функция беспрефиксно вычислима некоторой машиной.

◀ Это утверждение вовсе не самоочевидно, поскольку машина $F$, вычисляющая (в обычном смысле) некоторую беспрефиксную функцию $f$, знает, где кончается вход, и может использовать эту информацию. Тем не менее оно верно: если
функция $f$ беспрефиксная, мы можем построить другую машину $M$, для которой $\gamma_M = f$.

Это делается следующим образом. Машина $M$ на рабочей ленте параллельно моделирует вычисления машины $F$ на всех аргументах, время от времени читая очередные символы на входной ленте (когда именно это нужно делать, описано ниже). При появлении новой пары слов $x, y$, для которых $f(x) = y$, мы сравниваем $x$ с уже прочитанной частью входа (вначале она пуста). Если прочитанная часть входа не является началом $x$, то мы не делаем ничего (и продолжаем порождать пары слов). Если прочитанная часть совпадает с $x$, то мы останавливаемся и выдаём на вход $y$. Если же прочитанная часть является собственным началом слова $x$, то мы читаем следующий бит входа и повторяем сравнение — до тех пор, пока мы не прочтём на входе либо само слово $x$ (в этом случае $M$ останавливается с выходом $y$), либо какое-то слово, не являющееся началом слова $x$. На этом обработка пары $\langle x, y \rangle$ заканчивается, и мы ждём появления следующей пары.

Как выглядит этот процесс вычисления? Вначале на входе не прочитано ничего. Когда появляется первая пара $\langle x, y \rangle$, мы смотрим, пусто ли $x$. Если да, то (так ничего и не прочтя на входе) печатаем на выходе $y$ и останавливаемся. Если нет, то читаем вход до тех пор, пока либо не прочтём всё $x$, либо не отклонимся от $x$ (то есть прочтём кусок входа, который не является началом слова $x$). В первом случае мы печатаем на выходе $y$ и останавливаемся, во втором заканчиваем обработку пары $\langle x, y \rangle$ и ждём появления следующей пары.

Формально говоря, инвариант, который выполнен после обработки нескольких пар, таков (обозначим прочитанную часть входа через $r$): либо

(1) $f(r)$ определено, машина закончила работу и выдала на выход $f(r)$, либо

(2) $r$ не является началом слова $x$ ни для какой из обнаруженных пар $\langle x, y \rangle$, но всякое собственное начало $r'$ слова $r$ является собственным началом одного из таких слов. (Собственное начало — это начало, не совпадающее со всем словом.)

Используя этот инвариант, легко завершить формальную проверку, но мы вместо этого подчеркнём основную идею: если мы уже прочли некоторое слово $r$, и выяснилось, что функция $f$ определена на некотором собственном продолжении слова $r$, то заведомо $f(r)$ не определено, и потому можно прочесть следующий бит входа, не опасаясь прочесть лишнее. ►

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

$b := NextBit$

При выполнении этого оператора работа программы приостанавливается, на экране появляется надпись «Введите следующий бит». Когда клиент это делает (скажем, нажав клавишу «0» или «1»), соответствующий бит помещается в переменную $b$, и работа программы продолжается.

Каждой такой программы соответствует функция: её аргумент $x$ бит за битом сообщается программе в ответ на её запросы; значение равно $y$, если программа напечатала $y$ и остановилась, при этом запросив все биты слова $x$ и только их.
(Если она запросила следующий бит, прочтя всё слово х, или недоузнала биты этого слова, то х не входит в область определения функции.)

Адаптируя приведённые выше рассуждения, легко показать, что функции, соответствующие таким программам — это в точности вычислимые беспрефиксные функции. (Сдвиг головки на входной ленте в точности соответствует запросу следующего бита.)

### 4.4.2. Префиксно корректные функции

Есть и другая, более привычная схема работы программы, получающей свой вход бит за битом (причём конец входа никак не отмечается). Будем считать, что клиент набирает входное слово, не дожидаясь запросов, нажимая на клавиатуре клавиши «0» и «1» (и никак не обозначая конец входа). Нажатые им клавиши запоминаются и поступают в программу по требованию.

Очередной бит считается командой

`b := NextBit`

Помимо неё, есть команда

`b := NextExists`

Она позволяет выяснить, имеется ли в очереди нажатых клавиш ещё не прочитанная. Следует уточнить также, что происходит, если при выполнении команды `NextBit` очередь нажатых клавиш пуста. Можно считать, что это ведёт к аварии, а можно считать, что работа всего лишь приостанавливается до появления следующего бита (нажатия следующей клавиши). Какой из этих вариантов выбрать, не имеет значения, поскольку можно дожидаться появления входного бита, прежде чем его считать. Для этого нужно написать что-то вроде

```pascal
while not NextExists do {nothing};
b := NextBit
```

Программисты бы назвали описываемый в этом разделе механизм доступа к входу «неблокирующим» чтением в отличие от ранее рассмотренного «блокирующего». Неблокирующее чтение позволяет программе продолжать внутреннюю работу, одновременно следя за входом и ожидая появления там нового символа.

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

Назовём программу корректной, если для неё результат работы не зависит от моментов нажатия клавиши: для данного входного слова х либо работа программы не заканчивается, в какие моменты его ни подавай, либо всегда заканчивается с одним и тем же результатом.

Каждой корректной программе соответствует частичная функция (авансимость выхода от входа).

**Теорема 51.** (а) Эта функция вычислима и является префиксно корректной. (б) Любая префиксно корректная вычислимая функция соответствует некоторой корректной программе.
◀ (а) Вычислимость функции очевидна: если есть программа, вычисляющая её в описанном режиме (вход подаётся по частям), то есть и программа, вычисляющая её в обычном смысле. Проверим префиксную корректность. По определению (раздел 4.3) мы должны доказать, что если корректная программа выдаёт выход у на входе х, то она даёт тот же выход и для входа х', являющегося продолжением входа х. В самом деле, проследим за работой программы на входе х. По предположению она напечатает у и остановится. В самый последний момент, когда машина уже всё сделала и собирается остановиться, добавим к входу х недостающий до х' кусок. Это уже не повлияет на работу программы, и она по-прежнему напечатает у при входе х'. В силу корректности программа будет печатать слово у при любом другом выборе моментов нажатия клавиш для букв из х'.

(Замечание в скобках: на самом деле спешка тут нужна лишь для наглядности, ведь мы можем нажать оставшиеся клавиши и после завершения работы программы, определение этого не запрещает.)

(б) Покажем, что для любой префиксно корректной вычислимой функции можно построить соответствующую программу. Пусть $f$ — такая функция.

Корректная программа действует следующим образом. Она параллельно применяет $f$ ко всем словам, а также регулярно проверяет, не поступил ли на вход новый символ (и считает его). Если выяснится, что $f(x) = y$ для некоторых $x$ и $y$, причём текущее слово на входе равно $x$ или некоторому продолжению слова $x$, то на выход выдаётся $y$ и работа завершается.

Если $f(x) = y$, то эта программа выдаст $y$, в какие моменты не подавай биты слова $x$ на вход. В самом деле, если подождать достаточно долго, то слово $x$ будет подано целиком, а моделирование $f(x)$ завершится. В этот момент машина остановится и выдаст $y$, если она не остановилась раньше. А раньше она могла остановиться, если $f(x')$ оказалось определённым для некоторого начала $x'$ входной последовательности. Но тогда $x'$ является началом $x$ и $f(x')$ должно равняться тому же слову $y$, поскольку функция $f$ префиксно корректна по предположению. Поэтому на ответ это не повлияет.

С другой стороны, если $f(x)$ не определено, а функция $f$ префиксно корректна, то $f(x')$ не определено и для всех начал слова $x$, поэтому работа машины не закончится. ►

Эта теорема показывает, что корректным машинам с неблокирующим чтением соответствуют вычислимые префиксно корректные функции и только они, тем самым мотивируя определение префиксно корректной функции.

**96** Докажите, что существует алгоритм, преобразующий любую программу $p$ описанного вида (с командами NextBit и NextExists) в другую программу $p'$ того же вида, причём $p'$ всегда корректна и вычисляет ту же функцию, что и $p$, если программа $p$ корректна. [Указание. Воспользуйтесь конструкцией из доказательства теоремы 51 в обе стороны.]

**97** (Продолжение.) Докажите, что тем не менее не существует алгоритма, который по заданной программе $p$ проверял бы, является ли она корректной. [Указание. Это делается обычным для теории вычислимых функций способом: сведением проблемы остановки. См., например, [175].]
### 4.4.3. Непрерывные вычислимые отображения

Существует и другая, более абстрактная мотивировка понятия префиксно корректной функции. Она исходит из общей схемы определения вычислимости для объектов высших типов, но мы изложим её применительно к конкретной ситуации (уже и так этот раздел — предназначенный дотошным читателям! — чрезмерно скучен). Коротко говоря, префиксно корректные функции соответствуют вычислимым непрерывным отображениям битовых последовательностей в натуральные числа с дополнительным элементом «неопределённость». Сейчас мы объясним, что имеется в виду.

Рассмотрим множество Σ конечных и бесконечных двоичных последовательностей: Σ = Ξ ∪ Ω. Для каждого (конечного) слова x рассмотрим множество Σₓ его конечных и бесконечных продолжений. Введём на Σ частичный порядок, считая, что x ≤ y, если у является продолжением x.

Введём на множестве Σ топологию, считая базовыми открытыми множествами множества Σₓ (это значит, что открытыми множествами считаются всевозможные объединения множеств вида Σₓ). Легко проверить, что это действительно топология (не обладающая свойством отделимости).

Имеет место следующий (почти очевидный) факт:

**Теорема 52.** Множество $A \subset \Sigma$ открыто в этой топологии тогда и только тогда, когда оно обладает двумя свойствами:

(1) вместе с каждым двоичным словом оно содержит все его (конечные или бесконечные) продолжения;

(2) если бесконечная последовательность принадлежит A, то некоторое её конечное начало также принадлежит A.

▲ Объединение базовых открытых множеств очевидно обладает свойствами (1) и (2). С другой стороны, если A обладает этими свойствами, то оно является объединением множеств Σₓ по всем (конечным) словам x, принадлежащим A. ►

Теперь введём топологию на множестве $N_⊥$ натуральных чисел с добавленным к нему элементом $⊥$ (неопределённость). На этом множестве также полезно ввести частичный порядок, считая, что $⊥$ меньше всех остальных элементов, а между собой они несравнимы (рис. 4.3).

<figure><img src="image_14.png" /><figcaption>Рис. 4.3. Топологическое пространство $N_⊥$.</figcaption></figure>

Будем считать открытыми любые множества, не содержащие элемента $⊥$, а также всё пространство $N \cup \{⊥\}$. (Легко проверить, что аксиомы топологического пространства выполнены; пространство это также не является отделимым.)
Частичные функции из $Σ$ в $N$ отождествим с отображениями вида $Σ \to N_⊥$, определёнными на всёём $Σ$ (значение $⊥$ соответствует неопределённым значениям функции). Легко описать класс непрерывных отображений (напомним, что отображение называется непрерывным, если прообраз любого открытого множества открыт):

**Теорема 53.** Отображение $F: Σ \to N_⊥$ непрерывно тогда и только тогда, когда выполнены два условия:

(1) $F$ монотонно (если $x \le y$, то $F(x) \le F(y)$ в смысле введённых на $Σ$ и $N_⊥$ порядков);

(2) Если $F(x) \neq \perp$ для бесконечной последовательности $x$, то $F(x') \neq \perp$ для некоторого конечного начала $x' \le x$.

Пусть $F$ непрерывно. Проверим условие (1). Пусть $x \le y$. Если $F(x) \not\le F(y)$, то $F(x)$ есть натуральное число (а не $⊥$) и $F(x) \neq F(y)$. Тогда прообраз открытого множества $\{F(x)\}$ содержит $x$, но не содержит $y$ и потому не является открытым.

Проверим условие (2). Если $F(x) \neq \perp$ для бесконечной последовательности $x$, то открытый прообраз открытого множества $\{F(x)\}$ содержит $x$ и потому должен содержать некоторое конечное начало последовательности $x$.

Осталось проверить, что если для $F$ выполнены условия (1) и (2), то отображение $F$ непрерывно. Достаточно проверить, что прообраз каждого натурального числа открыт (прообраз всего пространства открыт, а остальные открытые множества состоят из натуральных чисел). Для этого достаточно проверить условия (1) и (2) предыдущей теоремы, которые прямо следуют из предположения. (Заметим, что если $x'$ есть начало $x$ и $F(x') \neq \perp$, то $F(x') = F(x)$ в силу монотонности.) ►

С каждым непрерывным отображением $F: Σ \to N_⊥$ свяжем множество $Γ_F$ всех пар $(x, n) \in Ξ \times N$, для которых $F(x) = n$. Заметим, что множество $Γ_F$ является лишь частью графика отображения $F$ (мы рассматриваем лишь конечные слова $x$ и не разрешаем элементу $⊥$ быть вторым членом пары.)

**Теорема 54.** Соответствие $F \mapsto Γ_F$ является взаимно однозначным соответствием между непрерывными отображениями $Σ \to N_⊥$ и множествами $A \subset \subset Ξ \times N$, обладающими двумя свойствами:

(1) $\langle x, n \rangle \in A, x \le y \Rightarrow \langle y, n \rangle \in A;$

(2) $\langle x, n \rangle \in A, \langle x, m \rangle \in A \Rightarrow m = n.$

Пусть отображение $F$ непрерывно. Если $F(x) = n \in N$, то условие (1) предыдущей теоремы гарантирует, что $F(y) = n$ для любого слова $y$, продолжающего $x$. Тем самым условие (1) выполнено для множества $Γ_F$. Выполнено и условие (2), поскольку $F(x)$ не может быть равно двум разным натуральным числам одновременно. Таким образом, для любого непрерывного $F$ множество $Γ_F$ обладает свойствами (1) и (2).

Легко видеть, что $Γ_F$ однозначно определяет $F$: чтобы найти $F(x)$ для конечного $x$, мы ищем пару $\langle x, n \rangle \in Γ_F$. Если такой пары нет, то $F(x) = \perp$. Для бесконечного $x$ значение $F(x)$ однозначно определяется по непрерывности.

Осталось показать, что любое множество $A$, обладающее свойствами (1) и (2), равно $Γ_F$ при некотором $F$. В самом деле, определим $F(x)$ при конечном $x$ как то
единственное $n$, для которого $\langle x, n \rangle \in A$ (свойство (2) гарантирует единственность) или как $\perp$, если такого $n$ не существует. Свойство (1) гарантирует, что построенная таким образом функция (определённая на конечных словах) монотонна. Осталось доопределить её на бесконечных словах. Для бесконечного $x \in \Sigma$ положим $F(x)$ равным $F(x')$, если найдётся конечное $x' \le x$, для которого $F(x') \ne \perp$; если такого $x'$ не найдётся, то $F(x) = \perp$. Корректность определения (независимость $F(x)$ от выбора $x' \le x$) гарантируется свойством (1). Очевидно, построенная таким образом функция $F$ обладает свойствами (1) и (2) предыдущей теоремы и потому непрерывна. Столь же очевидно, что $\Gamma_F = A$. ►

Легко понять, что свойства (1) и (2) последней теоремы означают, что $A$ представляет собой график префиксно корректной функции. Тем самым мы получаем взаимно однозначное соответствие между непрерывными отображениями $\Sigma \to \mathbb{N}_\perp$ и префиксно корректными функциями.

Назовём непрерывное отображение $F: \Sigma \to \mathbb{N}_\perp$ вычислимым, если множество $\Gamma_F$ перечислимо. Легко проверить, что это равносильно вычислимости соответствующей частичной функции из $\Xi$ в $\mathbb{N}$. (Частичная функция из $\Xi$ в $\mathbb{N}$ вычислима тогда и только тогда, когда её график перечислим.) Поэтому вычислимые отображения типа $\Sigma \to \mathbb{N}_\perp$ соответствуют вычислимым префиксно корректным функциям, что и является обещанной дополнительной мотивировкой понятия префиксно корректной функции.

### 4.5. Основная теорема о префиксной сложности

В этом разделе мы докажем, что три меры сложности — два варианта префиксной сложности ($KP$ с префиксно корректными способами описания и $KP'$ с беспрефиксными), а также минус логарифм априорной вероятности совпадают с точностью до $O(1)$. Для этого мы докажем три неравенства в цепочке

$$-\log m(x) \le KP(x) \le KP'(x) \le -\log m(x)$$

(с точностью до $O(1)$). Начнём с двух простых неравенств.

**Теорема 55.**

$$KP(x) \le KP'(x) + O(1).$$

◀ Неравенство было бы очевидным, если бы всякий беспрефиксный способ описания был бы префиксно корректным. Однако это не так: если беспрефиксный способ $D$ определён на каком-то слове $u$, то он не определён ни на каком продолжении слова $u$ (в то время как префиксно корректный способ описания должен быть определён на всех продолжениях и иметь то же значение).

Поэтому требуется чуть более сложная конструкция. Пусть $D$ — беспрефиксный способ описания. Построим новый способ описания $D'$. Если $D$ был определён на некотором слове $u$ и принимал на нём значение $x$, то мы положим $D'$ равным $x$ на всех продолжениях слова $u$. Другими словами, чтобы вычислить $D'(u)$, мы применяем $D$ ко всем началам слова $u$. Лишь одно из значений $D(u')$ (где $u' =$ начало слова $u$) может быть определённым (в силу беспрефиксности). Как только
такое у' найдётся, мы полагаем $D'(y)$ равным $D(y')$. Другими словами, $D'(y) = x$ тогда и только тогда, когда $D(y') = x$ для некоторого начала у' слова у.

Из построения видно, что функция $D'$ вычислима, префиксно корректна и является продолжением функции $D$. Поэтому сложность относительно $D'$ не превосходит сложности относительно $D$. (На самом деле сложность относительно $D'$ в точности равна сложности относительно $D$, так как кратчайшие описания остались теми же самыми.) ►

Можно пытаться доказать обратное неравенство аналогичным способом. Действительно, для каждого префиксно корректного отображения $D$ можно построить беспрефиксное отображение $D'$, сузив $D$ на «нижние точки» своей области определения (то есть положив $D'(y) = z$, если $D(y) = z$ и $D(y')$ не определено ни для какого начала у' слова у).

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

**98** Приведите пример вычислимой префиксно корректной функции, для которой соответствующая беспрефиксная функция не является вычислимой. [Указание. Пусть $A$ — перечислимое множество натуральных чисел, не являющиеся разрешимым и потому имеющее неперечислимое дополнение. Положим $f(0^n11x) = 0$ при всех $n$ и всех $x$ и $f(0^n1x) = 0$ при всех $n \in A$ и всех $x$.]

Эта задача говорит, что в некотором смысле неблокирующее чтение является более гибким средством, чем блокирующее (см. раздел 4.4).

**Теорема 56.**

$$ -\log m(x) \le KP(x) + O(1). $$

◀ Мы должны показать, что $-\log m(x) \le KP(x) + O(1)$ или что $2^{-KP(x)} \le cm(x)$ для некоторой константы $c$. В силу максимalityи полумеры $m$ достаточно показать, что функция $x \mapsto 2^{-KP(x)}$ не больше некоторой перечислимой снизу полумеры. (Здесь, говоря о полумерах, мы считаем аргументами двоичные слова, то есть рассматриваем вероятностные машины, выходом которых являются двоичные слова, см. раздел 4.1.)

Укажем эту полумеру, построив соответствующую вероятностную машину. Возьмём оптимальный префиксно корректный способ описания $D$, использованный в определении $KP$. Наша вероятностная машина (без входа) будет применять $D$ к случайной последовательности битов. Точнее говоря, $D$ применяется параллельно ко всем началам последовательности случайных битов $b_0, b_1, b_2, \dots$; как только одно из вычислений

$$ D(\Lambda), D(b_0), D(b_0 b_1), D(b_0 b_1 b_2), \dots $$

закончится, его результат и будет результатом работы машины. Заметим, что не имеет значение, какое именно из закончившихся вычислений мы возьмём (корректность гарантирует, что результат один и тот же).
Для любого слова х рассмотрим кратчайшее описание р слова х (относительно D). Тогда вероятность появления слова х как выхода вероятностной машины не меньше $2^{-l(p)}$. В самом деле, если первые $l(p)$ случайных битов совпали с р, то результат работы машины гарантированно равен х. Тем самым вероятность появления х не меньше $2^{-l(p)} = 2^{-KP(x)}$, что и требовалось. ►

Несколько другое доказательство того же результата обходится без вероятностных машин. В самом деле, мы знаем, что функция сложности перечислима сверху, поэтому функция $x \mapsto 2^{-KP(x)}$ перечислима снизу. Остаётся сослаться на следующую почти очевидную теорему:

**Теорема 57.**

$$ \sum_x 2^{-KP(x)} \le 1. $$

◀ В самом деле, пусть $p_x$ — кратчайшая программа для слова х. Тогда слова $p_x$ и $p_y$ несравнимы (при $x \ne y$). Остаётся воспользоваться такой простой леммой.

**Лемма.** Пусть $p_0, p_1, p_2, \dots$ — попарно несравнимые слова (это значит, что ни одно из них не является началом другого). Тогда $\sum_l 2^{-l(p_i)} \le 1$.

В самом деле, $2^{-l(p_i)}$ есть (равномерная бернуллиева) мера множества $\Omega_{p_i}$ всех (бесконечных) продолжений слова $p_i$. Поскольку слова $p_i$ несравнимы, множества их продолжений не пересекаются и потому меры этих множеств (вероятности получить $p_i$ в начале случайной последовательности битов) в сумме не превосходят единицы. Лемма (а с ней и теорема 57) доказана. ►

Кстати, мы заодно доказали, что для префиксной сложности не выполняется неравенство $KP(x) \le l(x) + O(1)$. В самом деле, если бы это было так, то сумма

$$ \sum_x 2^{-l(x)} $$

была бы конечной. А между тем для каждого $n$ сумма по всем $x$ длины $n$ равна единице (ибо состоит из $2^n$ членов по $2^{-n}$ каждый), и потому общая сумма бесконечна.

**99** Доказайте, что более слабая оценка $KP(x) \le l(x) + \log l(x) + O(1)$ также не имеет места (то есть что разность $KP(x) - l(x) - \log l(x)$ не ограничена). [Указание. Гармонический ряд расходится.]

Осталось доказать третье, наиболее сложное неравенство:

**Теорема 58.**

$$ KP'(x) \le -\log m(x) + O(1). $$

◀ Попытаемся вначале объяснить идею доказательства. Имеется перечислямая снизу полумера $m(x)$. Это значит, что мы постепенно узнаём всё большие и большие оценки снизу для $m(x)$. Большое значение $m(x)$ означает для нас, что $KP'(x)$ должно быть малым, то есть означает необходимость предусмотреть для х короткое описание $p$. При этом описания различных объектов должны быть несравнимыми. Несравнимость удобно представлять себе геометрически. Для каждого двоичного слова $p$ мы рассматриваем отрезок, который состоит из чисел, двоичная запись которых начинается на $p$. Таким образом, $[0, 1]$ разбивается на две половины
$I_0$ (левую) и $I_1$ (правую), которые в свою очередь делятся пополам на $I_{00}$, $I_{01}$ и $I_{10}$, $I_{11}$ и так далее. В этом представлении несравнимость слов $p_1$ и $p_2$ означает, что отрезки $I_{p_1}$ и $I_{p_2}$ не пересекаются. При этом неравенство $l(p) \le -\log_2 m(x)$ можно переписать как $2^{-l(p)} \ge m(x)$: длина отрезка $I_p$ должна быть не меньше $m(x)$.

Тем самым нашу задачу можно сформулировать так: каждому объекту $x$ нужно выделить отрезок длины не менее $m(x)$, причём отрезки, выделенные разным объектам, не должны перекрываться.

Сказанное требует уточнений. Во-первых, разрешается выделять отрезки длиной не $m(x)$, а $\varepsilon m(x)$ для некоторого фиксированного $\varepsilon$ (что соответствует аддитивной константе в исходном неравенстве). Во-вторых, нужны не произвольные отрезки, а только «регулярные» (половинки, четвертинки и другие отрезки вида $I_p$). Но с учётом первого замечания это не так важно, поскольку любой отрезок (не выходящий за пределы отрезка $[0, 1]$) содержит строго внутри себя регулярный подотрезок длиной не менее четверти исходного.

Таким образом, мы приходим почти к той же задаче, что была рассмотрена в разделе 4.1. К нам приходят клиенты с просьбами выделить им место на отрезке $[0, 1]$. По-прежнему сумма всех запросов не превосходит единицы и клиенты сообщают свои запросы постепенно (время от времени меняя их в сторону увеличения). Теперь, однако, клиентам важна не общая длина выделенных для них отрезков, а длина непрерывного участка, что усложняет задачу. В качестве компенсации мы имеем право выделять место с некоторым коэффициентом (урезать все запросы в фиксированное число раз). Но это нам не поможет, если при каждом увеличении запроса отводить новый участок — при такой стратегии никакого коэффициента не хватит. Решение проблемы: рассматривать новый запрос (выделяя новый отрезок) только, когда запрос увеличился вдвое. При этом общая сумма рассмотренных запросов не более чем вдвое превосходит последний запрос (ведь сумма геометрической прогрессии со знаменателем 2 не больше удвоенного последнего члена). С другой стороны, требования выполнены с точностью до мультипликативной константы.

Эту схему можно довести до вполне строгого доказательства. Мы, однако, изложим немного другое доказательство. Оно основано на следующей «лемме о шторах», называемой часто леммой Крафта — Чейтина (см. [23]). (Она является вычислимым аналогом леммы Крафта из теории информации, см. с. 244.)

**Лемма.** Пусть $l_0, l_1, l_2, \dots$ — вычислимая последовательность натуральных чисел, для которой

$$ \sum_i 2^{-l_i} \le 1. $$

Тогда существует вычислимая последовательность попарно несравнимых двоичных слов $x_0, x_1, x_2, \dots$, для которых $l(x_i) = l_i$.

Заметим, что указанное в лемме неравенство необходимо для существования несравнимых слов $x_i$ с длинами $l_i$, поскольку отрезки $I_{x_i}$ не перекрываются и имеют длины как раз $2^{-l_i}$. Лемма утверждает, что это необходимое условие одновременно является достаточным.

**Доказательство.** Наглядно можно сформулировать лемму так. Есть окно шириной 1 (отрезок $[0, 1]$). Нам приносят одну за другой шторы, которыми мы заня
вешиваем окно (так, чтобы они не перекрывались). При этом шторы могут иметь ширину 1, 1/2, 1/4, 1/8, ..., и вешать их можно не куда угодно, а с ограничениями. Штору размера 1 можно повесить единственным способом. Штору размера 1/2 можно вешать двумя способами (закрыв левую половину окна или закрыв правую). Для шторы размера 1/4 имеется четыре возможных положения (четыре четверти отрезка), и так далее. Выбор положения для шторы шириной $2^{-l}$ соответствует выбору слова длины $l$. Требование, чтобы шторы не перекрывались, означает, что соответствующие им слова несравнимы. Наконец, условие леммы утверждает, что суммарная ширина штор не превосходит ширины окна.

(Более компьютерная метафора: распределение памяти между процессами; каждый процесс требует $1/2^k$ доступной памяти, и требует, чтобы выделенный участок был выровнен [aligned]; память не освобождается; мы доказываем, что если сумма всех запросов не больше общего размера памяти, то их можно удовлетворить в порядке поступления, применяя описанный далее алгоритм.)

Выбор положения для очередной шторы происходит по такому алгоритму: свободная часть окна представляется в виде объединения непересекающихся «виртуальных штор», причём размеры всех виртуальных штор различны. Виртуальная штора обозначает место, которое пока свободно, но на которое потом можно будет повесить реальную штору того же размера. (Свободная память представлена в виде списка правильно выровненных блоков разного размера.)

Вначале окно свободно, и есть одна виртуальная штора ширины 1. Пусть теперь нам приносят штору ширины $w$. Если среди виртуальных штор имеется штор ширины $w$, то всё просто: изымаем её из набора и вешаем на её место реальную. Пусть это не так. Заметим, что тогда среди виртуальных штор обязательно есть штора ширины больше $w$. (В самом деле, иначе в наборе были бы только виртуальные шторы $w/2, w/4, ..., и общая ширина свободного пространства была бы меньше $w$. Напомним, что все виртуальные шторы разного размера.)

Итак, мы знаем, что есть хотя бы одна виртуальная штора ширины $w' > w$. Выберем из таких штор самую узкую (подобная стратегия при распределении памяти называется best fit). Отрежем от неё слева кусок размера $w$, а остальное разрежем на части $w, 2w, 4w, ..., w'/2$ (ведь $w+w+2w+4w+...+(w'/2)=w'$). Эти части и будут новыми виртуальными шторами. Поскольку $w'$ было выбрано минимальным, штор промежуточного размера (от $w$ до $w'/2$) раньше не было, так что наше условие (требующее, чтобы виртуальные шторы были разных размеров) продолжает выполняться. Лемма доказана.

**100** Докажите, что ту же стратегию можно описать другими словами: каждую следующую штору вешаем на самое левое из возможных мест. [Указание: описанныя в лемме конструкция сохраняет такое свойство: длины виртуальных штор возрастают слева направо.]

**Следствие.** Пусть $l_i$ — вычислимая последовательность натуральных чисел, причём $\sum_i 2^{-l_i} \le 1$. Тогда $KP'(i) \le l_i + O(1)$.

В самом деле, лемма позволяет указать последовательность несравнимых слов $x_i$ длины $l_i$. Определим способ описания $D$, положив $D(x_i) = i$. Несравнимость слов $x_i$ гарантирует, что этот способ описания будет беспрефиксным. Вычислимость
последовательности $x_i$ гарантирует вычислимость $D$ (имея вход $x$, мы сравниваем его по очереди со всеми $x_i$ до совпадения, после чего выдаём на выход $i$).

(Заметим, что мы, как и раньше, свободно переходим от натуральных чисел к словам, говоря об их сложности и априорной вероятности.)

Вернёмся к доказательству теоремы. Мы рассматриваем наибольшую (максимальную) перечислимую снизу полумеру $m$. Согласно определению перечислимости снизу,

$$m(x) = \lim_{i \to \infty} m(x, i),$$

где $m(x, i)$ — вычислимая и монотонная по $i$ функция двух аргументов с рациональными значениями. Округлим $m(x, i)$ в сторону увеличения до ближайшей степени двойки (то есть до одного из чисел $1, 1/2, 1/4, 1/8, \dots$), при этом нули оставляем нулями. Назовём результат округления $m'(x, i)$. По-прежнему $m'$ — вычислимая функция, монотонная по второму аргументу. Очевидно, $m'(x, i)$ не меньше $m(x, i)$, но превосходит $m(x, i)$ не более чем вдвое.

Назовём пару $(x, i)$ **граничной**, если $m'(x, i)$ больше $m'(x, i-1)$ (или если $i=0$ и $m'(x, 0) > 0$). Граничные пары отмечают те места, где запросы $m'(x, i)$ увеличиваются с ростом $i$ (при данном $x$).

Показем, что сумма всех $m'(x, i)$ по всем граничным парам $(x, i)$ не превосходит 4. Для этого достаточно показать, что сумма $m'(x, i)$ по всем граничным $i$ (для данного $x$) не превосходит $4m(x)$. А это делается так. В указанной сумме (для фиксированного $x$) каждый следующий член по крайней мере вдвое больше предыдущего, поэтому вся сумма не превосходит удвоенного последнего члена. А он, в свою очередь, не более чем вдвое превосходит $m(x, i)$ для какого-то $i$. Вспоминая, что $m(x, i) \le m(x)$, заключаем, что интересующая нас сумма не больше $4m(x)$, что и требовалось.

Множество всех граничных пар $(x, i)$ разрешимо. В самом деле, по паре можно проверить, является ли она граничной, посмотрев на рациональные числа $m'(x, i)$ и $m'(x, i-1)$.

Перенумеровав все пары в каком-то порядке и отобрав граничные, построим вычислимую последовательность $(x_0, i_0), (x_1, i_1), \dots$ содержащую каждую граничную пару по одному разу. Рассмотрим вычислимую последовательность чисел $l_n$, заданных соотношением

$$2^{-l_n} = m'(x_n, i_n)/4.$$

Тогда по доказанному

$$\sum_n 2^{-l_n} = (1/4) \sum_n m'(x_n, i_n) \le 1,$$

и потому $KP'(n) \le l_n + O(1)$. Поскольку $x_n$ алгоритмически получается по $n$, то (как мы видели в разделе про префиксную сложность)

$$KP'(x_n) \le KP'(n) + O(1) \le l_n + O(1) = -\log m'(x_n, i_n) + O(1).$$

Данное слово $x$ появляется среди $x_n$ столько раз, сколько имеется граничных пар вида $(x, i)$. Если $(x_n, i_n)$ — граничная пара с данным $x$ и наибольшим $i$, то $m'(x_n, i_n)$
больше или равно $m(x, i)$ при всех $i$ (поскольку округляем мы в сторону увеличения, и больших граничных пар нет). Поэтому в этом случае $m'(x_n, i_n) \ge m(x)$. Отсюда следует, что

$$KP'(x) \le -\log m(x) + O(1),$$

что и требовалось доказать. ►

Итак, три доказанных неравенства позволяют заключить, что $KP, KP'$ и $-\log m$ отличаются не более чем на $O(1)$. Имея это в виду, мы не будем различать $KP$ и $KP'$ (кроме тех случаев, когда в каком-то рассуждении годится только одно из этих двух определений).

Подробное изложение доказательства могло создать впечатление его сложности, но основная идея в сущности проста. В одну сторону: наличие короткого описания $p$ у слова $x$ гарантирует большую вероятность порождения слова $x$, так как при служащим выборе программы мы натыкаемся на $p$ с большой вероятностью. В другую сторону немного сложнее: большая вероятность не означает короткого описания, вместо этого может быть много длинных. Однако алгоритм выделения места поволяет их консолидировать: когда у некоторого объекта $x$ накопится описаний на $2^{-k}$, надо выделить для $x$ нетронутый отрезок длиной $\Omega(2^{-k})$, это можно делать, например, слева направо (уменьшая отрезок до правильно выровненного) — или использовать «лемму о шторах».

Аналогичные утверждения можно доказать и для релятивизованной (отноственно некоторого оракула) префиксной сложности: $KP^A$ совпадает с $KP'^A$ и с $-\log m^A$ с точностью до $O(1)$. Было бы интересно выяснить (авторы этого не знают), что из этих равенств сохраняется для более общих видов оракулов (типа сводимости по перечислению, или точек в конструктивном метрическом пространстве).

Отметим ещё (это нам пригодится при доказательстве критерия случайности в терминах монотонной сложности, раздел 5.6), что фактически мы доказали нечто большее:

**Теорема 59.** По любой перечислимой снизу последовательности чисел $p_0, p_1, p_2, \dots$, у которой $\sum_i p_i \le 1$, можно эффективно указать беспрефиксный способ описания $D$, для которого $KP'_D(i) \le -\log_2 p_i + 2$.

(Имеется в виду, что дан алгоритм, перечисляющий множество всех пар $(r, i)$, у которых $r < p_i$. Описанная в доказательстве теоремы конструкция алгоритмически преобразует его в беспрефиксный способ описания с нужным свойством.)

## 4.6. Свойства префиксной сложности

Вернёмся теперь к свойствам префиксной сложности. Для начала покажем, как некоторые уже известные нам свойства могут быть получены с использованием априорной вероятности (универсальной полумеры).

Ряд $\sum 1/n^2$, как известно из курса анализа, сходится. Умножив его на подходящую константу, получаем перечислимую снизу полумеру (с суммой меньше
единицы). Поэтому априорная вероятность числа $n$ не меньше $c/n^2$ при некотором $c$, то есть

$$KP(n) \le 2 \log n + O(1).$$

Пусть $x_n$ — слово с порядковым номером $n$ в последовательности $\Lambda, 0, 1, 00, 01, 10, 11, 000, \dots$; тогда

$$KP(x_n) \le KP(n) + O(1) \le 2l(x_n) + O(1) = 2l(x_n) + O(1)$$

(легко проверить, что $x_n$ есть двоичная запись числа $n+1$ без старшей цифры 1 и потому имеет длину $\log n + O(1)$). (Строго говоря, случай $n=0$ следовало бы разбирать отдельно, поскольку $1/0^2$ и $\log 0$ не определены, но необходимые исправления очевидны.) Получается оценка $KP(x) \le 2l(x) + O(1)$.

Чтобы получить лучшую оценку префиксной сложности (уже встречавшуюся нам на с. 98), рассмотрим более медленно сходящийся ряд

$$\sum \frac{1}{n \log^2 n}$$

(его сходимость можно установить, например, с помощью интегрального признания сходимости и интегрирования по частям). Он даёт оценку $KP(n) \le \log n + 2 \log \log n + O(1)$, которая после перехода к словам превращается в

$$KP(x) \le l(x) + 2 \log l(x) + O(1).$$

Можно дальше улучшать оценку, воспользовавшись рядами $\sum 1/(n \log n (\log \log n)^2)$, $\sum 1/(n \log n \log \log n (\log \log \log n)^2)$ и так далее.

Докажем теперь обещанное неравенство для энтропии пары.

### Теорема 60.

$$KP(x, y) \le KP(x) + KP(y) + O(1).$$

Под $KP(x, y)$ мы понимаем сложность слова $[x, y]$, где $\langle x, y \rangle \mapsto [x, y]$ — какое-либо вычислимое однозначное кодирование пар. (С точностью до ограниченного слагаемого сложность пары не зависит от выбора кодирования, поскольку переход от одного кодирования к другому — вычислимое преобразование.)

Рассмотрим функцию $m'$, определённую соотношением

$$m'([x, y]) = m(x)m(y),$$

где $m$ — априорная вероятность. (Если не всякое слово является кодом пары, полагаем $m'(z) = 0$ для слов $z$, не являющихся кодами.) Очевидно, $m'$ перечислика снизу (перемножая вычислимые последовательности, сходящиеся снизу к $m(x)$ и $m(y)$), получаем возрастающую вычислимую последовательность с нужным пределом). Кроме того,

$$\sum_z m'(z) = \sum_{x,y} m'([x,y]) = \sum_{x,y} m(x)m(y) = \sum_x m(x) \sum_y m(y) \le 1 \cdot 1 = 1.$$
Следовательно, $m'$ — перечислимая снизу полумера. Сравнивая её с априорной вероятностью, находим, что $m'([x, y]) \le cm([x, y])$ для некоторого $c$, и потому

$$KP([x, y]) \le KP(x) + KP(y) + O(1),$$

что и требовалось доказать. ►

**101** Докажите, что $\sum_y m([x, y])$ отличается от $m(x)$ не более чем на мультипликативную константу (в обе стороны). Докажите аналогичное утверждение для $\max_y m([x, y])$.

**102** Докажите, что для любой возрастающей вычислимой функции $f: \mathbb{N} \to \mathbb{N}$ величина $\sum \{m(k) | f(n) \le k < f(n+1)\}$ отличается от $m(n)$ не более чем на мультипликативную константу (в обе стороны): каким вычислимым способом ни разбивай сходящийся ряд $\sum m(n)$ на группы, получается тот же самый (с точностью до ограниченного множителя) ряд!

Попытаемся теперь доказать теорему 60 в терминах описаний. Здесь обнаруживается такой любопытный факт: определение с префиксно корректными способами не помогает, а с беспрефиксными всё получается. Итак, мы доказываем, что $KP'([x, y]) \le KP'(x) + KP'(y) + O(1)$. Пусть $D$ — оптимальный беспрефиксный способ описания, использованный при определении $KP'$.

Определим новый способ описания формулой

$$D'(pq) = [D(p), D(q)],$$

где $pq$ означает конкатенацию слов $p$ и $q$. Эта формула имеет смысл, если $D(p)$ и $D(q)$ определены. Требуется, однако, проверить, что это определение корректно, то есть что одно и то же слово $x$ не может быть представлено двумя разными способами $x = pq = p'q'$, если $D(p), D(q), D(p'), D(q')$ все определены. В самом деле, в этом случае слова $p$ и $p'$ согласованы (они являются началами одного и того же слова $x$, и потому одно из слов $p$ и $p'$ есть начало другого), поэтому $D(p)$ и $D(p')$ не могут быть одновременно определены при $p \ne p'$ (функция $D$ является беспрефиксной). А раз $p = p'$, то и $q = q'$.

Аналогичным образом легко проверить, что функция $D'$ является беспрефиксной: если $pq$ есть начало $p'q'$, то $p$ и $p'$ согласованы. Раз $D(p)$ и $D(p')$ определены, то $p = p'$. Поэтому $q$ является началом $q'$; раз $D(q)$ и $D(q')$ определены, то $q = q'$.

Функция $D'$ вычисlimа: чтобы найти $D'(x)$, мы разбиваем $x$ на $p$ и $q$ всеми возможными способами и параллельно вычисляем $D(p)$ и $D(q)$ для всех вариантов. Как мы видели, удачным может быть не более одного разбиения, и оно даёт ответ (если существует).

Остаётся заметить, что

$$KP_D([x, y]) \le KP_D(x) + KP_D(y).$$

В самом деле, если $p$ и $q$ — кратчайшие описания для $x$ и $y$ относительно $D$, то $pq$ — описание $[x, y]$ относительно $D'$, имеющее длину $KP_D(x) + KP_D(y)$.

Неформально машину $D'$ можно описать так: она читает вход, пока не прочтёт там описание для $x$. После этого остаток входа читается как описание для $y$.
**103** Докажите теорему 60, используя определение беспрефиксных способов описания в терминах машин с блокирующим чтением.

**104** Назовём множество слов беспрефиксным, если никакие два слова в нём не сравнимы. Покажите, что если А и В — беспрефиксные множества слов, то и множество

$$AB = \{ab \mid a \in A, b \in B\}$$

является беспрефиксным.

В данном случае рассуждение с априорной вероятностью было, пожалуй, проще. В следующем примере это уже не так.

**Теорема 61.**

$$KP(x, KP(x)) = KP(x) + O(1).$$

Аналогичное равенство для обычной (не префиксной) сложности составляло содержание задачи 23.

◀ Легко видеть, что $KP(x) \le KP(x, KP(x)) + O(1)$, поскольку $x$ получается алгоритмически по $[x, KP(x)]$. (Квадратные скобки обозначают вычислимое однозначное кодирование, используемое при определении префиксной сложности пары.)

Для доказательства обратного неравенства снова используем $KP'$, то есть беспрефиксные способы описания. Пусть $D$ — оптимальный беспрефиксный способ описания. Рассмотрим новый способ описания:

$$D'(p) = [D(p), l(p)],$$

имеющий ту же область определения, что и $D$, и потому беспрефиксный. Если $p$ — кратчайшее описание слова $x$ относительно $D$, то $l(p) = KP'(x)$, и потому $p$ является описанием пары $[x, KP'(x)]$ относительно $D'$. Поэтому $KP_{D'}([x, KP'(x)]) \le l(p) = KP'(x)$.

Теорема доказана? На самом деле тут есть тонкость, требующая разъяснения. Мы доказали теорему для функции $KP'$, соответствующей беспрефиксному способу описания. Если заменить её на $KP$ (соответствующую префиксно корректному способу описания), то правая часть изменится не более чем на константу. Вопрос в том, почему это верно и для левой части, поскольку $KP$ стоит внутри в качестве аргумента.

Чтобы ответить на этот вопрос, достаточно показать, что $KP(x, n)$ (сложность пары, в которой второй аргумент мы считаем натуральным числом) меняется не более чем на константу при изменении $n$ на единицу. Это следует из того, что отображения $[x, n] \mapsto [x, n+1]$ и $[x, n] \mapsto [x, n-1]$ вычислимы и потому могут увеличивать сложность не более чем на константу. ▶

Для сравнения проведём также и доказательство с помощью априорной вероятности. Пусть $m(x)$ — априорная вероятность слова $x$. Рассмотрим функцию $m'$, определённую так:

$$m'([x, k]) = \begin{cases} 2^{-k}, & \text{если } 2^{-k} < m(x), \\ 0, & \text{в противном случае.} \end{cases}$$
Эта функция перечислима снизу (для данных х и k мы выдаём нуль, пока не выяснится, что $2^{-k} < m(x)$, а потом выдаём $2^{-k}$).

Сумма $m'([x, k])$ по всем k (при данном x) представляет собой геометрическую прогрессию со знаменателем 2, и потому не больше $2m(x)$ (последний член прогрессии меньше $m(x)$). Следовательно, сумма $m'([x, k])$ по всем х и k конечна. Сравнивая $m'$ с априорной вероятностью и переходя к логарифмам, находим, что

$$KP(x, k) \le k + O(1)$$

при $2^{-k} < m(x)$. Теперь положим $k = -[\log m(x)] + 1$, тогда $2^{-k} < m(x)$ и получается, что

$$KP(x, -[\log m(x)] + 1) \le KP(x) + O(1).$$

Остаётся (как и раньше) заметить, что изменение второго члена пары на единицу меняет сложность не более чем на константу, и второе доказательство теоремы завершено.

**105** Приведённое только что доказательство теоремы 61 фактически доказывает чуть больше: $KP(x, u) \le u + O(1)$ при $KP(x) \le u$. Как вывести это из утверждения теоремы 61, не апеллируя к доказательству?

Что можно сказать об алгоритмических свойствах функции $KP(x)$? Как и обычная колмогоровская сложность, она перечислима сверху, но не вычислима и даже не имеет никакой нетривиальной (неограниченной) вычислимой нижней оценки. (Поскольку $KP(x) \le 2KS(x) + O(1)$, любая нетривиальная нижняя оценка для $KP$ немедленно давала бы нетривиальную нижнюю оценку для $KS$.)

Ранее (теорема 8, с. 29) мы видели, что $KS(x)$ можно определить как минимальную перечислимую сверху функцию $K$, для которой множества $\{x | K(x) < n\}$ имеют размер $O(2^n)$. Аналогичное утверждение для префиксной сложности выглядит так:

**Теорема 62.** $KP$ есть минимальная (с точностью до $O(1)$) перечислимая сверху функция $K$, для которой сумма ряда $\sum_x 2^{-K(x)}$ конечна.

◀ Как мы видели, функция $KP$ перечислима сверху и ряд $\sum_x 2^{-KP(x)}$ сходится. Если $K$ — перечислимая сверху функция с теми же свойствами, то функция $M(x) = c2^{-K(x)}$ при достаточно малом рациональном $c$ является полумерой (она перечислима снизу и сумма меньше 1). Следовательно, $M(x) = O(m(x))$ в силу maximальности априорной вероятности, и потому $\log M(x) \le \log m(x) + O(1)$, то есть $KP(x) \le K(x) + O(1)$. ►

Переформулировка: пусть функция $f$ с натуральными значениями определена на всех словах и перечислима сверху. Тогда свойства «$KP(x) \le f(x) + O(1)$» и $\sum_x 2^{-f(x)} < \infty$ равносильны.

Конечность суммы ряда в только что доказанной теореме является более сильным условием на функцию $K$, чем использованное в теореме 8 условие. В самом деле, если сумма ряда не больше $C$, то количество членов ряда, больших некоторой границы $\varepsilon$, не превосходит $C/\varepsilon$. Тем самым мы заново получаем, что $KS(x) \le KP(x) + O(1)$.
Поучительно сравнить обычную и префиксную сложности по двум параметрам: средней сложности слов данной длины и числу слов сложности не больше данной. Начнём с первого.

Мы видели, что большинство слов длины $n$ имеют (обычную) сложность $n + O(1)$ (см. с. 17, а также задачу 2 на с. 26). Естественно ожидать, что префиксная сложность будет несколько больше.

**Теорема 63.** (а) $KP(x) \le l(x) + KP(l(x)) + O(1)$.

(б) Найдётся такая константа $c$, что для любого $n$ и для любого $d$ доля слов $x$ длины $n$, у которых $KP(x) < n + KP(n) - d$, не превосходит $c2^{-d}$.

▲ (а) Пусть $m(x)$ — априорная вероятность слова $x$. Мы будем также говорить об априорной вероятности $m(n)$ натурального числа $n$ (или, что то же самое, его двоичной записи). Рассмотрим функцию $m'(x)$, равную $2^{-n}m(n)$ для слов $x$ длины $n$. Значения этой функции на всех словах длины $n$ одинаковы и в сумме дают $m(n)$, поэтому $\sum_{x} m'(x) \le 1$. Функция $m'$ перечислима снизу. Поскольку полумера $m$ является наибольшей, заключаем, что $m'(x) \le cm(x)$ для некоторого $c$ и для всех $x$. Переходя к логарифмам, получаем неравенство

$$KP(x) \le n + KP(n) + O(1)$$

для слов длины $n$ (константа в $O(1)$ не зависит от $n$).

(б) Теперь будем двигаться в обратном направлении и рассмотрим функцию

$$m'(n) = \sum_{l(x)=n} m(x)$$

(сумму априорных вероятностей всех слов данной длины). Поскольку эта функция перечислима снизу и $\sum_n m'(n) \le 1$, то $m'(n) = O(m(n))$ (где $m(n)$ — априорная вероятность натурального числа $n$). С другой стороны, слово из $n$ нулей имеет (с точностью до константы) ту же априорную вероятность, что и $n$, так что

$$c_1 m(n) \le \sum_{l(x)=n} m(x) \le c_2 m(n).$$

Другими словами, сумма значений функции $m(x)$ на словах длины $n$ с точностью до константы совпадает с $m(n)$, а среднее значение $m(x)$ на этих словах — с $m(n)/2^n$. Остаётся заметить, что доля тех аргументов, для которых функция в $2^d$ раз превышает своё среднее, не превосходит $2^{-d}$ (неравенство Чебышёва). ▶

**106** Используя эти оценки, докажите, что среднее арифметическое префиксных сложностей всех слов длины $n$ равно $n + KP(n) + O(1)$.

(Для обычной сложности это сделано в задаче 3, с. 26.)

Теперь оценим число слов данной сложности.

**Теорема 64.** Логарифм числа слов $x$, для которых $KP(x) < n$, равен $n - KP(n) + O(1)$.
◀ Пусть $c_n$ — число слов, для которых $KP(x) < n$. Перепишем основное свойство префиксной сложности, сходимость ряда $\sum 2^{-KP(x)}$, в терминах чисел $c_n$. Имеется $c_{n+1} - c_n$ слов, сложность которых равна в точности $n$, поэтому сумму ряда можно переписать как $\sum_n 2^{-n}(c_{n+1} - c_n)$. Перегруппировав члены, убеждаемся, что сумма $\sum_n (2^{-(n-1)} - 2^{-n})c_n = \sum_n 2^{-n}c_n$ конечна. Поскольку $c_n$ перечислимо снизу, то отсюда следует, что $2^{-n}c_n$ не превосходит априорной вероятности $m(n)$ числа $n$, откуда $c_n \le m(n)2^n$ (с точностью до мультипликативной константы).

С другой стороны, легко построить перечислимую сверху функцию $K$, аргументами которой являются двоичные слова, а значениями натуральные числа и плюс бесконечность, у которой будет примерно $m(n)2^n$ значений, равных $n$. Например, можно договориться, что на словах длины $n$ эта функция равна либо $n$, либо $+\infty$, причём изначально все значения бесконечны, а затем по мере появления всё больших оценок для $m(n)$ нужное число бесконечных значений заменяется на $n$.

Для этой функции сумма $\sum 2^{-K(x)}$ сходится, поэтому $KP(x) \le K(x) + O(1)$, и потому $c_{n+O(1)} \ge m(n)2^n$. Остаётся вспомнить, что $m(n)$ и $2^n$ меняются не более чем в константу раз при изменении $n$ на единицу. ▶

Эти результаты могут создать впечатление, что префиксная и обычная меры сложности отличаются всего лишь выбором шкалы (шкала для префиксной сложности сдвинута относительно обычной, так что префиксная сложность немного больше). Так ли это? Этот вопрос можно естественным образом уточнить: существуют ли две последовательности слов $a_n$ и $b_n$, для которых $KS(a_n) - KS(b_n) \to +\infty$, но $KP(a_n) - KP(b_n) \to -\infty$? На этот вопрос ответили Ан. А. Мучник и С. Е. Посицельский, доказав существование таких последовательностей в [118]. Другое доказательство дал Миллер (см. [104], где обсуждаются и другие результаты о связи простой и префиксной сложности). Мы ограничимся лишь несколькими простыми замечаниями (см. также раздел 4.7.4, р. 130).

Неравенство $KP(x) \le l(x) + KP(l(x))$ можно итерировать, получая

$$KP(x) \le l(x) + l(l(x)) + KP(l(l(x)) + O(1), \\ KP(x) \le l(x) + l(l(x)) + l(l(l(x))) + KP(l(l(l(x)))) + O(1)$$

и так далее. Кроме того, можно вспомнить, что если $D$ — оптимальный способ описания для обычной (не префиксной) сложности, то $KP(D(y)) \le KP(y) + O(1)$; сочетая это с неравенством $KP(x) \le l(x) + KP(l(x)) + O(1)$, получаем следующее утверждение:

Теорема 65.

$$KP(x) \le KS(x) + KP(KS(x))) + O(1), \\ KP(x) \le KS(x) + KS(KS(x))) + KP(KS(KS(x))) + O(1)$$

и так далее.

Отметим кстати, что все эти неравенства получаются также повторным применением первого из них.
**107** Докажите, что

$$KS(x, y) \le KP(x) + KS(y) + O(1)$$

для любых слов х, у. [Указание. Можно подсчитать число пар, где правая часть меньше n, но проще воспользоваться беспрефиксным кодированием.]

Мы говорили, что случайными словами длины n естественно считать те, у которых (простая) колмогоровская сложность максимальна, то есть близка к n. А что будет, если потребовать, чтобы префиксная сложность была максимальна, то есть близка к $n + KP(n)$? Следующая задача показывает, что из этого следует случайность в прежнем смысле.

**108** Покажите, что если обычная сложность слова х длины n не превосходит $n - d$, то его префиксная сложность не превосходит $n + KP(n) - d + O(\log d)$. [Указание: соединим беспрефиксные описания для х и d с обычным описанием для х.]

Аналогичное утверждение в обратную сторону неверно, как показал Р. Соловей (см. упомянутую статью Миллера [104] или [117]).

# 4.7. Условная префиксная сложность и сложность пары

## 4.7.1. Условная префиксная сложность

Как определить префиксный вариант условной сложности? Каждое из приведённых нами определений можно модифицировать, добавив туда условия. Вот что при этом получится.

Функция D двух аргументов называется **префиксно корректной** относительно первого аргумента, если при любом фиксированном значении второго аргумента получается префиксно корректная функция:

$$D(y, z) \text{ определено и } y \le y' \Rightarrow D(y', z) = D(y, z).$$

Здесь предполагается, что первый аргумент является двоичным словом; $y \le y'$ означает, что $y'$ является продолжением у.

При определении условной сложности в разделе 2.2 мы рассматривали всевозможные вычислимые функции двух аргументов, называя их способами условного описания. (В качестве аргументов и значений рассматривались двоичные слова.) Равенство $D(y, z) = x$ читалось так: у является описанием х при известном z. Сложность х при известном z определялась как длина кратчайшего описания. Среди всех способов описания выбирался оптимальный, при котором сложность меньше всего (с точностью до константы).

Ограничиваемся теперь префиксно корректными по первому аргументу способами описания. Среди них тоже существует оптимальный. Доказательство этого факта аналогично доказательству теоремы 48 на с. 95 (о существовании оптимального префиксно корректного способа безусловного описания), только все приведённые
там рассуждения надо параллельно провести для всех условий z. Именно, надо положить

$$D'(\hat{p}y, z) = [p](y, z),$$

где $[p](y, z)$ означает результат принудительной префиксной коррекции программы $p$ (как функции от у при каждом $z$ в отдельности).

Выбрав оптимальный префиксно корректный способ условного описания, сложность относительно него мы называем условной префиксной сложностью и обозначаем её $KP(x|z)$ (читается: «условная префиксная сложность слова $x$ при известном слове $z$).

Это определение можно видоизменить, заменив требование префиксной корректности на требование беспрефиксности по первому аргументу. И для этого класса существует оптимальный способ условного описания; соответствующую сложность будем обозначать $KP'(x|z)$. Можно доказать, что эти определения различаются не более чем на константу:

$$KP'(x|z) = KP(x|z) + O(1),$$

причём константа эта не зависит не только от $x$, но и от $z$.

Как и для безусловного случая, прямое доказательство этого равенства затруднительно, и в качестве промежуточного звена используется условная априорная вероятность $m(x|z)$. Её (как и раньше) можно определить двумя способами. Первый способ использует вероятностные машины с входом. Пусть $M$ — такая машина. Для каждого входного слова $z$ возникает своё распределение вероятностей: выход $x$ (при входе $z$) имеет некоторую вероятность $p_M(x|z)$. Функция $\langle x, z \rangle \mapsto p_M(x|z)$ перечислима снизу (в естественном смысле), и для каждого $z$ сумма $\sum_x p_M(x|z)$ не превосходит единицы. Эти свойства описывают класс всех функций $p_M$: если имеется перечислимая снизу неотрицательная функция $\langle x, z \rangle \mapsto p(x|z)$, для которой $\sum_x p(x|z) \le 1$ при всех $z$, то можно построить вероятностную машину $M$, для которой $p_M = p$.

Среди всех функций $p_M$ существует наибольшая с точностью до умножения на константу. Мы фиксируем одну из таких наибольших функций, называем её условной априорной вероятностью слова $x$ при известном слове $z$ и обозначаем $m(x|z)$.

Далее мы доказываем, что $-\log m(x|z) \le KP(x|z) + O(1)$ и что $KP'(x|z) \le -\log m(x|z) + O(1)$. Неравенство $KP(x|z) \le KP'(x|z) + O(1)$, которое доказывается столь же просто, как и в безусловном случае, замыкает круг: все три величины $KP(x|z)$, $KP'(x|z)$ и $-\log m(x|z)$ отличаются не более чем на константу.

Мы не приводим подробно всех доказательств, поскольку они состоят в параллельном проведении «безусловных» доказательств для всех условий $z$. Можно сказать, что мы имеем дело с «релятивизацией», но несколько особого вида.

Поясним сказанное. В общей теории алгоритмов «релятивизация» означает, что вместо вычислимых функций мы рассматриваем функции, вычислимые относительно некоторого оракула $A$. (Здесь $A$ — произвольное множество слов. Считается, что алгоритм, отвечающий на вопросы о принадлежности слова $x$ множеству $A$,
доступен как внешняя процедура с входным параметром х.) Практически все известные теоремы общей теории алгоритмов без труда переносятся и на такие («A-вычислимые») функции.

Кстати, и понятие сложности можно релятивизовать таким образом, определив для любого множества A колмогоровскую сложность $KS^A(x)$ и префиксную колмогоровскую сложность $KP^A(x)$ (см. раздел 6.4). Но сейчас мы делаем не это: в качестве оракула мы рассматриваем доступ к конечному слову z. Конечно, такой оракул не может изменить понятие вычислимости (слово z конечно), но он меняет колмогоровскую сложность, поскольку информация, имеющаяся в z, «выносится за скобки» и не учитывается при подсчёте сложности. В результате вместо обычной колмогоровской сложности $KS(x)$ мы получаем условную сложность $KS(x|z)$. Другой пример: величину $I(x:y|z)$ можно считать релятивизованной относительно z версией понятия взаимной информации $I(x:y)$.

Ещё одно важное замечание. Во всех наших рассмотрениях какие-бы то ни было требования, связанные с префиксами (началами), относятся только к описаниям. Напротив, и описываемые объекты, и условия для нас лишены какой бы то ни было структуры.

Такой подход не является единственно возможным. Можно учитывать отношение «быть началом» для описываемых объектов (так делают при определении монотонной сложности и сложности разрешения, см. главы 5 и 6). Можно было бы также учитывать отношение «быть началом» и для условий (см. раздел 6.3); такие варианты определений вполне осмыслены, хотя и мало изучены.

Отметим также, что при определении условной префиксной сложности требования, связанные с префиксами, накладываются отдельно при каждом значении условия (второго аргумента функции). Например, мы требуем, чтобы машина сама решала, когда она кончит читать описание — но это решение может зависеть от второго аргумента. Из-за этого утверждение, аналогичное задаче 28 (с. 45), уже не имеет места:

**109** Показите, что $KP(y|x)$ не превосходит минимальной префиксной сложности программ, переводящих $x$ в $y$, но обратное неверно (все неравенства понимаются с точностью до $O(1)$). (Оба утверждения верны для любого разумного языка программирования; аддитивная константа может зависеть от выбора языка программирования.) [Указание. Легко видеть, что $KP(y|I(y)) \le I(y) + O(1)$, так как при известном $I(y)$ каждое слово можно считать своей самоограниченной программой. Если бы обратное утверждение было верно, то отсюда мы получили бы $2^n$ различных программ префиксной сложности не более $n$.]

### 4.7.2. Свойства условной префиксной сложности

Перечислим несколько простых свойств условной префиксной сложности.

$$ \bullet KP(x|z) \le KP(x) + O(1). $$

В самом деле, любой префиксно корректный (или беспрефиксный) способ безусловного описания $y \mapsto D(y)$ можно рассматривать как префиксно кор-
ректный (соответственно беспрефиксный) способ условного описания $\langle y, z \rangle \mapsto \mapsto D(y)$ (второй аргумент фиктивен).

В терминах полумер: всякая вероятностная машина без входа может рассматриваться как вероятностная машина со входом, игнорирующая свой вход. Соответственно любая перечислимая снизу полумера $q(x)$ может рассматриваться как семейство полумер $q'(x|z) = q(x)$ с фиктивным параметром $z$.

* $KP(x|x) = O(1)$.

Способ описания $D(y, z) = z$ является префиксно корректным (нас интересует префиксная корректность по $y$, а не по $z$) и $KP_D(x|x) = 0$. Беспрефиксный способ описания можно определить так: $D(\Lambda, z) = z$, где $\Lambda$ — пустое слово; для непустых первых аргументов $D$ не определён. Наконец, перечислимое снизу семейство полумер таково: $q(x|x) = 1$ и $q(x|z) = 0$ при $z \neq x$.

* $KP(f(x, z)|z) \le KP(x|z) + O(1)$ для любой вычислимой функции $f$ и для любых слов $x, z$, на которых $f$ определена. (При этом константа в $O(1)$ может зависеть от $f$, но не от $x$ и $z$.)

Если $D$ — оптимальный префиксно корректный [беспрефиксный] способ условного описания, то $D': \langle y, z \rangle \mapsto f(D(y, z), z)$ также будет префиксно корректным [соответственно беспрефиксным] и $KP_{D'}(f(x, z)|z) \le KP_D(x|z)$, откуда и следует искомое неравенство.

В терминах полумер: если $m(x|z)$ — априорная вероятность $x$ при известном $z$, рассмотрим полумеру

$$q(x|z) = \sum \{m(x'|z) | f(x', z) = x\}$$

(при каждом $z$ она представляет собой прямой образ полумеры $x \mapsto m(x, z)$ при отображении $x \mapsto f(x, z)$); легко проверить, что функция $q$ перечислима снизу, что $\sum_x q(x|z) \le 1$ и что $q(f(x, z)|z) \ge m(x|z)$. Используя оптимальность $m$, приходим к искомому неравенству (для логарифмов априорных вероятностей).

* $KP(f(x)|x) = O(1)$ для любой вычислимой функции $f$ и для всех $x$, при которых $f(x)$ определено.
  (Простое следствие предыдущих.)

* $KP(x|z) \le KP(x|f(z)) + O(1)$ для любой вычислимой функции $f$ и любых $x, z$ (если $f(z)$ определено; константа может зависеть от $f$, но не от $x$ и $z$). (Достаточно рассмотреть способ описания $\langle y, z \rangle \mapsto D(y, f(z))$ или семейство полумер $q(x|z) = m(x|f(z))$.)

* $KS(x|z) \le KP(x|z) + O(1)$

В самом деле, префиксно корректные (или беспрефиксные) способы условного описания входят в число способов условного описания, рассматриваемых при определении $KS(x|z)$.

* $KP(x|z) \le KS(x|z) + 2 \log KS(x|z) + O(1)$

Это утверждение можно вывести из предыдущих. Пусть $D$ — оптимальный способ условного описания (не обязательно префиксно корректный). Тогда

$$KP(D(y, z)|z) \le KP(y|z) + O(1) \le KP(y) + O(1) \le l(y) + 2 \log l(y) + O(1).$$
Если в качестве у взято кратчайшее описание х при известном z, то $l(y) = KS(x|z)$.

Аналогичным образом можно доказать и более сильное неравенство

$$KP(x|z) \le KS(x|z) + \log KS(x|z) + 2 \log \log KS(x|z) + O(1)$$

и так далее.

### 4.7.3. Префиксная сложность пары

Мы видели (теорема 60, с. 113), что $KP(x, y) \le KP(x) + KP(y) + O(1)$. Это неравенство можно усилить:

**Теорема 66.**

$$KP(x, y) \le KP(x) + KP(y|x) + O(1).$$

◀ Есть два варианта доказательства: с беспрефиксными способами описания и с полумерами. С беспрефиксными способами описания мы рассуждаем так. Пусть $D$ — оптимальный беспрефиксный способ безусловного описания, а $D_c$ — оптимальный беспрефиксный способ условного описания. Рассмотрим способ описания $D'$, определяемый формулой

$$D'(uv) = [D(u), D_c(v, D(u))]$$

(для тех $u$ и $v$, для которых правая часть определена). Как и при доказательстве теоремы 60, легко проверить, что $D'$ корректно определён и является беспрефиксным способом описания; при этом конкатенация кратчайших описаний для $x$ и для $y$ (при известном $x$) даст описание для $[x, y]$.

(Заметим, что в этом рассуждении существен порядок $u$ и $v$: если бы мы взяли $vu$ (вместо $uv$), то сначала надо было бы выделять слово $v$, и возникла бы трудность: функция $D_c$ является беспрефиксной при фиксированном втором аргументе, а $D(u)$ пока ещё не известно.)

С полумерами: пусть $m(x)$ — априорная вероятность $x$, а $m(y|x)$ — априорная вероятность $y$ при известном $x$. Рассмотрим функцию $m'$, определённую соотношением

$$m'([x, y]) = m(x)m(y|x)$$

(мы считаем, что $m'(z) = 0$ для слов $z$, не являющихся кодами пар). Тогда $m'$ перечислила снизу (как произведение двух перечислимых снизу функций), и

$$\sum_{z} m'(z) = \sum_{x,y} m(x)m(y|x) = \sum_{x} [m(x) \sum_{y} m(y|x)] \le \sum_{x} m(x) \le 1.$$

Поэтому $m([x, y]) \ge \varepsilon m'([x, y]) = \varepsilon m(x)m(y|x)$, что и требовалось доказать. ►

**110** Доказите, что $KS(x, y) \le KP(x) + KS(y|x) + O(1)$.

[Указание. Можно использовать беспрефиксные способы описания, дописав к беспрефиксному описанию для $x$ обычное описание для $y$ при известном $x$. А можно подсчитать число пар, при которых $KP(x) + KS(y|x) \le n$. Если первое слагаемое равно $k$, то пар не больше $2^k \cdot m(k) \cdot 2^{n-k} = 2^n m(k)$, и после суммирования по $k$ получаем $2^n \cdot O(1)$.]
Только что доказанное неравенство можно несколько усилить. Для начала за-
метим, что мы можем рассматривать в качестве условий не только слова, но и
пары слов (поскольку замена одного способа кодирования пар на другой меняет
сложность не более чем на константу). Кроме того, можно говорить о сложности
троек слов. После этих замечаний можно записать такую цепочку неравенств (для
краткости члены $O(1)$ опускаем):

$$
\begin{align*}
\mathrm{KP}(x, y) \le \mathrm{KP}(x, \mathrm{KP}(x), y) \le \mathrm{KP}(x, \mathrm{KP}(x)) + \mathrm{KP}(y|x, \mathrm{KP}(x)) = \\
&= \mathrm{KP}(x) + \mathrm{KP}(y|x, \mathrm{KP}(x)).
\end{align*}
$$

При этом мы использовали равенство KP(x, KP(x)) = KP(x) (теорема 61), а так-
же только что доказанную теорему про энтропию пары. Полученное неравенство
усиливает эту теорему, поскольку KP(y|x, KP(x)) ≤ KP(y|x) (x получается алго-
ритмически по [x, KP(x)]). Как обнаружили Л. А. Левин (см. [43]) и Г. Чейтин [23],
такое уточнение замечательным образом превращает неравенство в равенство:

Теорема 67.

$$
\mathrm{KP}(x, y) = \mathrm{KP}(x) + \mathrm{KP}(y | x, \mathrm{KP}(x)) + O(1).
$$

◀ В одну сторону неравенство нами уже доказано (см. обсуждение перед фор-
мулировкой теоремы). Можно привести и прямое доказательство: чтобы получить
беспрефиксный код пары ⟨x, y⟩, достаточно к кратчайшему беспрефиксному коду
x приписать справа беспрефиксный код у при известных х и KP(x) (причём в ка-
честве KP(x) надо взять как раз длину написанного беспрефиксного кода для х).
Заметим, что после выделения первой части мы знаем не только х, но и KP(x),
так что есть всё необходимое для восстановления слова у.

В терминах полумер это доказательство можно изложить так. Рассмотрим функ-
цию m', для которой

$$
m'([x, y]) = \sum_{\{k|2^{-k} < 2m(x)\}} 2^{-k} m(y|x, k).
$$

Эта функция перечислима снизу, сумма по всем х, у конечна (сумма $m(y|x, k)$ по у
не больше 1; сумма $2^{-k}$ по всем $k$, для которых $2^{-k} < 2m(x)$, не больше $4m(x)$,
и суммирование по всем $x$ даёт не больше 4). Остаётся сравнить её с априорной
вероятностью $m$ и заметить, что при $k = -\lfloor \log_2 m(x) \rfloor$ получаем как раз нужный
член суммы.

Перейдём теперь к доказательству обратного неравенства:

$$
\mathrm{KP}(x) + \mathrm{KP}(y | x, \mathrm{KP}(x)) \le \mathrm{KP}(x, y) + O(1).
$$

Для начала приведём (неправильное, но более простое) доказательство (неправиль-
ного, но более сильного) утверждения

$$
\mathrm{KP}(x) + \mathrm{KP}(y|x) \le \mathrm{KP}(x, y) + O(1).
$$
Переходя к полумерам, можно переписать это неравенство так:

$$m(x)m(y|x) \geq \varepsilon m([x, y])$$

(для некоторого $\varepsilon$ и для всех $x, y$). Здесь буквой $m$ обозначены априорные вероятности (условная и безусловная). Перепишем это неравенство как

$$m(y|x) \geq \varepsilon \frac{m([x, y])}{m(x)}.$$

Достаточно доказать, что функция

$$m'(y|x) = \varepsilon \frac{m([x, y])}{m(x)}$$

при любом фиксированном $x$ является полумерой (при некотором $\varepsilon$), после чего сослаться на максимальность функции $m(y|x)$. Просуммируем $m'(y|x)$ по $y$. Нам надо убедиться, что сумма

$$\sum_{y} m'(y|x) = \varepsilon \frac{\sum_{y} m([x, y])}{m(x)}$$

не превосходит единицы.

Почему это так? В самом деле, функция $x \mapsto \sum_y m([x, y])$ является полумерой (её сумма по всем $x$ есть $\sum_{x,y} m([x, y]) \leq 1$) и потому эта функция не больше $m(x)/\varepsilon$ при некотором $\varepsilon$.

Где ошибка в этом рассуждении? Мы забыли, что полумерам должна быть перечислика снизу. В одном из двух случаев это действительно так: функция $\sum_y m([x, y])$, как легко понять, будет перечислимой снизу, поскольку функция $m$ была такой. Но вот про $m([x, y])/m(x)$ этого сказать уже нельзя, поскольку $m(x)$ стоит в знаменателе, а при возрастании знаменателя дробь не увеличивается (как нам бы хотелось), а уменьшается.

Правильное доказательство более слабого неравенства следует той же схеме, но обходит указанную только что трудность. Мы должны доказать, что при $z = KP(x)$ имеет место неравенство

$$m(y|x, z) \geq \varepsilon \frac{m([x, y])}{m(x)}.$$

Наша проблема, напомним, в том, что правая часть не является перечислимой снизу. Но при $z = KP(x)$ можно заменить $m(x) \approx 2^{-KP(x)}$ на $2^{-z}$ и рассмотреть функцию

$$m'(y|x, z) = m([x, y])2^z.$$

Эта функция перечислима снизу. Зато она может не быть полумерой, поскольку сумма $\sum_y m'(y|x, z)$ не всегда будет ограничена единицей. Это будет так, лишь если

$$\sum_{y} m([x, y]) \leq 2^{-z}.$$
Мы видели, что $\sum_y m([x, y]) = O(m(x)) = O(2^{-KP(x)})$, поэтому для некоторой константы $c$ выполнено такое свойство:

$$z \le KP(x) - c \Rightarrow \sum_y m'(y | x, z) \le 1.$$

Это хорошо, но мало: нам нужно семейство полумер, в котором такое неравенство выполняется при всех $x$ и $z$, а не только при некоторых. Поэтому мы исправим функцию $m'$, получив функцию $m''$ с такими свойствами:

* функция $\langle y, x, z \rangle \mapsto m''(y | x, z)$ перечислима снизу;

* неравенство

$$\sum_y m''(y | x, z) \le 1$$

выполнено при всех $x$ и $z$;

* для некоторой константы $c$

$$z \le KP(x) - c \Rightarrow m''(y | x, z) = m'(y | x, z).$$

Технология такого рода исправления уже обсуждалась в разделе 4.2: строя всё большие приближения снизу, мы проверяем, не нарушают ли они границу для суммы, и если нарушают, то отбрасываем.

Сравнивая $m''$ с априорной условной вероятностью и переходя к логарифмам, мы видим, что

$$z \le KP(x) - c \Rightarrow KP(y | x, z) \le KP(x, y) - z + c'$$

для некоторых констант $c$ и $c'$ и для всех $x, y, z$.

Чтобы вывести отсюда утверждение теоремы, подставим $z = KP(x) - c$ в полученное неравенство и заметим, что при изменении $z$ на единицу значение $KP(y|x, z)$ меняется не более чем на константу (функция прибавления единицы ко второму члену пары вычислима, аналогично для вычитания), поэтому

$$KP(y|x, KP(x) - c) = KP(y|x, KP(x)) + O(1). \quad \blacksquare$$

Заметим, что теорема 22 (с. 49), утверждающая, что

$$KS(x, y) = KS(x) + KS(y|x) + O(\log n)$$

для слов сложности не больше $n$, является следствием только что доказанной.

В самом деле, замена $KP$ на $KS$ меняет все три члена в равенстве на более чем на $O(\log n)$. Остаётся заметить, что $KS(y|x, KP(x))$ отличается от $KS(y|x)$ не более чем на $O(\log n)$. Тем самым мы получили новое доказательство теоремы 22, в которой комбинаторные подсчёты заменены оценками вероятностей.

Вспоминая, что $m(x) \approx \sum_y m([x, y])$ с точностью до ограниченного множителя (задача 101, с. 114), можно переписать утверждение теоремы 67 так:

$$m(y|x, KP(x)) \approx \frac{m([x, y])}{\sum_y m([x, y])}.$$
Правую часть этого равенства можно интерпретировать как условную вероятность того, что второй член пары равен у, при условии «первый член пары равен х».

**111** Докажите, что

$$KP(x|z) \le KP(x|y) + KP(y|z) + O(1)$$

для любых слов x, y, z. (Это неравенство можно ещё усилить, заменить $KP(x|y)$ на меньшую величину $KP(x|y, z)$.)

**112** Докажите «релятивизованный» вариант теоремы 67:

$$KP(x, y|z) = KP(x|z) + KP(y|x, KP(x|z), z) + O(1).$$

Дважды применяя теорему 67, можно получить формулу для префиксной сложности тройки слов. Эту тройку можно рассматривать как пару, первый член которой есть пара $(x, y)$, а второй — $z$. Получаем, что

$$KP(x, y, z) = KP(z|x, y, KP(x, y)) + KP(x, y) + O(1).$$

Ещё раз применяя теорему 67, получаем ответ:

### Теорема 68.

$$KP(x, y, z) = KP(z|x, y, KP(x, y)) + KP(y|x, KP(x)) + KP(x) + O(1).$$

Можно изменить порядок действий (применяя на втором шаге «релятивизованный» относительно z) вариант теоремы 67):

$$KP(x, y, z) = KP(y, z|x, KP(x)) + KP(x) = \\ = KP(z|y, KP(y|x, KP(x)), x, KP(x)) + KP(y|x, KP(x)) + KP(x)$$

(для краткости мы опускаем слагаемые $O(1)$).

Получилась немного другая формула по сравнению с утверждением теоремы 68: два последних слагаемых в ней те же, но первое слагаемое изменилось. Как и раньше, там стоит условная сложность слова z, но вместо условия $KP(x, y)$ появилось два условия $KP(x)$ и $KP(y|x, KP(x))$ — две сложности, которые в сумме дают как раз $KP(x, y)$ по теореме 67. Поэтому пара этих сложностей содержит не меньше информации, чем $KP(x, y)$. Более удивительно, что (при известных x и y) верно и обратное. В самом деле, подставим в качестве z пару $(KP(x), KP(y|x, KP(x)))$; во второй формуле первое слагаемое обратится в нуль (точнее, в $O(1)$). Приравняв правые части формул, получаем такое следствие:

### Теорема 69.

$$KP(KP(x)|x, y, KP(x, y)) = O(1), \\ KP(KP(y|x, KP(x))|x, y, KP(x, y)) = O(1).$$

(Разумеется, симметричные утверждения верны для $KP(y)$ и $KP(x|y, KP(y))$.)
**113** Дайте прямое доказательство теоремы 69. [Указание. Зная х, у и KP(x, y), мы можем искать верхнюю оценку d для KP(x), для которой KP(y|x, d) + d сравняется с KP(x, y). Совпадение с точностью до O(1) будет означать, что d = KP(x) + O(1): если d превышает KP(x) на некоторое число m, то KP(y|x, d) может упасть за счёт этого не более чем на O(log m), поэтому в сумме будет проигрыш.]

С помощью теоремы 67 легко показать, что базисное неравенство (теорема 24, с. 58) для префиксной сложности выполняется с точностью O(1) (для обычной сложности была лишь логарифмическая оценка):

**Теорема 70.**

$$KP(x, y, z) + KP(x) \le KP(x, y) + KP(x, z) + O(1)$$

для любых трёх слов x, y, z.

◀ В самом деле, правую часть можно переписать как

$$KP(x) + KP(y|x, KP(x)) + KP(x) + KP(z|x, KP(x)),$$

а левую — как

$$KP(x) + KP(y, z|x, KP(x)) + KP(x),$$

и остаётся доказать, что

$$KP(y, z|x, KP(x)) \le KP(y|x, KP(x)) + KP(z|x, KP(x)),$$

что есть релятивизованный вариант теоремы 60 (с. 113). ▶

Приведём также прямое доказательство теоремы 70 с помощью полумер. Нам нужно доказать, что (с точностью до ограниченных множителей)

$$m(x, y, z)m(x) \ge m(x, y)m(x, z),$$

где m — наибольшая перечислимая снизу полумера. Поделив на m(x), получим неравенство

$$\frac{m(x, y)m(x, z)}{m(x)} \le m(x, y, z).$$

Проверим, что его левая часть имеет конечную сумму (по всем тройкам слов x, y, z). Это следует из того, что

$$\sum_{y,z} \frac{m(x, y)m(x, z)}{m(x)} \le m(x)$$

(ведь $\sum_u m(x, y) \le m(x)$ и $\sum_z m(x, z) \le m(x)$). (Для краткости мы опускаем множители O(1), как если бы они были равны единице.)

Этого, однако, недостаточно: из-за m(x) в знаменателе дробь

$$\frac{m(x, y)m(x, z)}{m(x)}$$
может не быть перечислимой снизу, и потому мы не можем воспользоваться свойством максимальности. Применим такой обходной манёвр (уже использованный нами при доказательстве теоремы 67): построим перечислимую снизу верхнюю оценку для этой дроби.

Это делается так: для каждого натурального $n$ через $m_n(x, y)$ обозначим функцию $m(x, y)$, у которой для каждого $x$ сумма $\sum_y m(x, y)$ принудительно ограничена сверху числом $2^{-n}$. Заметим, что $\sum_y m(x, y)$ равно $m(x)$ (как и раньше, ограниченные множители мы опускаем), поэтому $m_n(x, y) = m(x, y)$ при $n = KP(x)$. Теперь рассмотрим функцию

$$ \langle x, y, z \rangle \mapsto \sum_{n \ge KP(x)} \frac{m_n(x, y)m_n(x, z)}{2^{-n}}. $$

Среди всех слагаемых есть и член с $n = KP(x)$. С другой стороны,

$$ \begin{aligned} \sum_{x,y,z} \sum_{n \ge KP(x)} \frac{m_n(x,y)m_n(x,z)}{2^{-n}} &\le \sum_x \sum_{n \ge KP(x)} \frac{\sum_y m_n(x,y)\sum_z m_n(x,z)}{2^{-n}} \\ &\le \sum_x \sum_{n \ge KP(x)} 2^{-n} \\ &\le \sum_x 2m(x) \\ &\le 2. \end{aligned} $$

(Как и раньше, мы опускаем константы — их учёт даст ограниченный множитель в окончательной оценке.)

**114.** Покажите, что неравенство из теоремы 26 (с. 59) для префиксной сложности выполняется с точностью $O(1)$:

$$ 2KP(x, y, z) \le KP(x, y) + KP(x, z) + KP(y, z) + O(1) $$

для любых слов $x, y, z$. [Указание: сложите базисное неравенство $KP(x, y, z) + KP(z) \le KP(x, z) + KP(y, z)$ с неравенством $KP(x, y, z) \le KP(x, y) + KP(z)$.]

**115.** Докажите, что при некотором $c$ для любого слова $x$ и любого числа $n$ найдётся такое слово $y$ длины $n$, что

$$ KP(x, y) \ge KP(x) + n - c. $$

[Указание: для любых $z$ и $n$ существует слово $y$ длины $n$, для которого $KP(y|z) \ge n$.]

Сходное утверждение можно сформулировать не для пар, а для продолжений данного слова $x$ на $n$ битов (аналогичное утверждение для простой колмогоровской сложности составляло содержание задачи 46 на с. 52):

**Теорема 71.**

$$ \max\{KP(xy) | l(y) = n\} \ge KP(x|n) + n - O(1). $$

Другими словами, при некотором $c$ для всех $x$ и $n$ можно так продлить слово $x$ на $n$ битов, чтобы его сложность увеличилась на $n-c$, правда не по сравнению с $KP(x)$, а лишь по сравнению с $KP(x|n)$.
◀ Переходя к априорным вероятностям, перепишем искомое неравенство как

$$2^n \min\{m(xy) | l(y) = n\} \le m(x|n) \cdot O(1).$$

Левая часть не превосходит $\sum\{m(xy) | l(y) = n\}$ (если заменить все слагаемые на наименьшее из них, сумма лишь уменьшится). А эта величина представляет собой при каждом $n$ (как функция от $x$) перечислимую снизу полумеру, так что остаётся воспользоваться максимальностью. ▶

**116** Показайте, что чуть более слабое утверждение с $KP(x) - KP(n)$ вместо $KP(x|n)$ в правой части можно вывести из задачи 115.

### 4.7.4. Обычная и префиксная сложности

Мы уже видели оценки для префиксной сложности в терминах обычной (теорема 65). Есть и другие связи. Например, следующее замечание Левина позволяет определить обычную сложность в терминах префиксной:

**Теорема 72.** Простую сложность $KS(x)$ можно определить как значение $i$, при котором $KP(x|i) = i$. Более точно, $KP(x|KS(x)) = KS(x) + O(1)$; с другой стороны, если $KP(x|i) = i + \delta$, то $KS(x) = i + O(\delta)$.

◀ Мы уже видели в задаче 44 (с. 51), что $KS(x) \le KS(x|KS(x))$ с точностью $O(1)$. С другой стороны, $KP(x|KS(x)) \le KS(x)$ с той же точностью. В самом деле, при известной длине описания это описание можно считать беспрефиксным (ограничившись описаниями только этой длины). Тем самым первое утверждение теоремы доказано. Остаётся заметить, что функция $i \mapsto KP(x|i)$ меняется медленно: изменение $i$ на $d$ приводит к изменению её значения на $O(\log d)$. Поэтому отклонение $i$ от значения $KS(x)$, при котором достигается равенство, приводит почти к такому же по величине отклонению $i$ от $KP(x|i)$. ▶

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

$$KP(x) = KP(x, KP(x)) = KP(KP(x)) + KP(x | KP(x), KP(KP(x)))$$

с точностью $O(1)$. Если нас устраивает точность $O(KP(KP(KP(x))))$, то пару $\langle KP(x), KP(KP(x)) \rangle$ в условии можно заменить на разность $KP(x) - KP(KP(x))$, и получится

$$KP(x) - KP(KP(x)) = KP(x | KP(x) - KP(KP(x))) + O(KP^{(3)}(x))$$

(используем сокращение $KP^{(i)}(x)$ для $i$ итераций функции $KP$). Остаётся воспользоваться предыдущей теоремой, и получится такой результат Соловея (из [161]):

**Теорема 73.**

$$KS(x) = KP(x) - KP(KP(x)) + O(KP^{(3)}(x)).$$

Другими словами, $KP(x) - KS(x)$ равно $KP(KP(x)) + O(KP^{(3)}(x))$.
Соловей заметил также, что в правой части можно заменить $KP$ на $KS$, то есть что $KP(x) - KS(x) = KS(KS(x)) + O(KS^{(3)}(x))$. На самом деле $O(KP^{(3)}(x))$ и $O(KS^{(3)}(x))$ — это одна и та же точность, и $KP(KP(x))$ и $KS(KS(x))$ совпадают с этой точностью. Чтобы убедиться в этом, заметим, что уже известная формула для $KP(x) - KS(x)$ позволяет утверждать, что

$$|KP(KP(x)) - KP(KS(x))| \le KP^{(3)}(x) + O(\log KP^{(3)}(x))$$

и

$$|KS(KP(x)) - KS(KS(x))| \le KP^{(3)}(x) + O(\log KP^{(3)}(x)),$$

поскольку разница сложностей двух чисел не превосходит префиксной сложности их разности. С другой стороны, в формулу для разности $KP(y) - KS(y)$ можно подставить $y = KP(x)$ и заключить, что

$$KP(KP(x)) - KS(KP(x)) = O(KP^{(3)}(x)).$$

Таким образом, все четыре варианта сложности сложности $x$ (комбинации простой и префиксной) отличаются друг от друга на $O(KP^{(3)}(x))$. В частности,

$$KP(KP(x)) - KS(KS(x)) = O(KP^{(3)}(x)),$$

и остаётся заметить, что из $|u - v| = O(KP(u))$ вытекает $|KP(u) - KP(v)| = O(\log KP(u))$. Таким образом, $KP(KP(x))$ и $KP(KS(KS(x)))$ «логарифмически близки», если под логарифмической близостью $a$ и $b$ понимать $|a - b| = O(\log a)$. Несложно проверить, что это отношение (логарифмической близости) симметрично и транзитивно (с точностью до увеличения константы в $O$-обозначении). Остаётся заметить, что $KS(v)$ и $KP(v)$ тоже логарифмически близки (при любом $v$, в том числе при $v = KS(KS(x)))$, так что по транзитивности $KP(KP(x)))$ и $KS(KS(KS(x)))$ также логарифмически близки и уж заведомо $O(KP^{(3)}(x))$ и $O(KS^{(3)}(x))$ — одна и та же точность.

Таким образом, мы получили и другое равенство Соловея из [161]:

**Теорема 74.**

$$KP(x) = KS(x) + KS(KS(x)) + O(KS^{(3)}(x)).$$

Другими словами, неравенство теоремы 65 (с. 118) оказывается близким к равенству.

**117** Дайте прямое доказательство оценки

$$KS(x) \le KP(x) - KP(KP(x)) + KP^{(3)}(x) + O(1),$$

оценив число слов, при которых правая часть мала.

[Указание. Мы видели (теорема 64, с. 117), что логарифм числа слов, для которых $KP(x) \le n$, не превосходит $n - KP(n) + c$ при некотором $c$ и при всех $n$. Кроме того, такие слова можно перечислять (при известном $n$), так что каждое такое слово можно восстановить, зная $n$ и порядковый номер слова в перечислении.
Этот порядковый номер мы будем записывать в виде двоичного слова ровно из $n - KP(n) + c$ битов (Добавив слева нули, если нужно). Имея такое слово, мы уже знаем $n - KP(n)$ (константу с считаем фиксированной), так что для задания $n$ достаточно задать ещё $KP(n)$, что можно сделать с помощью самоограниченного кода длиной $KP(KP(n))$. Приписав к этому коду упомянутый выше порядковый номер, мы получим (для любого слова $x$ с $KP(x) \le n$, в том числе для всех слов префиксной сложности $n$) слово длиной $KP(KP(n)) + n - KP(n) + c$, по которому мы можем эффективно восстановить слово $x$.]
# 5. Монотонная и априорная сложности и случайность

## 5.1. Вероятностные машины и полумеры на дереве

Определяя априорную вероятность в главе 4, мы рассматривали вероятностные алгоритмы (машины), которые на выходе печатали натуральное число и останавливались. Теперь мы рассмотрим другой класс вероятностных алгоритмов, которые выдают на выход бит за битом и не обязаны останавливаться. Алгоритм такого вида задаёт случайную величину, значениями которой являются элементы $\Sigma$ (конечные и бесконечные последовательности нулей и единиц).

В качестве примера рассмотрим алгоритм, выдающий на выходе случайные биты, получаемые от датчика:

```
while true do
    b := random;
    OutputBit(b);
od
```

Соответствующая случайная величина сосредоточена на бесконечных последовательностях (любое множество конечных последовательностей имеет вероятность нуль) и имеет там равномерное распределение. Но в общем случае конечные последовательности могут появляться с положительной вероятностью (это соответствует ситуации, когда алгоритм с некоторого момента новых битов не выдаёт).

Для каждого алгоритма А описанного типа рассмотрим функцию, определённую на двоичных словах и принимающую вещественные значения:

$$a(x) = \text{Pr}[\text{выход А начинается на x}].$$

Формально говоря, эту функцию надо определять так. Каждому вероятностному алгоритму А соответствует некоторое отображение $\tilde{A}$ множества $\Omega$ (бесконечные последовательности нулей и единиц) в множество $\Sigma$. Именно, $\tilde{A}(\omega)$ есть последовательность битов, которая получается на выходе, если использовать в качестве случайных битов члены последовательности $\omega$ (очередной вызов $b := random$ берёт следующий бит последовательности $\omega$). Для приведённой выше программы, очевидно, $\tilde{A}(\omega) = \omega$.

После этого $a(x)$ определяется как равномерная мера прообраза множества $\Sigma_x$ при отображении $\tilde{A}$ (где $\Sigma_x$ есть множество всех конечных и бесконечных последовательностей, начинающихся на слово $x$).
**118** Укажите отображение $\bar{A}$ и функцию $a$ для алгоритма А, который печатает на выходе бесконечную последовательность нулей (и не использует случайных битов).

В этом разделе мы опишем функции, соответствующие вероятностным алгоритмам указанного вида.

**Теорема 75.** Пусть А — вероятностный алгоритм описанного вида, а — соответствующая ему функция. Тогда:

(а) $a(x) \ge 0$ при всех $x$;

(б) $a(\Lambda) = 1$ (здесь $\Lambda$ обозначает пустое слово);

(в) $a(x) \ge a(x0) + a(x1)$ для любого слова $x$;

(г) функция $a$ перечислима снизу.

Перечислимость снизу определялась в разделе 4.1 (с. 88) для последовательностей действительных чисел. Для функций на словах определение аналогично: $a(x) = \lim_{i} a(x, i)$, где $a$ — вычислимая функция двух аргументов, $a(x, i)$ определено всех слов $x$ и для всех натуральных $i$, является рациональным числом (или специальным символом $-\infty$) и не убывает по $i$.

▲ Первые три утверждения очевидны:

(а) Вероятность всегда неотрицательна.

(б) $a(\Lambda) = 1$, поскольку пустое слово является началом любого выхода.

(в) $a(x) \ge a(x0) + a(x1)$, поскольку события «выход начинается на $x0$» и «выход начинается на $x1$» несовместны и являются подмножествами события «выход начинается на $x$».

Заметим, что неравенство пункта (в) не обязано быть равенством: разность

$$a(x) - a(x0) - a(x1)$$

есть вероятность того, что на выходе появится слово $x$ и больше никаких битов не появится.

(г) Чтобы доказать перечислимость снизу функции $a$, нам надо уметь получать приближения снизу к $a(x)$ для данного слова $x$. Будем моделировать поведение алгоритма А для всех возможных значений случайных битов. Время от времени будут обнаруживаться значения случайных битов, которые гарантируют появление на выходе слова $x$, то есть интервалы в пространстве $\Omega$, на которых функция $\bar{A}$ равна $x$ или какому-нибудь продолжению слова $x$. Вероятность $a(x)$ равна суммарной мере всех таких интервалов, и в качестве искомого приближения $a(x, i)$ мы берём меру интервалов, обнаруженных к шагу $i$. ►

Функции $a$, определённые на двоичных словах, принимающие действительные значения и удовлетворяющие условиям (а) – (г) теоремы 75, называют перечислимыми снизу полумерами на дереве (двоичных слов). Мы будем называть полумерами на дереве функции, удовлетворяющие условиям (а) – (в); условие (г) выделяет из них перечислимые снизу.

Важно не смешивать полумеры на дереве с ранее рассматривавшимися полумерами на натуральных числах (или на словах как изолированных конструктивных объектах): прежние полумеры соответствовали алгоритмам, которые выдавали на
выходе какое-либо число (или слово) и останавливались. Чтобы подчеркнуть различие, ранее рассматривавшиеся полумеры можно назвывать дискретными, а полумеры на дереве называть непрерывными.

**119** Показайте, что полумеры на дереве (функции со свойствами (а) – (в)) соответствуют мерам (в смысле теории меры) на пространстве Σ конечных и бесконечных последовательностей. Найдите меру множества всех бесконечных продолжений слова x при таком соответствии. [Ответ: если a — полумера на дереве, то мера этого множества равна пределу убывающей по n последовательности

$$ \alpha_n = \sum \{a(y) \mid y \text{ есть продолжение } x \text{ длины } n\}. $$

Здесь $\alpha_n$ определено при $n \ge l(x)$ и равно $a(x)$ при $n = l(x)$.

**120** Показайте, что для перечислимой снизу полумеры на дереве сумма $\sum_x a(x)$ может быть бесконечной. [Указание. Рассмотрите алгоритм, копирующий случайные биты на выход.]

Верно и обратное к теореме 75 утверждение:

**Теорема 76.** Всякая перечислимая снизу полумера на дереве соответствует некоторому вероятностному алгоритму.

◀ Идею доказательства легко объяснить в терминах выделения места, по аналогии с доказательством теоремы 46 (с. 91). Изменение состоит в том, что теперь запросы носят иерархический характер. Две организации (которые мы будем условно называть 0 и 1) требуют выделить им непересекающиеся подмножества в пространстве Ω (которое можно отождествить с отрезком [0, 1]), при этом размеры запрашиваемых ими областей увеличиваются со временем, но в сумме ни в какой момент не превышают единицы.

В каждой из организаций есть по два подразделения (в организации 0 есть подразделения 00 и 01, в организации 1 есть два подразделения 10 и 11), которые требуют выделения им места внутри области, выделенной для всей организации. При этом их требования тоже растут со временем, но для каждого момента времени в сумме не превышают требований всей организации (в тот же момент). Аналогично для ещё более мелких подразделений 000, 001 и так далее: в пределе каждое подразделение х требует выделить (не обязательно сплошной) участок, имеющий размер $a(x)$, где $a$ — заданная полумера. При этом однажды выделенная любому подразделению область навсегда остаётся за ним и перераспределена быть не может.

Соответствие между этой схемой выделения места и вероятностным алгоритмом таково: если последовательность случайных битов попадает в область, выделенную подразделению х, это означает, что выход алгоритма начинается с х (для данной последовательности случайных битов).

Представив себе описанную ситуацию, легко понять, что такое распределение осуществимо. Тем не менее мы приведём более формальное рассуждение (одновременно объясняя смысл его этапов с точки зрения описанной метафоры).

**Лемма 1.** Пусть $a$ — произвольная перечислимая снизу полумера на дереве. Тогда существует вычислимая всюду определённая неубывающая по $i$ функция $\langle x, i \rangle \mapsto a(x, i)$, аргументами которой являются двоичное слово $x$ и натуральное
число i, значения которой — неотрицательные двоично-рациональные числа, $\lim_i a(x, i) = a(x)$ и для каждого i функция $x \mapsto a(x, i)$ является полумерой, у которой лишь конечное число значений отлично от нуля.

Другими словами, можно считать, что на каждом шаге запросы на выделение места подчиняются дополнительным ограничениям:

* запрашиваемые размеры двоично-рациональны (имеют вид $k/2^n$ для некоторых целых $k$ и $n$);

* лишь конечное число подразделений имеет ненулевые запросы;

* запросы согласованы (запрос любого подразделения не меньше суммы запросов его частей).

**Доказательство.** Будем постепенно корректировать функцию $a$ из определения перечислимой снизу полумеры (не меняя самой предельной полумеры). Сначала добьёмся, чтобы все значения были двоично-рациональными. Это можно сделать, заменив $a(x, i)$ на ближайшее снизу двоично-рациональное число со знаменателем $2^i$ (отрицательные числа заменяем на нули).

Затем можно добиться выполнения второго условия, положив $a(x, i) = 0$ для слов х длины больше $i$.

Наконец, можно добиться выполнения третьего условия, выполнив замену

$$a(x, i) := \max(a(x, i), a(x0, i) + a(x1, i))$$

последовательно в порядке убывания длин слов. Поскольку функция $a(x)$ является полумерой по предположению, такие замены сохранят неравенство $a(x, i) \le a(x)$. Легко проверить, что значения полумеры (пределы $\lim_i a(x, i)$ при каждом $x$) при нашей коррекции не изменятся. Лемма 1 доказана.

Следующую лемму удобно формулировать, введя несколько вспомогательных определений. Будем называть полумеру с конечным числом ненулевых двоично-рациональных значений «простой» полумерой.

Будем называть «простым множеством» объединение конечного числа интервалов в $\Omega$. (Напомним, что интервал в $\Omega$ есть множество вида $\Omega_z$, состоящее из всех бесконечных продолжений данного слова $z$. Таким образом, простыми являются множества, принадлежность к которым определяется конечным числом битов последовательности.)

Будем называть «простым семейством» семейство простых множеств $A_x$, индексированное двоичными словами $x$, в котором все множества, кроме конечного числа, пусты, и для каждого слова $x$ множества $A_{x0}$ и $A_{x1}$ являются непересекающимися подмножествами множества $A_x$. Для такого семейства функция $x \mapsto \mu(A_x)$, где $\mu$ — равномерная мера на $\Omega$, является простой полумерой.

**Лемма 2.** Для всякой простой полумеры существует простое семейство, которому она соответствует.

**Доказательство.** Начнём строить такое семейство, начиная с пустого слова и постепенно увеличивая длину слова-индекса. На каждом шаге нам нужно будет внутри простого множества $A_x$ найти два непересекающихся простых подмножества $A_{x0}$ и $A_{x1}$ заданных мер (при этом сумма этих мер не превосходит меры объемлющего множества). Ясно, что это возможно. Лемма 2 доказана.
**Лемма 3.** Пусть дана простая полумера $b(x)$ и соответствующее ей простое семейство $B_x$. Пусть дана также простая полумера $c$, причём $c(x) \ge b(x)$ для всех $x$. Тогда можно построить простое семейство $C_x$, соответствующее полумере $c$, для которого $C_x \supset B_x$ при всех $x$.

**Доказательство.** Повторим рассуждение из доказательства леммы 2, только теперь внутри простого множества есть два непересекающихся простых подмножества, и надо увеличить их меры до заданных значений, оставив подмножества непересекающимися и не выйдя за пределы множества. Ясно, что это возможно. Лемма 3 доказана.

Доказательства лемм 2 и 3 эффективны в том смысле, что по таблицам значений простых полумер можно алгоритмически построить соответствующие простые семейства.

Будем теперь применять лемму 3 по очереди к простым полумерам, получающимся фиксацией $i = 0, 1, 2, \dots$ в $a(x, i)$. Получим двупараметрическое семейство простых множеств $U(x, i)$, при этом

* описание множества $U(x, i)$ (список входящих в него интервалов) строится алгоритмически по $x$ и $i$;

* мера множества $U(x, i)$ равна $a(x, i)$ (и стремится к $a(x)$ при $i \to \infty$);

* при любых $x$ и $i$ множества $U(x0, i)$ и $U(x1, i)$ являются непересекающимися подмножествами множества $U(x, i)$;

* $U(x, i) \subset U(x, i+1)$ при любых $x$ и $i$.

Теперь искомый вероятностный алгоритм, порождающий полумеру $a$, можно построить так: строим множества $U(x, i)$ при всех $x$ и $i$ параллельно запрашиваем случайные биты, записывая их в последовательность $\omega$. Как только обнаруживается, что $\omega \in U(x, i)$ для каких-то $x$ и $i$, выдаём на выход ещё не выданные биты слова $x$.

Заметим, что если последовательность $\omega$ оказалась в $U(x, i)$, то она автоматически оказывается в $U(y, i)$ для любого начала у слова $x$. Заметим также, что $\omega$ не может оказаться одновременно в $U(x, i)$ и $U(x', i)$ для несовместных слов $x$ и $x'$ (слов, не являющихся началами друг друга). Поэтому уже выданные на выход биты не потребуется «отзывать».

Слово $x$ или его продолжение появится на выходе такого алгоритма тогда и только тогда, когда последовательность $\omega$ принадлежит объединению возрастающей последовательности множеств $U(x, i)$ при $i = 0, 1, 2, \dots$; вероятность этого события есть предел мер множеств $U(x, i)$, а этот предел совпадает с $a(x)$, что и требовалось. ►

**Теоремы 75 и 76.** Показывают, что перечислимые снизу полумеры на дереве можно эквивалентно определить как функции, соответствующие распределениям на выходе вероятностных алгоритмов.

Среди всех вероятностных алгоритмов описанного вида выделяются алгоритмы, которые почти наверно выдают бесконечную последовательность (вероятность получить конечную последовательность равна нулю). Им соответствуют полумеры, являющиеся вычислимыми мерами. Точнее говоря, верна следующая теорема:
**Теорема 77.** (а) Пусть $\mu$ — вычислимая мера на пространстве $\Omega$. Тогда функция $p$, определяемая формулой $p(x) = \mu(\Omega_x)$, является перечислимой снизу полумерой, причём $p(x) = p(x0) + p(x1)$ для всех х.

(б) Если для перечислимой снизу полумеры $p$ выполнено равенство $p(x) = p(x0) + p(x1)$ при всех х, то она определяет некоторую вычислимую меру на $\Omega$.

Напомним, что мы включаем в определение полумеры условие $p(\Lambda) = 1$; без этого, или хотя бы без вычислимости $p(\Lambda)$, второе утверждение теоремы перестаёт быть верным.

◀ (а) Если действительное число $\alpha$ вычислимо, и $a_n$ — рациональное приближение к нему с ошибкой $1/n$, то $b_n = a_n - 1/n$ будет приближением снизу с ошибкой $2/n$. Вообще говоря, последовательность $b_n$ может не быть монотонной (неубывающей), но последовательность

$$c_n = \max(b_0, b_1, \dots, b_n)$$

заведомо будет вычислимой неубывающей последовательностью рациональных чисел, стремящейся к $\alpha$. Таким образом, каждое вычислимое действительное число перечислимо снизу. Проводя эту конструкцию параллельно для всех х, мы убеждаемся, что любая вычислимая мера задаёт перечислимую снизу полумеру. Поскольку $\Omega_x$ есть объединение непересекающихся подмножеств $\Omega_{x0}$ и $\Omega_{x1}$, то $p(x) = p(x0) + p(x1)$ (аддитивность меры).

(б) Пусть $p$ — перечислимая снизу полумера, для которой $p(x) = p(x0) + p(x1)$ при всех х. Покажем индукцией по длине х, как найти приближение к $p(x)$ с любой заданной точностью. Для пустого слова значение $p(\Lambda)$ равно 1 по определению. Если мы уже умеем находить приближения к $p(x)$ сверху и снизу с любой точностью, а хотим сделать это для $p(x0)$ и $p(x1)$, то надо ждать, пока сумма постепенно растущих нижних оценок для $p(x0)$ и $p(x1)$ не приблизится к (убывающей) верхней оценке для $p(x)$. Другими словами, верхние оценки для $p(x1)$ можно получить, вычитая из верхних оценок для $p(x)$ (которые возможны по предположению индукции) нижние оценки для $p(x0)$. ►

Эту теорему можно интерпретировать следующим образом. Пусть нам нужен датчик случайных чисел, который выдаёт последовательность нулей и единиц, распределённую по некоторой вычислимой мере $p$ (вероятность того, что выдаваемая датчиком последовательность начинается на х, должна быть равна $p(x)$). Тогда теоремы 76 и 77 говорят, что такой датчик можно построить в виде вероятностного алгоритма, который внутри себя имеет равномерный датчик, а на выходе имеет нужное распределение.

Заметим, что в частном случае вычислимых мер можно воспользоваться более простой и явной конструкцией, чем дана в доказательстве теоремы 76. А именно, разобьём отрезок $[0, 1]$ на две части длиной $p(0)$ и $p(1)$. Первую из них разобьём ещё на две части длиной $p(00)$ и $p(01)$, вторую — на части длиной $p(10)$ и $p(11)$ и так далее. Для каждого двоичного слова $z$ получится некоторый отрезок $\pi_z$ длиной $p(z)$; отрезки $\pi_z$ для всех слов $z$ данной длины образуют разбиение отрезка $[0, 1]$.
Теперь рассмотрим вероятностный алгоритм, который бросает честную монету и получает последовательность $\alpha$ случайных битов. Эта последовательность рассматривается как двоичное разложение некоторого числа (которое мы тоже будем обозначать $\alpha$). Параллельно с получением $\alpha$ алгоритм ищет такие $z$, при которых $\alpha$ содержится строго внутри $\pi_z$ (и это можно сказать на основе уже имеющейся информации о $\alpha$ и о границах отрезков $\pi_z$, которые параллельно вычисляются с возрастающей точностью).

Возникающие при этом слова $z$ являются началами друг друга (чем больше битов числа $\alpha$ известно, тем длиннее может быть $z$). Они являются началами последовательности битов, которая выдаётся на выход.

Вообще говоря, алгоритм этот может дать конечную последовательность, если число $\alpha$ совпадёт с концом одного из отрезков $\pi_z$, но таких концов счётное множество, и вероятность этого события равна 0. Выход алгоритма начинается на $z$ тогда и только тогда, когда число $\alpha$ содержится строго внутри $\pi_z$, так что вероятности правильные.

Говоря более формально, описанное преобразование $T$ последовательности битов $\alpha$ в выходную последовательность битов $\beta = T(\alpha)$ переводит равномерную меру в меру $p$.

(Ничего неожиданного в этом алгоритме нет. Если у вас есть датчик случайных равномерно распределённых на $[0, 1]$ чисел, а нужно имитировать несимметричную монету, где 0 и 1 имеют вероятности, скажем, $2/3$ и $1/3$, то надо сравнить случайную точку с границей $2/3$. Для получения второго бита с тем же распределением надо каждый из отрезков $[0, 2/3]$ и $[2/3, 1]$ снова разделить на неравные части в пропорции 2 : 1. Ровно это и делается в описанном алгоритме.)

Теорема 76 показывает, что достаточно иметь «честную монету», то есть генератор независимых случайных равномерно распределённых битов, чтобы (с помощью алгоритмического преобразования) порождать последовательности битов с произвольным вычислимым распределением и даже по произвольной перечислимой снизу полумере. Можно ещё отметить, что выбор равномерного распределения (честной монеты) в качестве источника случайности не принципиален:

**121** Покажите, что в теореме 75 можно заменить равномерную меру на любую вычислимую меру и даже полумеру. [Указание: композиция двух алгоритмических преобразований последовательностей также является алгоритмическим преобразованием.]

**122** Покажите, что в теореме 76 можно использовать вместо равномерной меры любую вычислимую меру, в которой каждая отдельная последовательность имеет нулевую вероятность. [Указание. Вычислимую меру $P$ можно преобразовать в равномерную, если при получении $z$ от $P$-датчика выдавать на выход биты слова $x$, для которого отрезок $\pi_z$ целиком содержится внутри отрезка $I_x$ (чисел, двоичные разложения которых начинаются на $x$).]

Условие в этой задаче необходимо: если некоторая бесконечная последовательность имеет положительную меру, то значение отображения $\bar{A}$ на этой последовательности имеет положительную вероятность, и равномерной меры не получится.
Но если этого препятствия нет, то датчик с любым известным заранее вычислимым распределением может заменить равномерный.

Вопрос о том, что можно сделать, если заранее распределение неизвестно, рас-
сматривается при построении экстракторов случайности; разумные постановки его
возможны и в классической теории вероятностей, и в терминах колмогоровской
сложности. См. краткий обзор А. Вигдерсона [190] и приводимые там ссылки, а
также обзор М. Зиманда о сложностных постановках задачи [195]. Мы не затраги-
ваем этих вопросов в нашей книге.

5.2. Наибольшая перечислимая полумера на дереве

Теорема 78. Среди всех перечислимых снизу полумер на дереве существует наибольшая (с точностью до константы) полумера а: для любой перечислимой снизу полумеры а' на дереве выполнено неравенство а'(x) ≤ ca(x) для некоторой константы с и для всех х.

◀ Как и для полумер на $\mathbb{N}$ (теорема 47, с. 93), рассмотрим вероятностный алгоритм $A$, который сначала случайно выбирает некоторый вероятностный алгоритм, а затем моделирует выбранный алгоритм. Если полумера $a'$ соответствует вероятностному алгоритму $A'$, то $a'(x) \le (1/\varepsilon)a(x)$, где $\varepsilon$ — вероятность того, что будет выбран именно алгоритм $A'$. ▶

Другой способ доказательства состоит в том, что мы располагаем все перечислимые снизу полумеры в вычислимую последовательность $a_0, a_1, \dots$, а затем рассматриваем полумеру $a = \sum_i \lambda_i a_i$, где $\lambda_i$ — ряд с вычислимыми членами и суммой 1 (например, $\lambda_i = 2^{-i-1}$).

Тонкость здесь в том, что надо построить вычислимую последовательность всех полумер, то есть перечислимую снизу функцию $u(i, x)$, для которой: (1) при каком фиксированном $i$ функция $u_i: x \mapsto u(i, x)$ является полумерой; (2) среди $u_i$ содержатся все перечислимые снизу полумеры.

Это можно сделать, либо перечисляя все вероятностные алгоритмы (что соответствует ранее приведённому доказательству), либо принудительно корректируя программы так, чтобы они перечисляли полумеры. Это рассуждение аналогично случаю дискретных полумер (раздел 4.2, страница 93), и мы не будем приводить детали. (Скажем лишь, что в случае нарушения условия $p(x) \ge p(x0) + p(x1)$ надо увеличивать $p(x)$, если только это не приведёт к тому, что $p(\Lambda)$ станет больше единицы.)

123 Проведите это рассуждение подробно.

(Замечание в скобках: доказательство теоремы 78 даёт даже немного больше, чем утверждается. А именно, не только вероятность появления слова с началом х (то есть $p(x)$), но и вероятность появления на выходе в точности слова х, то есть разность $p(x) - p(x0) - p(x1)$, для построенной «универсальной» машины больше, чем для любой другой.)

124 Покажите, что всё сказанное выше естественно переносится на вероят-
ностные алгоритмы, которые выдают на выход (по одному) не биты, а натуральные
числа (каждое число выдаётся как единое целое). Такие алгоритмы соответствуют перечислимым снизу мерам на пространстве конечных и бесконечных последовательностей натуральных чисел.

**125** (Продолжение.) Пусть $m$ — наибольшая перечислимая снизу полумера на пространстве конечных и бесконечных последовательностей натуральных чисел. Покажите, что её ограничение на последовательности длины $1$ даёт априорную вероятность на натуральных числах в смысле главы 4, а её ограничение на двоичные слова даёт наибольшую полумеру на двоичном дереве (в смысле теоремы 78).

**126** Покажите, что $a(0^n1)$ и $m(n)$ отличаются не более чем на ограниченный множитель, если $a$ — максимальная полумера из теоремы 78, а $m(n)$ — априорная вероятность натурального числа $n$ в смысле главы 4. (Здесь вместо $0^n1$ можно взять любое беспрефиксное кодирование натуральных чисел.) [Указание: см. далее теорему 79.]

Фиксируем некоторую наибольшую перечислимую снизу полумеру на дереве и обозначим её $a(x)$. Её также называют универсальной полумерой на дереве. Величину $a(x)$ можно было бы назвать априорной вероятностью слова $x$ (как элемента дерева), но важно не путать её с априорной вероятностью в смысле главы 4. Чтобы различать эти два понятия, можно говорить о дискретной и непрерывной априорных вероятностях. Величину

$$KA(x) = -\log a(x)$$

будем называть априорной сложностью слова $x$. (Здесь можно не опасаться путаницы, так как в главе 4 аналогичное определение приводило к префиксной сложности и специальное наименование излишне.) Различные варианты выбора наибольшей полумеры приводят к разным функциям априорной сложности, но они отличаются друг от друга не более чем на аддитивную константу (поскольку различные наибольшие полумеры на дереве отличаются не более чем в константу раз).

В англоязычной литературе для априорной сложности иногда используется обозначение $KM(x)$ (а монотонная сложность, которую мы так обозначаем, обозначается $Km(x)$ или $K_m(x)$).

В следующем разделе мы изучим свойства априорной сложности. Заметим сразу же, что формально по нашему определению априорная сложность может не быть целым (и даже рациональным) числом. Но поскольку большинство интересующих нас утверждений всё равно формулируются «с точностью до $O(1)$», то можно было бы заменить $-\log a(x)$ на минимальное число $n$, при котором $2^{-n} < a(x)$. Тут есть небольшая тонкость: мы используем строгое неравенство, чтобы получаемая функция была перечислила сверху. В дальнейшем мы специально оговариваем те редкие случаи, когда это округление (или его отсутствие) существенно.

## 5.3. Свойства априорной сложности

**Теорема 79.** (а) Априорная сложность монотонна: если $x$ есть начало у, то $KA(x) \le KA(y)$;
(б) $KA(x) \le l(x) + O(1)$ для любого х;

(в) $KA(x) \le KP(x) + O(1)$ для любого х;

(г) если $x_0, x_1, \dots$ — вычислимая последовательность несравнимых слов (ни одно из них не является началом другого), то $KA(x_i) = KP(x_i) + O(1) = KP(i) + O(1)$;

(д) $KP(x) \le KA(x) + 2\log l(x) + O(1)$;

(е) более того, $KP(x) \le KA(x) + KP(l(x)) + O(1)$;

(ë) и более того, $KP(x|I(x)) \le KA(x) + O(1)$;

(ж) бесконечная последовательность нулей и единиц вычислима тогда и только тогда, когда априорная сложность её начальных отрезков ограничена;

(з) если $f: \Sigma \to \mathbb{N}_\perp$ — вычислимое непрерывное отображение, то $KP(f(x)) \le KA(x) + O(1)$ для любого слова х, на котором $f(x)$ определено (не равно $\perp$).

▲ (а) Мера подмножества не превосходит меры множества.

(б) Функция $p(x) = 2^{-l(x)}$ является перечислимой снизу полумерой на дереве, и потому $p(x) \le ca(x)$ для некоторого с.

(в) Машины, которые выдают двоичное слово (как единое целое) и останавливаются, можно рассматривать как частный случай машин, выдающих последовательности битов. Поэтому $m(x) \le ca(x)$, где $m$ — априорная вероятность в смысле главы 4, откуда и следует требуемое.

Поучительно провести это рассуждение в терминах полумер. Положим $m'(x)$ равным сумме $m(y)$ по всем продолжениям у слова $x$, где $m$ — дискретная априорная вероятность. (Ешё положим в порядке исключения $m'(\Lambda) = 1$.) Тогда $m'$ будет полумерой на дереве и потому $m(x) \le m'(x) = O(a(x))$.

(г) Если $x_i$ — вычислимая последовательность несравнимых двоичных слов, а $a$ — априорная вероятность на дереве (универсальная полумера на дереве), то функция $i \mapsto a(x_i)$ является полумерой на $\mathbb{N}$. В самом деле, она перечислима снизу, а события «$x_i$ появляется на выходе вероятностного алгоритма» несовместны, и потому сумма их вероятностей не превосходит единицы. Поэтому $KP(i) \le KA(x_i) + O(1)$.

С другой стороны, $KP(x_i) = KP(i) + O(1)$, поскольку из $i$ можно алгоритмически получить $x_i$ и наоборот; наконец, $KA(x_i) \le KP(x_i) + O(1)$ согласно (в).

(д) Пусть $a$ — априорная вероятность на дереве. Рассмотрим перечислимую снизу функцию $u(x) = a(x)/l(x)^2$. Сумма значений $a(x)$ по всем словам длины $n$ не превосходит 1, поскольку эти слова попарно несравнимы, поэтому

$$ \sum_x u(x) = \sum_n \sum_{l(x)=n} \frac{a(x)}{n^2} \le \sum_n \frac{1}{n^2} = O(1), $$

откуда и следует требуемое.

(е) доказывается аналогично, только надо положить $u(x) = a(x)m(l(x))$, где $m$ — априорная вероятность на $\mathbb{N}$.

(ë) Рассмотрим функцию

$$ u(x, n) = \begin{cases} a(x), & \text{если } l(x) = n, \\ 0, & \text{если } l(x) \ne n. \end{cases} $$
При каждом $n$ функция $x \mapsto u(x, n)$ является полумерой в смысле предыдущей главы (сумма не превосходит 1), откуда и следует требуемое.

(ж) Для данной бесконечной вычислимой последовательности $\omega$ нулей и единиц рассмотрим вероятностный (по форме) алгоритм, который не использует датчика случайных чисел и печатает один за другим биты последовательности $\omega$. Соответствующая полумера равна 1 на любом начале последовательности, и потому априорные вероятности (мы рассматриваем априорную вероятность на дереве) всех этих начал отделены от нуля.

Обратное рассуждение несколько сложнее. Пусть априорные вероятности всех начал последовательности $\omega$ больше некоторого рационального $\varepsilon > 0$. Рассмотрим множество $B$ всех двоичных слов, для которых $a(x) > \varepsilon$. Множество $B$ содержит все начала последовательности $\omega$. Оно является деревом (вместе с любым словом содержит все его начала). Кроме того, любое его подмножество, состоящее из попарно несравнимых слов, содержит не более $1/\varepsilon$ элементов (поскольку соответствующие события не пересекаются и их суммарная вероятность не больше 1). Наконец, $B$ перечислимо (строя приближения снизу к $a(x)$, мы рано или поздно обнаружим любое $x$, для которого $a(x) > \varepsilon$).

Этих свойств уже достаточно, чтобы заключить, что последовательность $\omega$ вычислима. В самом деле, рассмотрим максимально возможное число попарно несравнимых слов $x_1, \dots, x_N$ из $B$. Для каждого из слов $x_i$ рассмотрим все его продолжения, лежащие в $B$. Все они сравнимы (иначе можно было бы заменить $x_i$ на два несравнимых продолжения и увеличить $N$). Поэтому в дереве $B$ из каждого $x_i$ выходит конечная или бесконечная ветвь без ветвлений, и эта ветвь вычислима (поскольку можно перечислять множество $B$). Последовательность $\omega$ является одной из таких ветвей (если бы $\omega$ не проходила ни через одно из слов $x_i$, то её достаточно длинное начало можно было бы добавить к списку несравнимых слов и увеличить $N$).

(з) Построим вероятностную машину в смысле главы 4, применяя $f$ к выходу вероятностной машины, соответствующей наибольшей перечислимой полумере на дереве, и сравним результат с наибольшей перечислимой полумерой на $N$ (логарифм которой равен $KP+O(1)$). ►

Отметим, что априорная сложность отличается по своим свойствам от уже знакомых нам (обычной и префиксной) сложностей. Прежде всего, её определение использует структуру начал на множестве двоичных слов, и потому алгоритмические преобразования, не сохраняющие этой структуры, могут увеличивать сложность более чем на константу.

**127** Покажите, что априорная сложность слова $x$ может быть ограниченной, а сложность слова $x^R$ (те же биты в обратном порядке) — сколь угодно большой. (Формально: существует такое $c$, что для любого $n$ найдётся слово $x$ с $KA(x) < c$ и $KA(x^R) > n$.) [Указание: слово $x$ может начинаться с единицы, за которой идут нули.]

Тем самым нет смысла (в отличие от префиксной и обычной сложностей) говорить об априорной сложности, скажем, натурального числа или графа.
Априорная сложность слова длины $n$ отличается от уже известных нам вариантов сложностей не более чем на $O(\log n)$, но здесь важно, что под логарифмом стоит именно длина слова, а не его сложность, поскольку, скажем, для слов из одних нулей априорная сложность ограничена, а обычная и префиксная — нет.

**128** Докажите, что для любого слова $x$ хотя бы одно из чисел $KA(x0)$ и $KA(x1)$ не меньше $KA(x) + 1$. (Здесь существенно, что $KA(x)$ определено как $-\log a(x)$ без округления.) Выведите отсюда, что для любого слова $x$ и числа $n \in \mathbb{N}$ можно найти слово $u$ длины $n$, для которого $KA(xy) \ge KA(x) + n$. Покажите, что существует бесконечная двоичная последовательность $\omega$, у которой априорная сложность любого начала не меньше его длины.

(Ср. теорему 71 на с. 129 и задачу 46 на с. 52; заметим, что здесь нет условия $n$ и даже константы $O(1)$.)

**129** Покажите, что разности $KS(x) - KA(x)$ и $KA(x) - KS(x)$ могут быть порядка $\log n$ для некоторых слов длины $n$ (и для сколь угодно больших $n$). [Указание. $KS(x)$ будет больше $KA(x)$, если взять слово из одних нулей. Обратное соотношение имеет место для начал последовательности из предыдущей задачи, у которых $KA(x) = l(x) + O(1)$, а сложность $KS(x)$ бывает меньше длины примерно на логарифм длины, см. задачу 54.]

**130** Докажите, что

$$KA(xy) \le KP(x) + KA(y) + O(1),$$

где $xy$ — соединение слов $x$ и $y$. Здесь существенно, что речь идёт о соединении именно в таком порядке: покажите, что для другого порядка это неверно. [Указание. Пусть $U$ — вероятностный алгоритм в смысле главы 4, порождающий наибольшую перечислимую снизу полумеру (дискретную), а $V$ — вероятностный алгоритм в смысле этой главы, порождающий наибольшую полумеру на дереве. Рассмотрите алгоритм, который вначале действует как $U$, а после остановки продолжает работу как $V$ (используя свежие случайные биты и добавляя биты к уже выданным). Чтобы показать, что для $KA(ux)$ аналогичная оценка места не имеет, положите $y = 0^n$ и $x = 1$.]

Ещё одно свойство априорной сложности непосредственно следует из определения. Пусть дана произвольная вычислимая мера $\mu$ на пространстве $\Omega$. Тогда для некоторой константы $c$ и для всех слов $x$ выполняется неравенство

$$KA(x) \le -\log \mu(\Omega_x) + c.$$

В самом деле, априорная вероятность на дереве не меньше меры $\mu$ (и даже любой другой перечислимой снизу полумеры) с точностью до ограниченного множителя, что после логарифмирования и даёт требуемое неравенство.

Мы обращаем внимание на это (простое) свойство, поскольку на случайна по вычислимой мере $\mu$ тогда и только тогда, когда для её начальных отрезков $x$ это неравенство превращается в равенство, то есть когда разница $-\log \mu(\Omega_x) - KA(x)$
ограничена сверху (снизу она всегда ограничена в силу только что рассмотренного свойства).

Этот критерий является следствием теоремы Левина-Шнорра (критерий слу-
чайности в терминах монотонной сложности) и будет доказан вместе с ней в раз-
деле 5.6. Но прежде нам необходимо дать определение монотонной сложности
(раздел 5.5), для чего подробнее рассмотреть понятие вычислимого отображения
пространства $\Sigma$ в себя (раздел 5.4).

Можно охарактеризовать априорную сложность и как минимальную перечисли-
мую сверху функцию, удовлетворяющую некоторым условиям — подобно тому,
как это сделано в теореме 8 (с. 29) для простой сложности и в теореме 62 (с. 116)
для префиксной сложности. А именно, справедлива следующая теорема:

**Теорема 80.** Функция *КА* является минимальной с точностью до константы перечислимой сверху функцией *К* с таким свойством:

$$
\sum_{x \in M} 2^{-K(x)} \le 1
$$

для любого множества М попарно несравнимых двоичных слов.

◀ Поскольку слова $x \in M$ несравнимы, соответствующие множества $\Sigma_x$ не пересекаются и вероятности попадания в них в сумме не превосходят единицы.

С другой стороны, пусть дана произвольная перечислимая сверху функция K, обладающая указанным в теореме свойством. Нам нужно определить перечислимую снизу полумеру, которая была бы не меньше (перечислимой снизу) функции 2⁻^K. Заметим, что функция 2⁻^K не обязана быть полумерой, её значения на словах x, x0 и x1, вообще говоря, никак не связаны. Поэтому её надо увеличить — в той мере, в которой это неизбежно. А именно, положим u(x) равным точной верхней грани всех сумм вида

$$
\sum_{y \in M} 2^{-K(y)}
$$

по всем множествам *M* попарно несравнимых продолжений слова *x*. Легко проверить, что *u(x)* действительно будет перечислимой снизу полумерой и будет не меньше 2⁻$K(x)$, что и требовалось. ►

131. Будем рассматривать функции $b: \Xi \to [0, 1]$, обладающие следующим свойством: существует мера $\mu$ на $\Omega$, для которой $b(x) \le \mu(\Omega_x)$ при всех $x$.

(а) Докажите, что любая полумера на дереве обладает этим свойством.

(б) Докажите, что любая перечислимая снизу функция, обладающая этим свойством, мажорируется некоторой перечислимой снизу полумерой на дереве.

5.4. Вычислимые отображения Σ → Σ

В главе 4 мы рассматривали префиксную сложность, определённую в терминах кратчайших описаний, и априорную вероятность, определённую в терминах вероятностных машин — и одно оказалось логарифмом другого (плос O(1)).

В этой главе мы рассмотрели другой вариант априорной вероятности, и воз-
никает естественный вопрос: какая сложность ей соответствует? Такая сложность
действительно может быть естественно определена и называется монотонной сложностью, правда, она уже не совпадает с логарифмом априорной вероятности на дереве. Но её определение (см. далее раздел 5.5) требует некоторой подготовки, которой и посвящён этот раздел.

Алгоритмы (машины), рассматриваемые нами при определении априорной вероятности (универсальной полумеры) на дереве, состоят из двух частей: датчика случайных чисел, порождающего последовательность случайных битов, и алгоритма, который порождает выходные биты, используя эту последовательность. Сейчас мы изучим подробнее эту вторую составляющую, введя понятие вычислимого отображения пространства Σ (конечных и бесконечных последовательностей нулей и единиц) в себя. Отметим, что мы рассматриваем отображения, определённые на всём Σ (зато среди значений может быть пустое слово, что в некотором смысле заменяет неопределённость).

### 5.4.1. Непрерывные отображения Σ → Σ

Пусть дано отображение $f: Σ \to Σ$, определённое на всём Σ. Мы будем называть его *непрерывным*, если выполнены два свойства:

(1) оно монотонно: если $x \in Σ$ является началом $y \in Σ$, то $f(x)$ является началом $f(y)$;

(2) значение отображения $f$ на бесконечной последовательности $\omega$ является объединением (наимененным общим продолжением) значений $f(x)$ на всех конечных началах $x$ последовательности $\Omega$.

Мы будем использовать обозначение $x \leqslant y$ для отношения «x является началом y»; предполагается, что $x, y \in Σ$ могут быть и конечными, и бесконечными. Если $x \leqslant y$ для бесконечной последовательности $x$, то $x = y$. Требование (1) представляет собой монотонность $f$ с точки зрения частичного порядка $\leqslant$ на $Σ$. Оно гарантирует, что значения $f(x)$ на конечных началах $x$ последовательности $\omega$ будут продолжать друг друга; их объединение (точная верхняя грань в смысле $\leqslant$-порядка) согласно требованию (2) должно совпадать с $f(\omega)$.

132 Показите, что это определение соответствует стандартному понятию непрерывности для отображений топологических пространств, если $Σ$ снабдить топологией раздела 4.4.3 (с. 104). [Указание: ср. аналогичный результат для непрерывных отображений пространства $Σ$ в $N_⊥$ в том же разделе.]

С каждым непрерывным отображением $f: Σ \to Σ$ свяжем множество $Γ_f$, которое естественно назвать *подграфиком* отображения $f$; его элементами являются пары слов $(x, y)$, где $x, y$ конечные слова, для которых $y \leqslant f(x)$. Имеет место следующее простое наблюдение: для любого непрерывного $f$ множество $Γ_f$ обладает следующими тремя свойствами:

(1) $\langle x, Λ \rangle \in Γ_f$ для любого слова $x$;

(2) если $\langle x, y \rangle \in Γ_f$, то $\langle x', y' \rangle \in Γ_f$ при любых $x' \geqslant x, y' \leqslant y$;

(3) если $\langle x, y_1 \rangle$ и $\langle x, y_2 \rangle$ принадлежат $Γ_f$, то слова $y_1$ и $y_2$ сравнимы (одно из них является началом другого).
Первые два свойства очевидны, третье следует из того, что два слова, являющиеся началами конечной или бесконечной последовательности, сравнимы. Следующая теорема показывает, что непрерывные отображения однозначно задаются своими подграфиками.

**Теорема 81.** Соответствие $f \mapsto \Gamma_f$ является взаимно однозначным соответствием между непрерывными отображениями $\Sigma \to \Sigma$ и множествами пар слов, обладающими свойствами (1)-(3).

Пусть дано множество $F$ пар слов, обладающее свойствами (1)-(3). Требования (1)-(3) гарантируют, что для любого слова $x$ множество тех у, при которых $\langle x, y \rangle \in F$, непусто и состоит из сравнимых слов. Их объединение (точную верхнюю грань) и будем считать значением $f(x)$. Свойство (2) гарантирует, что $x \le x'$ влечёт $f(x) \le f(x')$ (с ростом $x$ рассмотренное множество слов у также растёт). Тем самым можно корректно определить $f(\omega)$ как объединение $f(x)$ для всех слов $x \le \omega$. Построенное отображение $f$ будет непрерывно в смысле данного выше определения. Легко проверить, что построенное соответствие $F \mapsto f$ обратно к $f \mapsto \Gamma_f$. ►

Непрерывное отображение $f: \Sigma \to \Sigma$ будем называть вычислимым, если соответствующее множество $\Gamma_f$ перечислимо. (Вычислимые отображения по определению всегда непрерывны.)

Формально нам не требуется никакого «оправдания» для этого определения, и всё сказанное далее о «машинно-автоматной» интерпретации вычислимых отображений нигде не потребуется. Тем не менее поучительно понять, какому виду машин (программ) соответствует такое определение.

### 5.4.2. Монотонные машины с неблокирующим чтением

Будем рассматривать программы, которые используют неблокирующее чтение со входа (можно прочесть очередной бит из очереди входных битов и проверить, пуста ли эта очередь). Такие программы подробно обсуждались в разделе 4.4.2, с. 102. Но теперь будем считать, что машина строит выход по битам, имея команду OutputBit($b$) с битовым аргументом.

Выходная последовательность такой программы может быть конечной или бесконечной, и зависит, вообще говоря, не только от входной последовательности битов (нажатых клавиши «0» и «1»), но и от моментов нажатия клавиши. Будем называть программу корректной, если такой зависимости нет (моменты нажатия клавиши могут влиять на моменты появления битов на выходе, но не на выходную последовательность). Корректная программа задёт некоторое отображение множества $\Sigma$ в себя.

**Теорема 82.** Любая корректная программа задёт вычислимое отображение (в описанном выше смысле); всякое вычислимое отображение может быть задано некоторой корректной программой.

Пусть имеется некоторая корректная программа $M$ и две входные последовательности $x$ и $x'$, причём $x \le x'$. Покажем, что $M(x) \le M(x')$, где через $M(z)$ обозначается выход программы $M$ на входе $z$ (не зависящий, по предположению, от
моментов времени подачи на вход битов последовательности z). При бесконечном х это заведомо так (поскольку $x = x'$). Пусть х конечно. Подадим х на вход и будем ждать, пока на выходе не появится $M(x)$. Это рано или поздно должно случиться, если $M(x)$ конечно, после чего мы подадим на вход недостающие символы из $x'$. Полученная после этого на выходе последовательность $M(x')$ неизбежно будет продолжением $M(x)$.

Столь же ясно, что для бесконечного $\omega$ значение $M(\omega)$ есть объединение значений $M(x)$ для конечных $x \le \omega$, поскольку в каждый момент вычисления на вход подано лишь конечное число битов последовательности $\omega$.

Множество пар слов $(x, y)$, для которых $y \le M(x)$, перечислимо, так как его можно перечислять, моделируя работу машины $M$ на всевозможных входах. Таким образом, каждой корректной машине соответствует некоторое вычислимое (в абстрактном смысле) отображение.

Напротив, пусть имеется произвольное вычислимое отображение $f$. Построим машину $M$, которая корректно вычисляет его. А именно, $M$ перечисляет подграфик $\Gamma_f$ и параллельно с этим читает биты со входа. Как только в $\Gamma_f$ обнаружится некоторая пара $(x, y)$, для которой $x$ является началом входа, мы выдаём недостающие биты слова у (требования (2) и (3) гарантируют, что все обнаруживающиеся слова у будут сравнимы, так что отзывать биты с выхода не придётся). ►

### 5.4.3. Перечислимость множества вычислимых отображений

Определение вычислимости с корректными программами кажется более естественным, но оно (как и для случая префиксно корректных программ) имеет важный недостаток: нет алгоритма, позволяющего по данной программе определять, будет ли она корректной. Тем не менее можно алгоритмически преобразовать какую программу в корректную: надо перейти от неё к множеству пар, «скорректировать» это множество и затем обратно перейти к программе. Мы не будем это описывать подробно, поскольку корректные программы для нас — всего лишь мотивировка понятия вычислимого отображения, а ограничимся утверждением о перечислимости множества вычислимых отображений, которое нам понадобится в дальнейшем.

**Теорема 83.** Существует перечислимое множество $U$ троек $(n, x, y)$ (где $n$ — натуральные числа, $x$ и $y$ — слова) с такими свойствами:

(а) при любом $n$ множество $U_n = \{(x, y) \mid (n, x, y) \in U\}$ является подграфиком некоторого вычислимого отображения $u_n: \Sigma \to \Sigma$ (то есть удовлетворяет свойствам (1)–(3) теоремы 81);

(б) среди отображений $u_n$ встречаются все вычислимые отображения $\Sigma$ в себя.

◄ Рассмотрим универсальное множество $W$ троек того же вида, среди сечений $W_n$ которого встречаются все перечислимые множества пар слов. Далее изменим $W$, «скорректировав» все сечения $W_n$. Мы хотим, чтобы после коррекции сечение заведомо удовлетворяло свойствам (1)–(3) (и тем самым было подграфиком вычислимого отображения по теореме 81), и чтобы корректные сечения при этом не менялись.
Коррекция состоит из двух этапов: сначала устраняются «противоречия», а затем восполняются «пробелы». Противоречие образуют две пары $\langle x_1, y_1 \rangle$ и $\langle x_2, y_2 \rangle$, в которых $x_1$ сравнимо с $x_2$, а $y_1$ не сравнимо с $y_2$. (Легко видеть, что в подграфике таких пар быть не может.) Противоречия устраняются естественным способом: выбрасываются пары, противоречащие ранее появившимся (и не выброшенным). Полученное множество перечислимо. После этого восполняются пробелы: добавляются все пары вида $\langle x, \Lambda \rangle$; если в множестве есть пара $\langle x, y \rangle$, то добавляются также и все пары $\langle x', y' \rangle$ с $x' \succsim x$ и $y' \succsim y$. Восполнение пробелов также сохраняет перечислимость; легко проверить, что полученное после этого множество удовлетворяет нашим требованиям. ►

Это утверждение, которое можно назвать перечислимостью множества всех вычислимых отображений $\Sigma$ в себя, будет использовано при построении монотонной сложности в следующем разделе.

## 5.5. Монотонная сложность

При определении монотонной сложности в качестве способов описания (декомpressоров) рассматриваются вычислимые отображения $D: \Sigma \to \Sigma$. Монотонной сложностью слова $x$ при данном способе описания $D$ называется наименьшая длина слова $y$, для которого $x \preceq D(y)$. Она обозначается $KM_D(x)$.

(Это определение безо всяких изменений переносится и на бесконечные последовательности $x$, но мы следуем традиции и рассматриваем лишь двоичные слова, если это не оговорено особо.)

**133** Докажите, что естественным образом определённая сложность бесконечной последовательности равна пределу неубывающей последовательности сложности её начальных отрезков.

**Теорема 84.** Существует оптимальный способ описания, то есть вычисливаемое отображение $D: \Sigma \to \Sigma$, для которого $KM_D$ минимальна с точностью до константы: для всякого вычислимого $D'$: $\Sigma \to \Sigma$ найдётся такая константа $c$, что

$$KM_D(x) \le KM_{D'}(x) + c$$

для любого слова $x$.

Пусть $U$ — множество троек, сечениями которого являются все подграфики вычислимых отображений и только они (теорема 83, с. 148). Пусть $D_n$ — вычислимое отображение, соответствующее сечению $U_n$. Определим отображение $D$ формулой

$$D(\hat{n}z) = D_n(z),$$

где $\hat{n}$ — беспрефиксный код числа $n$ (скажем, его двоичная запись с удвоенными цифрами, за которой следует 01), а $z$ — произвольный элемент $\Sigma$. В терминах подграфика: рассмотрим множество всех пар $\langle \hat{n}u, v \rangle$, для которых $\langle n, u, v \rangle \in U$. Легко проверить, что действительно получается вычислимое отображение и что если способ описания $D'$ имеет номер $n$ (подграфик совпадает с $U_n$), то $KM_D(x) \le KM_{D'}(x) + l(\hat{n})$ при всех $x$. ►
Как обычно, мы фиксируем некоторый оптимальный «монотонный способ описания» (вычислимое отображение D, для которого выполнено утверждение этой теоремы) и монотонной сложностью слова х называем $KM_D(x)$. Обозначение: $KM(x)$. (В англоязычной литературе, в частности, в книге Ли и Витаньи [85], используется обозначение $Km(x)$, а $KM(x)$ обозначает априорную сложность, $KA(x)$ в наших обозначениях.)

**Теорема 85.** (а) Монотонная сложность монотонна: $KM(x) \le KM(y)$ при $x \le y$;

(б) функция $KM$ перечислима сверху;

(в) $KM(x) \le l(x) + O(1)$;

(г) $KM(x) \le KP(x) + O(1)$;

(д) $KA(x) \le KM(x) + O(1)$;

(е) бесконечная последовательность нулей и единиц вычислима тогда и только тогда, когда монотонная сложность её начальных отрезков ограничена;

(ë) если $f: \Sigma \to \Sigma$ — вычислимое отображение, то $KM(f(x)) \le KM(x) + O(1)$ (скрытая в $O(1)$ константа может зависеть от $f$, но не от $x$);

(ж) если $f: \Sigma \to \mathbb{N}_\perp$ — вычислимое отображение, то $KP(f(x)) \le KM(x) + O(1)$ (скрытая в $O(1)$ константа может зависеть от $f$, но не от $x$).

Поучительно сравнить эти утверждения со свойствами априорной сложности (теорема 79, с. 141). Поскольку монотонная сложность не меньше априорной (утвержение (д)), некоторые свойства априорной сложности сразу же переносятся на монотонную. В частности, мы получаем, что $KP(x|I(x)) \le KM(x) + O(1)$ и $KP(x) \le KM(x) + KP(l(x)) + O(1)$. Кроме того, отметим, что для вычислимых последовательностей несравнимых слов префиксная и априорная сложности совпадают с точностью до $O(1)$ — и потому совпадают с находящейся между ними монотонной: если $x_0, x_1, \dots$ — такая последовательность, то $KM(x_i) = KA(x_i) + O(1) = KP(x_i) + O(1)$.

◀ Утверждение (а) непосредственно следует из определения: если $D(u) \ge y$, то и $D(u) \ge x$ для любого начала $x$ слова $u$. Можно сказать, что при определении монотонной сложности требуется описать не само слово, а любое из его продолжений, и при удлинении слова эта задача усложняется (множество продолжений становится меньше).

Утверждение (б) сразу следует из определения: подграфик вычислимого отображения перечислим, поэтому перечислимо и множество троек $\langle x, y, r \rangle$, для которых $l(y) < r$ и пара $\langle y, x \rangle$ принадлежит подграфику $D$, а значит, перечислим и надграфик функции $KM$ как проекция этого множества.

Чтобы доказать (в), достаточно заметить, что тождественное отображение $\Sigma \to \Sigma$, для которого $D(x) = x$ при всех $x \in \Sigma$, вычислимо.

Чтобы сравнить $KM$ и $KP$ (пункт (г) теоремы), достаточно заметить, что любое вычислимое отображение $\Sigma \to \mathbb{N}_\perp$ можно переделать в отображение $\Sigma \to \Sigma$ (отобразив $\mathbb{N}_\perp$ в $\Sigma$: элемент $\perp$ переходит в пустое слово). Более формально, если $D$ — оптимальный префиксно корректный способ описания, используемый при определении $KP$, то его же можно считать вычислимым отображением $\Sigma \to \Sigma$, до-
определив пустым словом на тех аргументах, где D не был определён, и продолжив на бесконечные последовательности по непрерывности.

Для сравнения $КМ$ и $КА$ (пункт (д) теоремы) надо вспомнить, с чего мы начинали обсуждение вычислимых отображений: мы говорили, что вероятностный алгоритм представляет собой датчик случайных битов, к выходу которого применяется вычислимое отображение пространства $\Sigma$ в себя. Пусть $D$ — оптимальный способ описания, используемый при определении монотонной сложности. Рассмотрим вероятностную машину, которая состоит в применении $D$ к последовательности случайных битов. Нас интересует вероятность того, что на её выходе появится слово $x$ или какое-то его продолжение. Ясно, что эта вероятность не меньше $2^{-l(y)}$ для любого слова $y$, при котором $D(y) \ge x$, поскольку датчик случайных битов с вероятностью $2^{-l(y)}$ выдаст последовательность, начинающуюся на $y$, а применение $D$ после этого даст последовательность, начинающуюся на $x$. (Подробнее о сравнении $КМ$ и $КА$ см. формулировку теоремы 87 и её обсуждение.)

Утверждение (е) в одну сторону прямо следует из соответствующего утверждения теоремы 79, а в другую очевидно: начальные отрезки вычислимой последовательности $\omega$ имеют ограниченную монотонную сложность, поскольку можно рассмотреть вычислимое отображение $\Sigma \to \Sigma$, равное $\omega$ на всех аргументах.

В пункте (ё) допустим и случай, когда $f(x)$ бесконечно (если стремиться этому избежать, то надо говорить о сложности всех конечных начал $f(x)$). Для доказательства достаточно рассмотреть способ описания, являющийся композицией оптимального (использованного при определении монотонной сложности) способа и отображения $f$.

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

[134] Докажите, что $КМ(xy) \le KP(x) + КМ(y) + О(1)$ (здесь $xy$ — конкатенация слов $x$ и $y$). В частности, $КМ(xy) \le KP(x) + l(y) + О(1)$. [Указание. Рассмотрим оптимальный беспрефиксный способ описания $D_p$ и оптимальный монотонный способ описания $D_m$. Теперь положим $D'(uv) = D_p(u)D_m(v)$ (когда $D_p$ прочитает всё, что захочет, непрочитанная часть рассматривается как вход для $D_m$).]

[135] Покажите, что в предыдущей задаче можно заменить $КМ(y)$ в правой части на «условную» монотонную сложность $КМ(y|x)$, определив её естественным образом (монотонности по аргументу $x$ не требуется; подробнее см. в главе 6).

[136] Докажите, что утверждение (ё) остаётся верным, если заменить $КМ$ на $КА$ (в обеих частях). [Указание: отображение $f$ можно применять к выходу вероятностной машины; получится новая вероятностная машина, которая не хуже оптимальной.]

Определение монотонной сложности можно дать и формально более простым (хотя, на наш взгляд, менее естественным) образом. Вот как это делается. Напомним, что через $\Xi$ мы обозначаем множество всех двоичных слов. На этом множестве рассмотрим отношение «быть сравнимым»: $x$ сравнимо с $y$, если $x \le y$ или
y ≲ x. Перечислимое отношение $D ⊂ Ξ × Ξ$ будем называть корректным, если оно обладает таким свойством: для всех $x_1, x_2, y_1, y_2$

$$ \langle x_1, y_1 \rangle \in D, \langle x_2, y_2 \rangle \in D \text{ и } (x_1 \text{ сравнимо с } x_2) \Rightarrow (y_1 \text{ сравнимо с } y_2). $$

Далее монотонную сложность слова у относительно D определяем как минимальную длину х, при котором $\langle x, y \rangle \in D$, и доказываем утверждение о существовании оптимального корректного перечислимого отношения.

**137** Показайте, что такой подход приводит к величине монотонной сложности, отличающейся от определённой нами не более чем на ограниченное слагаемое. [Указание. Подграфик всякого вычислимого отображения $\Sigma \to \Sigma$ является корректным множеством в только что описанным смысле. Напротив, если множество D корректно, то после «восполнения пробелов» (см. доказательство теоремы 83) оно превращается в подграфик вычислимого отображения.]

Сравнивая это определение с определением обычной колмогоровской сложности (где в качестве D берутся графики вычислимых функций, то есть перечислимые и однозначные по второму аргументу множества), можно увидеть отличия между $KS$ и $KM$. В данном случае мы не требуем однозначности: при одном и том же х в D могут быть пары $\langle x, y \rangle$ с разными у; нужно лишь, чтобы все эти у были согласованы, то есть были различными началами какой-то одной последовательности нулей и единиц. За счёт этого сложность уменьшается. Например, это позволяет всем началам данной вычислимой последовательности иметь ограниченную сложность (скажем, $KM(0^n)$ ограничено, в то время как $KS(0^n) = KS(n)$ может достигать логарифма $n$).

С другой стороны, мы накладываем и дополнительные ограничения: если х является описанием какого-то у, то сравнимые с х слова могут описывать лишь слова, сравнимые с у. За счёт этого сложность увеличивается. Это особенно хорошо видно, когда мы говорим о несравнимых словах (элементах вычислимой последовательности): монотонная сложность при этом обращается в префиксную, и разница между ней и обычной сложностью также может быть примерно равна $\log n$ для слов длины $n$.

Суммируя эти наблюдения (и вспоминая, что и априорная сложность, и обычная сложность отличаются от префиксной не более чем на $O(\log n)$ для слов длины $n$), приходим к такому утверждению:

**Теорема 86.** Разница между $KS(x)$ и $KM(x)$ не превышает $O(\log n)$ для слов длины $n$ и может достигать $\log n - O(1)$ в обе стороны для слов длины $n$ при бесконечно многих $n$.

Мы вернёмся к вопросу о связи различных вариантов определения сложности в главе 6. Сейчас мы приведём лишь одно утверждение такого рода:

**Теорема 87.** Величина $KM(x) - KA(x)$ не ограничена сверху; более того, для бесконечно многих $n$ найдется слово длины $n$, для которого эта разность не меньше $\log \log n - O(\log \log \log n)$.

Это доказал недавно А. Дей [36], усилив более ранний результат П. Гача о том, что разность не ограничена сверху [45]. Обе работы основаны на сведении вопроса
к некоторой игре, в которой указывается выигрышная стратегия для одного из игроков.

Вспомним, что и при определении $КМ(x)$, и при определении $КА(x)$ выбирается некоторое вычислимое непрерывное отображение $f: \Sigma \to \Sigma$. Затем рассматривается прообраз множества всех продолжений слова $x$ при этом отображении. Разница между $КА$ и $КМ$ состоит в том, что в первом случае нас интересует меня этого прообраза, а во втором случае — мера наибольшего интервала вида $\Sigma_y$, содержащегося в этом прообразе. Из этого описания видно, что $KA_f \le KM_f$, и разница может быть большой, если прообраз «разреженный». Вопрос в том, насколько это возможно для оптимального способа описания.

Аналогичная проблема возникала при сравнении префиксной сложности с логарифмом априорной вероятности на изолированных объектах. Речь шла о выделении места на отрезке $[0, 1]$ счётному числу клиентов, см. доказательства теорем 46 (с. 91) и 58 (с. 108). Разница между префиксной сложностью и логарифмом априорной вероятности на $\mathbb{N}$ также возникала из-за того, что в одном случае нас интересовал общий размер прообраза, а в другом случае — длина наибольшего непрерывного участка. Однако тогда за счёт перехода к другому способу описания удавалось обойтись лишь постоянным множителем.

Теперь задача усложняется за счёт того, что клиенты объединены в иерархическую структуру типа дерева. Из-за этого дополнительное ужесточение требований (учёт лишь максимального непрерывного участка памяти, а не общего её количества) приводит к большим потерям памяти.

### 5.5.1. Доказательство теоремы Гача – Дея

Сначала аккуратно определим используемую игру двух игроков: **Заказчика** и **Менеджера**. Чтобы определить игру, фиксируем некоторое дерево с корнем и рациональное число $d \ge 1$. Каждой вершине дерева в каждый момент игры поставлено в соответствие неотрицательное рациональное число, которое мы называем **запросом** этой вершины (в этот момент). При этом запрос любой вершины всегда должен быть не меньше суммы запросов всех её сыновей, а запрос корня дерева — не больше $1/d$.

Запросы делает **Заказчик**; в ответ **Менеджер** выделяет место в канторовском пространстве. В каждый момент игры для каждой вершины дерева известно, какое подмножество пространства $\Omega$ ей выделено. Это подмножество должно быть объединением конечного числа интервалов (множеств вида $\Omega_x$). Множество, выделенное вершине, должно содержать множества, выделенные ей детям, а эти последние не должны пересекаться. (Отсюда следует, что несравнимым вершинам соответствуют непересекающиеся множества.)

Игроки делают ходы по очереди. В начале игры все запросы равны нулю, и все выделенные множества пусты. На очередном ходу **Заказчик** может увеличить запрос любой вершины дерева (или сразу нескольких), соблюдая ограничения из предыдущего абзаца. Уменьшать запросы нельзя. В свою очередь, **Менеджер** может увеличивать выделенные вершинам множества. Цель его — удовлетворить запросы в таком смысле: выделенное вершине $i$ множество должно содержать интервал