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

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

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

**Теорема 88 (Гача-Дея).** Для каждого $d \ge 1$ для дерева Т глубины $O(d)$ и ветвления в каждой вершине $2^{O(d)O(d)}$ Заказчик имеет вычислимую выигрышную стратегию. (Вычислимость означает, что есть алгоритм, который, получив на вход $d$, реализует эту стратегию.)

Гач доказал аналогичный результат для деревьев бесконечного ветвления глуби-
ны $O(d)$, а также для деревьев конечного, но очень большого ветвления. Вклад Дея
заключается в улучшении конструкции Гача, позволяющем значительно уменьшить
степень ветвления дерева.

Объясним, как из теоремы Гача – Дея следует теорема 87. Из описания игры видно, что увеличение ветвления и высоты дерева облегчает задачу Заказчика. Кроме того, ветвление можно заменить высотой: скажем, дерево с корнем и $2^n$ его сыновьями можно вложить в бинарное дерево глубины $n$ (суммируя запросы для промежуточных вспомогательных вершин). Дерево из теоремы Гача – Дея можно вложить в бинарное дерево глубины $O(d)^{O(d)}$, так что и для этого бинарного дерева Заказчик может выиграть.

Положим $d = 2^c$, где $c$ — некоторое натуральное число. По теореме Гача – Дея при таких значениях параметров Заказчик имеет вычислимую выигрышную стратегию на бинарном дереве глубины $2^{O(c2^c)}$.

Запустим эту стратегию, а в качестве стратегии Менеджера применим алгоритм
перечисления подграфика оптимального вычислимого отображения $f: \Sigma \rightarrow \Sigma$ из
определения монотонной сложности. Точнее, по ходу игры Менеджер перечисляет
все пары $(y, x)$, для которых $x \le f(y)$, то есть $y$ является описанием $x$, выделяя
вершине $x$ интервал $\Omega_y$ и не обращая внимания на $x$ за пределами дерева (когда
длина $x$ больше $2^{O(c2^c)}$). Как только все текущие запросы окажутся удовлетворен-
ными, он сообщает Заказчику, что ход сделан (а после ответного хода Заказчика он
продолжит перечисление и выделение места, пока не будет удовлетворён и новый
запрос). Если этого (удовлетворения всех запросов) не произойдёт, то это значит,
что Менеджер так и не сделает ход и проиграет. (Эта стратегия Менеджера, так
сказать, соответствует идеалам планового хозяйства: не имеет значения, что просят
потребители, промышленность делает то, что запланировано, пока потребители не
окажутся удовлетворены — если окажутся.)
Теорема гарантирует, что Менеджер в некоторый момент не сможет сделать хода. Это означает, что существует слово х длины не больше $2^{O(c2^c)}$, запрос которого в некоторый момент становится больше $2^{-KM(x)}$. С другой стороны, в ходе игры Заказчик перечисляет снизу некоторую полумеру $\mu_c$ на дереве: значение на х равно верхней грани всех запросов вершины х. Поскольку Заказчик в некоторый момент выигрывает, для этой полумеры для некоторого х выполнено $KM(x) > -\log \mu_c(x)$. Сумма полумер $\mu_c$ с весами $2^c/c^2$ является перечислительной снизу полумерой. Поэтому априорная полумера на дереве не меньше, чем $\varepsilon\mu_c(x)2^c/c^2$ (для некоторого положительного $\varepsilon$ и всех $c, x$). Отсюда следует, что для каждого с найдется слово х длины не больше $2^{O(c2^c)}$, для которого

$$KM(x) > KA(x) + c - 2 \log c - O(1).$$

Обозначим длину этого слова через $n$. Тогда $c$ не меньше $\log \log n - O(\log \log \log n)$, а значит

$$KM(x) > KA(x) + \log \log n - O(\log \log \log n).$$

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

**138** Покажите, что для бесконечно многих $n$ выполнено такое свойство: для всех слов х длины $n$ разница $KM(x) - KA(x)$ не превосходит $\log \log \log n$. Здесь тройной логарифм можно заменить на любую неубывающую вычислимую функцию, стремящуюся к бесконечности. [Указание: если объявить какие-то очень редкие длины особо важными, то для слов каждой из этих длин можно выделять место по отдельности, и превышение будет не очень большим.]

◀ Изложение доказательства теоремы Гача-Дея начнём с неформального обсуждения. Какая главная трудность возникает у Менеджера при выделении места? Пусть Заказчик запросил очень небольшое (но ненулевое) место для некоторой вершины. У Менеджера есть выбор: позаботиться о том, чтобы рядом с выделенным местом был запас свободного пространства (соседние интервалы не выделены никому другому), или не делать этого.

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

Наша стратегия будет эксплуатировать эту трудность, контролируя размер $\varepsilon$-окрестности владений различных вершин. Пусть дано $\varepsilon \le 1$, являющееся целой степенью двойки. Будем называть $\varepsilon$-окрестностью подмножества $X$ в канторовском пространстве объединение всех интервалов длины $\varepsilon$, пересекающихся с множеством $X$. Заказчик будет добиваться, чтобы отношение окрестности выделенного пространства к запросу было большим (скажем, не меньше некоторого $k$); поскольку размер окрестности не больше 1, то при запросе больше $1/k$ Менеджер не сможет это поддерживать и проиграет. В соответствии с этим планом мы будем строить

А что будет

> ства $n$?
стратегии для Заказчика, добивающиеся того, что в некоторый момент игры за-
прос корня не превосходит некоторого $\alpha$, а длина $\varepsilon$-окрестности владений корня
не меньше некоторого $\beta$. (Эту окрестность мы будем называть «надкушенным про-
странством» по аналогии с фразой «не съем, так хоть понадкусываю» из анекдота
про жадину.)

Более точно, мы будем строить стратегии Заказчика, исходя из следующих па-
раметров:

• дерево, на котором происходит игра;

• $\varepsilon$, указывающий, как измеряется окрестность выделенного множества;

• максимально разрешённый запрос $\alpha$ для корня;

• требуемый размер $\beta$ надкушенной части (то есть $\varepsilon$-окрестности выделенного пространства).

При некоторых соотношениях параметров выигрышная стратегия для Заказчика существует, то есть он может добиться, чтобы $\varepsilon$-окрестность выделенного Менеджером пространства (для корня дерева — остальные вершины получают части) была не меньше $\beta$, при этом запрос для корня не превосходит $\alpha$.

Пример 1. Пусть $\varepsilon$ — степень двойки, $\beta = \varepsilon$, а значение $\alpha$ положительно и много меньше $\beta$. Тогда стратегия существует, даже если дерево состоит только из корня: запросим $\alpha$; что бы нам ни выделили, это непустое множество будет иметь $\varepsilon$-окрестность размера не меньше $\varepsilon$.

Таким образом, получить большой коэффициент «полезного действия» (отноше-
ние $\beta/\alpha$) несложно, если $\beta$ мало. Сложность возникает, когда $\beta \gg \varepsilon$, и для этого
нам понадобиться строить стратегии индуктивно, соединяя стратегии для разных
деревьев и используя внутри одной стратегии рекурсивные вызовы других (на под-
деревьях). При индуктивном построении нам будет полезно учитывать отдельно
коэффициент полезного действия, добавив ещё один параметр $k$ и требуя, чтобы
отношение надкушенного к запрошенному было не меньше $k$. При $k \le \beta/\alpha$ это
выполнено автоматически, но нам будет полезно иметь стратегии, гарантирующие
данный коэффициент полезного действия, но оставляющие некоторую свободу для
размера запрошенного.

Пример 2. Пусть дерево $T$ имеет $m$ сыновей корня, каждый из которых имеет двух сыновей (внуков корня). Пусть $\varepsilon$ — некоторая степень двойки, $\alpha = \beta = m\varepsilon$, а $k = 3/2$ (так что в данном случае $k$ существенно: мы не знаем точного размера запрошенного и надкушенного, но знаем, что второе должно быть минимум в полтора раза больше первого, а $m\varepsilon$ должно лежать между ними).

Стратегия в этом примере строится так. Чтобы поставить Менеджера в трудное
положение, выберем у каждого сына корня по одному сыну и запросим для них
по $\varepsilon/2$. (Мы указываем запросы для листьев; для остальных вершин они получа-
ются сложением запросов для потомков.) Менеджер должен будет решить, кого из
внуков размещать в паре со своим двоюродным братом (выделив им по $\varepsilon/2$ внутри
одного интервала размера $\varepsilon$), а кого помещать «поодиночке в двухместный номер»
(сохраняя соседний интервал как резерв для брата). Для тех внуков, у которых нет
резерва, закажем $\varepsilon/2$ и для их родных братьев — тогда запрос отца этих братьев
достигнет $\varepsilon$ и придётся выделить новый интервал размера $\varepsilon$ (потому что в старом не было резерва; резервы в других местах тоже малы). Таким образом, для любого сына корня происходит одно из двух: либо при заказе $\varepsilon/2$ было выделен резерв $\varepsilon$, либо при заказе в $\varepsilon$ пришлось выделить $(3/2)\varepsilon$. В обоих случаях достигнут коэффициент $3/2$.<fnref n="1" />

Попробуем теперь соединить две стратегии с одним и тем же гарантированным коэффициентом полезного действия $k$. (Наша цель — сохранить этот коэффициент, но увеличить размер запрошенного и надкушенного.) Пусть дерево $T$ состоит из корня из двух поддеревьев $T_1$ и $T_2$. Пусть на дереве $T_1$ для каких-то $\alpha_1, \beta_1, \varepsilon$ (и выбранного $k$) есть выигрышная стратегия (для Заказчика, как всегда), а на дереве $T_2$ есть стратегия с другими параметрами $\alpha_2, \beta_2$ и теми же $\varepsilon$ и $k$. Будем применять эти стратегии последовательно: сначала на $T_1$ применим первую стратегию, а когда будет надкушено достаточно (первая стратегия выиграет), применим на $T_2$ вторую. (Без ограничения общности можно считать, что во время запросов на $T_1$ для вершин из $T_2$ ничего не выделяется, так как это в любом случае можно отложить.) В такой ситуации общий запрос будет не больше $\alpha_1 + \alpha_2$, так как запросы складываются. Беда в том, что надкушенное пространство, в отличие от выделенного, не складывается: размер $\varepsilon$-окрестности объединения двух множеств может быть меньше суммы размеров $\varepsilon$-окрестности каждого из них. Например, во второй игре менеджер может использовать резерв внутри интервалов, надкушенных, но не занятых целиком в первой игре.

Это можно предотвратить, рассматривая разные значения $\varepsilon_1$ и $\varepsilon_2$ для первой и второй стратегии и взяв $\varepsilon_1 \ll \varepsilon_2$. Если при этом вторая стратегия будет запрашивать только интервалы размера $\varepsilon_1$ и больше, то внутри $\varepsilon_1$-окрестности владений дерева $T_1$ ей ничего выделено быть не может. Неформально говоря, мы накапливаем резервы на разных уровнях (сначала малого размера, потом большого). Правда, остаётся проблема в обратную сторону: хотя владения $T_2$ теперь не пересекают $\varepsilon_1$-окрестность владений $T_1$, но владения $T_1$ вполне могут попадать в $\varepsilon_2$-окрестность владений $T_2$, и сложения опять не получится. Чтобы выйти из положения, мы снова общим игру и будем считать, что перед началом игры какое-то подмножество $A \subset \Omega$ считается *недоступным менеджеру*, и оценивать *новые надкушенные интервалы*. Более точно это описывается так.

В окончательном варианте игра задаётся такими параметрами:

* дерево $T$, на котором происходит игра;

* подмножество $A \subset \Omega$ (недоступное менеджеру);

* $\delta$ (указывающий, как измеряется окрестность недоступного множества);

* $\varepsilon$ (указывающий, как измеряется окрестность выделенного множества);

<footnote n="1">¹В принципе, достигнуть коэффициента $3/2$ легко, запросив для каждого сына чуть больше $\varepsilon/2$: поскольку выделять можно только интервалы, их размеры будут степенями двойки и менеджеру придётся выделить $\varepsilon$. Однако этот эффект, в отличие от описанного выше, не «масштабируется» (не позволяет увеличивать коэффициент за счёт рекурсивных вызовов), так что мы его использовать и о нём говорить не будем. Ещё можно было бы обойтись без внуков, сначала заказав для детей корня по $\varepsilon/2$, а потом увеличив заказ до $\varepsilon$ в тех вершинах, где нет резерва. Мы выбрали вариант с внуками, так как он больше похож на будущую конструкцию для общего случая.</footnote>
* максимально разрешённый (суммарный) запрос α;

* требуемый размер β;

* требуемый коэффициент полезного действия k.

Заказчик увеличивает запросы на дереве T (от нуля), минимальный ненулевой запрос δ, при этом запрос корня не может быть больше α. Менеджер выделяет место в канторовском пространстве, при этом не используя интервалы, пересекаются с А. Заказчик выигрывает, если размер свеженадкушенной части (ε-окрестности выделенного минус δ-окрестность А) не меньше β, а его отношение к запросу корня не меньше k (или если Менеджер не смог сделать хода, не нарушив правила игры). Как и раньше, увеличение дерева и ε, а также α упрощает задачу Заказчика. Она упрощается также и при уменьшении δ, β или k.

При таком определении обсуждение выше даёт такое утверждение:

**Лемма о композиции.** Пусть для дерева $T_1$ и любого недоступного подмножества Заказчик может выиграть в игре с параметрами $ε_1, δ_1, α_1, β_1, k_1$, а для дерева $T_2$ и любого недоступного подмножества он может выиграть в игре с параметрами $ε_2, δ_2, α_2, β_2, k_2$. Пусть при этом $ε_1 = δ_2$ и $k_1 = k_2$ (общее их значение обозначим k). Тогда на дереве T, состоящем из корня и двух поддеревьев $T_1$ и $T_2$, при любом недоступном подмножестве Заказчик может выиграть в игре с параметрами $ε_2, δ_1, α_1 + α_2, β_1 + β_2, k$.

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

На самом деле, мы будем использовать не буквально утверждение леммы, а применять ту же идею в чуть более общей ситуации: деревья не будут заданы ранее, а будут выбираться в ходе игры (выбор следующего дерева будет зависеть от хода игры на предыдущем). Кроме того, мы будем соединять не две стратегии, а много. За это нам придется заплатить большой разницей между значениями ε и δ в результатующей игре: в каждой следующей игре значение ε увеличивается по сравнению с предыдущим (которое для неё будет входным значением δ). Заметим также, что соединение стратегий не приводит к увеличению коэффициента полезного действия, которого нужно добиться как-то иначе.

Прежде чем показать на примере, как увеличивать коэффициент полезного действия, сделаем одно простое техническое замечание. Без ограничения общности можно потребовать, чтобы в конце игры запрос корня был не меньше $β/k$. В самом деле, если в результате какой-то непредвиденной экономии он оказался меньше, можно в конце игры искуственно увеличить запрос, не нарушив условий выигрыша (в плановой экономике этот приём назывался «освоением средств»).

**Пример 3.** Покажем, как можно добиться коэффициента полезного действия $k > 2$. Мы будем действовать как в примере 2, но вместо прямого заказа $ε/2$ для внуков мы будем рекурсивно вызывать стратегию того же примера 2.

Прежде всего вспомним, чего мы можем добиться с помощью стратегии примера 2. Для данного α и сколь угодно малого ε, делящегося на цело, можно построить стратегию на дереве глубины 2, которая при $δ = ε/2$ для любого множества А позволяет получить не менее α (свеже) надкушенного при не более чем α запрошенного с коэффициентом полезного действия не менее 1,5. Для этого достаточно
вспомнить стратегию и понять, что при $δ = ε/2$ наличие запрещённого множества не помешает. Дерево имеет $m = α/ε$ сыновей корня, каждый из которых имеет двух сыновей. Условие делимости нам в дальнейшем не помешает, так как мы будем применять стратегию примера 2 только для $α$, кратных $ε$.

Если мы хотим применять к таким стратегиям лемму о композиции, нам придется позаботиться о согласовании параметров $ε$: в каждой следующей стратегии параметр должен быть вдвое больше, чем в предыдущей. Важно, что при этом мы можем использовать одно и то же $α$, конструкция примера 2 позволяет развязать выбор размера запроса и выбор масштаба измерения окрестности. Если знать заранее максимальное число применений (число стратегий, подвергаемых композиции), то можно понять, с какого значения $ε$ начинать. Теперь о значении $ε$ для игр в композиции уже можно не говорить, и мы будем использовать $ε$ для обозначения параметров основной игры (где мы хотим достичь $k > 2$, измеряя $ε$-окрестность выделенного).

В основной игре мы тоже будем действовать по аналогии с примером 2. Мы обеспечим коэффициент $k > 2$ при любом заданном $ε$, при любом $α = με$ и при достаточно малом $δ$, с максимальным размером запроса и минимальным размером надкушенного, равным $α = με$.

Как же мы играем? Корень имеет $m$ сыновей, как и раньше. Теперь нам понадобится больше внуков. Договоримся, скажем, что каждый сын корня имеет в свою очередь 12 сыновей (этого хватит). Вместо того, чтобы просто заказывать для внуков интервалы какого-то размера, мы будем вызывать для них рекурсивно описанные выше стратегии: над каждым внуком будет поддерево высоты 2, так что всего высота дерева будет 4.

Итак, мы в каждый момент смотрим, какие из сыновей корня не имеют резерва, понимая под резервом интервал размера $ε$, в котором им что-то выделено, ничего не выделено другим вершинам (не считая их потомков и предков) и нет точек запрещённого множества. Другими словами, резерв — это интервал, который (1) уже частично занят и (2) ещё может быть использован в будущем, когда запрос увеличится до $ε$. Выберем одного из таких (не имеющих резерва) сыновей и запустим на нём (а точнее, на некотором ещё не обработанном его сыне) стратегию с $α = ε/8$. При этом будет запрошено не больше $α$ и, можно считать, не меньше $α/1,5 = ε/12$ (см. выше об освоении средств). Может быть, после этого появится резерв (а может, и не появится, если выделенные интервалы будут рядом с множеством $A$). Так или иначе, мы повторяем это действие, пока для всех сыновей корня не появятся резервы — с одним уточнением: если уже запрошенное каким-то из них место превысило $(7/8)ε$ и есть опасность, что следующий запрос пересечёт границу в $ε$, мы нового запроса не делаем, а добиваемся резерва, просто увеличив заказ этого интервала до $ε$. Поскольку при каждом вызове стратегии для некоторого сына его запрос увеличивается не менее чем на $ε/12$, нам хватит двенадцати сыновей у каждого сына корня. По этой же причине общее количество вызовов стратегии будет ограничено некоторым заранее известным числом $(12m)$.

Почему эта стратегия даст хороший результат? Для каждого сына корня рассмотрим последнее обращение к нему, после которого образовался резерв. Этот
резерв имеет размер $ε$ и до этого обращения резервом не был. Раз он смог стать резервом, значит, ничего постороннего в нём нет (и не было); раз он резервом не был, значит, он был совершенно пустым. Вывод: то, что было надкушено при всех не-последних обращениях, в резервы не вошло. Оно дало выигрыш в полтора раза, да плюс ещё почти пустые резервы — в итоге получается выигрыш с $k = 20/9 > 2$, если подсчитать аккуратно.

Вот этот подсчёт: обозначим через $\gamma$ общий запрос при не-последних обращениях. Он даёт вклад $(3/2)\gamma$ в надкушенное, лежащий вне резервов, всего получается $(3/2)\gamma + m\epsilon$ надкушенного при максимум $\gamma + m(\epsilon/8)$ запрошенного. (Можно сказать, что часть увеличивается в 3/2 раза, а часть в 8 раз, и притом вторая часть не очень мала по сравнению с первой, так что в целом коэффициент увеличивается). Технически, из $\gamma \le m\epsilon$ следует

$$ \left[ \frac{3}{2}\gamma + m\epsilon \right] \ge \frac{20}{9} \left[ \gamma + m\frac{\epsilon}{8} \right] $$

(что нетрудно проверить, раскрыв скобки и приведя подобные члены). Таким образом, обещанная стратегия с $\alpha = \beta = m\epsilon$ и $k = 20/9 > 2$ построена.

Теперь общая схема должна быть уже более или менее понятна. Имея стратегию с $k = 20/9$, мы можем её рекурсивно вызывать для внуков корня (тем самым перейдя к дереву глубины 6 с большим ветвлением — можно даже оценить, каким). Такой переход, если действовать аккуратно, может увеличить $k$ почти на 1. В самом деле, если взять достаточно малую долю $\epsilon$ вместо $\epsilon/8$, то потерями на последних шагах (с образованием резерва) можно пренебречь, и мы получаем резерв $m\epsilon$ в дополнение к индуктивно полученному увеличению в $k$ раз. При этом, если общий запрос $\gamma$ близок к максимуму $m\epsilon$, то резерв прибавляет к коэффициенту полезного действия почти единицу, а если общий запрос оказался меньше, то нам же лучше. Чтобы оценить сверху число внуков корня, надо вспомнить, что мы можем (методом освоения средств) обеспечить увеличение запроса на некоторую фиксированную долю $\epsilon$. Таким образом, при дереве глубины $O(k)$ и достаточно большого ветвления мы можем обеспечить превышение надкушенного над запрошенным в $k$ раз, что достаточно для теоремы Гача (но не Дея).<fnref n="1" />

Остаётся более аккуратно объяснить детали этого рассуждения. Индукцией по полуцельм $k \ge 1$ мы доказываем, что для любых степеней двойки $\epsilon \le \alpha \le 1$ найдётся степень двойки $\delta \le \epsilon$ такая, что Заказчик выигрывает в игре с параметрами $\epsilon, \delta, \alpha, \kappa$ и любым недоступным Менеджеру множеством на дереве бесконечного ветвления глубины $4(k-1)$.

База индукции ($k=1$) очевидна. Индуктивный переход: пусть утверждение верно для $k$ и надо доказать его для $k+1/2$. Запустим стратегию из примера 3 на дерево

<footnote n="1">¹На самом деле мы еще не до конца доказали теорему Гача. Мы построили стратегию с произвольным коэффициентом $k$, а нужна нам стратегия со сколь угодно большим отношением $\beta/\alpha$: нам надо надкусить больше 1 и при этом запросить не больше $1/d$. Такую стратегию легко получить последовательным применением построенных стратегий с подходящими параметрами. Например, применяя их с параметрами $k=2d$ и $\alpha=1/(4d)$ по очереди для каждого из сыновей корня исходного дерева до тех пор, пока запрос корня не превысит впервые $1/d - 1/(4d)$, мы получим стратегию с параметрами $\alpha=1/d$ и $\beta=2d(1/d - 1/(4d)) = 3/2$, чего вполне достаточно. Для этой стратегии достаточно дерева глубины $4(2d-1) + 1$.</footnote>
ве глубины $4(k + 1/2 - 1)$, только на этот раз будем во внуках запускать стратегию с параметром $k$, существующую по индуктивному предположению (глубина дерева с корнем во внуках как раз равна $4(k - 1)$). В качестве параметра $\alpha$ при рекурсивных вызовах выберем степень двойки, лежащую в интервале $(\varepsilon/(6k), \varepsilon/(3k))$. (Поскольку правая граница интервала вдвое больше левой, в этом интервале обязательно найдется степень двойки.) При каждом рекурсивном вызове запрос корня увеличивается не менее, чем на $\varepsilon/(6k^2)$, поэтому общее количество рекурсивных вызовов можно ограничить заранее — оно не превзойдет $6mk^2$. Тем самым, можно заранее подобрать параметры $\varepsilon, \delta$ для всех рекурсивных вызовов. Кроме того, можно ограничить количество внуков — каждому сыну достаточно $6k^2$ сыновей. В момент, когда все сыновья корня сделали резервы, мы достигли своей цели. В самом деле, обозначим через $\gamma$ общий запрос корня при не-последних рекурсивных вызовах. Он daßt вклад $k\gamma$ в надкущенное, лежащее вне резервов, всего получается $k\gamma + m\varepsilon$ надкущенного при максимум $\gamma + m(\varepsilon/(3k))$ запрошенного. Поскольку $\gamma \le m\varepsilon$, величина первого в $k + 1/2$ больше величины второго:

$$k\gamma + m\varepsilon \ge (k + 1/2)(\gamma + m\varepsilon/(3k)),$$

что проверяется простым раскрытием скобок.

Как видно из доказательства, стратегия будет выигрывать и на деревьях глубины $4(k-1)$ конечного ветвления, зависящего от $\varepsilon, \alpha, k$. Однако полученная таким образом величина этого ветвления намного хуже указанной в теореме 88. Поясним, почему так получается. Дерево для стратегии с параметрами $\varepsilon, \alpha, k$ имеет ветвление $\alpha/\varepsilon$ в корне. В сыновьях корня ветвление мало, и им можно пренебречь. Чтобы оценить ветвление во внуках корня, нам нам нужно оценить сверху отношение $\alpha'/\varepsilon'$ при всех рекурсивных вызовах стратегии. Эти вызовы делаются с параметрами $\alpha' \approx \varepsilon/(3k)$ и некоторых $\varepsilon'$, которые меняются от вызова к вызову. При этом минимальное $\varepsilon'$, с которым будет вызываться стратегия во внуках получается в результате цепи из $(\alpha/\varepsilon)6k^2$ применений преобразования $\varepsilon \mapsto \delta$. Это приводит к тому, что минимальное значение $\varepsilon'$ значительно меньше исходного $\varepsilon$. Поэтому и ветвление во внуке, который будет обрабатываться первым, должно быть очень большим (на самом деле, поскольку мы заранее не знаем, кто будет обрабатываться первым, «старший сын» каждого сына корня должен иметь много сыновей).<fnref n="1" />

Таким образом, недостаток нашей стратегии в том, что она делает слишком много рекурсивных вызовов. Оказывается можно обойтись всего лишь $O(k^2)$ вы-

$$f_{k+1/2}(\alpha/\varepsilon) \approx 3k \cdot f_k(1) \cdot f_k(f_k(1)) \cdot f_k(f_k(f_k(1))) \dots$$

<footnote n="1">¹ Чтобы оценить ветвление во внуках, нужно индукцией по $k$ оценить сверху отношение $\varepsilon/\delta$ первых двух параметров стратегии функцией $f_k(\alpha/\varepsilon)$ от $k$ и $\alpha/\varepsilon$. Значение $f_{k+1/2}(\alpha/\varepsilon)$ получается произведением $(\alpha/\varepsilon)6k^2$ значений $f_k(\alpha'/\varepsilon')$. При этом первое $\varepsilon'$ можно взять равным $\alpha'$, но остальные должны быть значительно меньше — второе $\varepsilon'$ уже в $f_k(1)$ раз меньше первого $\varepsilon'$, третье в $f_k(f_k(1))$ меньше второго и так далее. Последний сомножитель в произведении получается $(\alpha/\varepsilon)6k^2$-кратным применением функции $f_k$ к 1. Поэтому</footnote>

<footnote>(в произведении $(\alpha/\varepsilon)6k^2$ сомножителей и мы используем приблизительное равенство, поскольку первое $\varepsilon'$ лишь приблизительно равно $\varepsilon/(3k)$). При этом, скажем $f_{3/2}(\alpha/\varepsilon) \equiv 2$ (см. пример 2). Поэтому $f_2(\alpha/\varepsilon)$ не меньше экспоненты от $\alpha/\varepsilon: f_2(\alpha/\varepsilon) > 2^{\alpha/\varepsilon}$, а $f_{2,5}(\alpha/\varepsilon)$ уже не меньше, чем башня из двоек высоты $\alpha/\varepsilon$. (Можно было бы воспользоваться стратегией примера 3 и тем, что при индуктивном периоде можно увеличить значение $k$ почти на 1, но это мало бы помогло — башня двоек возникла бы при немного большем $k$.)</footnote>
зовами (вместо $O(k^2\alpha/\varepsilon)$). Важно, что это число не зависит от $\alpha/\varepsilon$. Для этого $k+1/2$-стратегия будет обрабатывать всех сыновей корня, не имеющих резерва, параллельно, а не последовательно, как раньше. Точнее, на каждом шаге для всех сыновей корня, которые не имеют резерва, стратегия будет выбирать по одному из их необработанных сыновей (внуков корня) и для полученного множества вершин делать рекурсивный вызов. Правда, для этого нужно изменить формат стратегии — теперь ее входом надо считать не одно дерево, а семейство одинаковых не связанных друг с другом деревьев. (Вершинам разных деревьев Менеджер обязан выделять не-пересекающиеся интервалы.) Само по себе это нововведение не поможет — может оказаться, что на каждом шагу только один сын корня не имеет резерва. В этом случае параллельной обработки фактически происходить не будет. С этим можно бороться следующим образом: не будем ждать, пока все сыновья корней сделают резервы. Вместо этого остановимся, когда количество сыновей с резервом составляет достаточно большую долю от общего их числа (во всех деревьях вместе — напомним, что теперь игра происходит в нескольких деревьях). Эту долю можно определить любым числом, большим половины (если мы хотим, чтобы $k$ возросло не меньше, чем на $1/2$), скажем в три четверти. Это приведет к небольшой потери — значение параметра $\beta$ будет равно трём четвертям от $\alpha$. В свою очередь, это приведет к потерям при освоении средств — нижняя оценка на суммарный запрос всех корней будет три четвертых от старой оценки (что скажется на небольшом увеличении количества итераций, необходимых для достижения резервов). Основание средств теперь будет выполняться так: если среднее арифметическое запросов корней оказалось меньше $(3/4)\alpha/k$, мы увеличиваем запросы для некоторых, чей запрос меньше $\alpha$, так, чтобы среднее арифметическое стало равно $(3/4)\alpha/k$.

Как и раньше, если запрос некоторого сына корня уже настолько приблизился к $\varepsilon$, что обработка нового его сына может повлечь превышение $\varepsilon$, мы просто увеличиваем запрос этого сына до $\varepsilon$. Как и раньше, это надо делать перед началом очередного рекурсивного вызова.

Таким образом, длина надкушенного будет равна $k\gamma + (3/4)\varepsilon$ вместо $k\gamma + \varepsilon$, как раньше (где $\gamma$ равно надкушенному внуками, обработанными не последними, а $\gamma$ равно общему количеству сыновей корня во всех деревьях), а длина запрошенного останется той же, что раньше — $\gamma + \varepsilon/(3k)$. Напомним, что $\varepsilon/(3k)$ здесь появилось, как параметр $\alpha$ при рекурсивных вызовах. Поэтому чтобы соотношение надкушенного к запрошенному было не меньше $k+1/2$, надо будет немножко уменьшить этот параметр — $\varepsilon/(6k)$ будет достаточно. Это приведет к увеличению количества итераций еще вдвое, что не страшно. Более подробно: на каждом шаге сумма запросов всех сыновей будет увеличиваться на величину, пропорциональную $\varepsilon/k^2$. Сумма запросов всех сыновей не может превысить $\varepsilon$, поэтому количество рекурсивных вызовов не превысит $O(k^2)$.

Перейдя к более детальному изложению, объясним более подробно, какие изменения надо ввести в определение игры и в построение выигрышной стратегии. Параметрами игры, помимо чисел $k, \varepsilon, \delta, \alpha, \beta$, дерева $T$ и недоступного множества $A$, является число деревьев $l$. Смысл параметров $\varepsilon, \delta, A$ не меняется. Параметр $\alpha$ ограничивает сверху запрос каждого корня, а параметр $\beta$ ограничивает снизу среднее количество свеженадкушенного в расчете на одно дерево — длина свеженадку-
шенного пространства должна быть не менее $l\beta$. Наконец, параметр $k$ ограничивает снизу отношение длины свеженадкушенного пространства к сумме запросов корней всех деревьев.

Ясно, что и теперь можно соединять стратегии. Но теперь у соединяемых стратегий должны быть одинаковые параметры $k, T, \alpha$. А именно, применим стратегию с параметрами $\varepsilon_1, \delta_1, \alpha, \beta_1, k$ и недоступным множеством $A$ для некоторого подсемейства деревьев (каждое из которых изоморфно $T$). Затем применим её еще раз с новыми параметрами $\varepsilon_2, \delta_2, \alpha, \beta_2, k$ (и новым недоступным множеством, равным объединению $A$ с владениями обработанного семейства деревьев) для другого, не пересекающегося со первым, семейства. И пусть $\varepsilon_1 = \delta_2$. Тогда в результате мы выиграем игру с параметрами $\varepsilon_2, \delta_1, \alpha, \beta_1 + \beta_2, k$ для объединенного семейства деревьев и недоступного множества $A$.

Индукцией по полулечым $k$ мы строим выигрышную стратегию Заказчика для любых $\varepsilon \le \alpha \le 1$, $\beta = (3/4)\alpha$ и некоторых $\delta \le \varepsilon$ и конечного дерева глубины $4(k-1)$, ветвление которого мы оценим потом. Числа $\varepsilon, \alpha, \delta$ должны быть степенями двойки. Стратегия должна выигрывать для любых $l$ и $A$.

База индукции ($k=1$) очевидна. Индуктивный переход от $k$ к $k+1/2$: дерево, как и раньше имеет $\alpha/\varepsilon$ сыновей, а каждый из них — $O(k^2)$ сыновей (точное значение определим позже). Стратегия действует так. Сначала мы увеличиваем до $\varepsilon$ запросы тех сыновей корней, запрос которых уже превысил $\varepsilon - \varepsilon/6k$. Дав Менеджеру пойти, мы затем проверяем, сколько сыновей корней не имеют резерва. Если их более одной четверти от общего числа, мы для каждого такого сына выбираем любого его необработанного сына. Для получившегося множества внуков мы делаем рекурсивный вызов с параметром $k$, выбирая в качестве параметра $\alpha$ степень двойки в интервале $(\varepsilon/(12k), \varepsilon/(6k)]$. Затем мы повторяем то же самое до тех пор, пока доля сыновей без резерва не станет меньше одной четверти.

При каждом рекурсивном вызове общий прирост запроса будет как минимум $(3/4)m(\varepsilon/(12k^2))$, где $m$ — общее число сыновей всех корней. При этом сумма запросов всех корней не может стать больше $m\varepsilon$ — мы гарантируем, что запрос любого сына любого корня не превышает $\varepsilon$ (если запрос некоторого сына достиг $\varepsilon$, у него появляется резерв). Поэтому общее количество рекурсивных вызовов будет не больше $O(k^2)$. Кроме того, запрос любого корня не превысит $\alpha$, поскольку у каждого корня $\alpha/\varepsilon$ сыновей. Общий размер свеженадкушенного пространства не меньше общей длины всех резервов, которая не меньше $(3/4)m\varepsilon$, как и требовалось. Осталось оценить отношение длины свеженадкушенного к сумме запросов.

Обозначим через $\gamma$ суммарный рост запросов всех корней, исключая те последние увеличения, которые приводили к образованию резервов. Он даёт вклад $k\gamma$ в надкушенное, лежащий вне резервов, всего получается $k\gamma + (3/4)m\varepsilon$ надкушенного при максимум $\gamma + m(\varepsilon/(6k))$ запрошенного. Поскольку $\gamma \le m\varepsilon$, величина первого в $k+1/2$ больше величины второго:

$$k\gamma + (3/4)m\varepsilon \ge (k + 1/2)(\gamma + m\varepsilon/(6k)),$$

что проверяется простым раскрытием скобок.

Осталось оценить необходимое ветвление дерева $T$, как функцию $k$ и отношения $\alpha/\varepsilon$ (ясно, что для игры важно только отношение этих чисел). Как мы видели
(см. обсуждение после построения стратегии для дерева бесконечного ветвления), для этого сначала нужно понять во сколько раз $\delta$ меньше $\varepsilon$. Для этого индукцией по $k$ докажем, что параметр $\delta$ можно выбрать в $c_k$ меньшим $\varepsilon$, где $c_k$ зависит только от $k$, и оценим сверху величину $c_k$.

Для $k=1$ у нас было $\delta = \varepsilon$, значит $c_1 = 1$. Стратегия для $k+1/2$ делает не более $O(k^2)$ вызовов $k$-стратегии. Отношение $\varepsilon/\delta$ есть произведение аналогичных отношений для этих вызовов и отношения исходного $\varepsilon$ к параметру $\varepsilon'$ последнего вызова (оно не превосходит $12k$, так как последний вызов делается с параметром $\alpha'$ не меньшим $\varepsilon/(12k)$ и таким же можно взять значение $\varepsilon'$). Таким образом, мы получаем рекуррентное соотношение

$$c_{k+1/2} = O(kc_k^{O(k^2)}),$$

откуда получается $c_k = 2^{O(k)^{4(k-1)}}$.

Теперь легко оценить ветвление дерева $T$, как функцию от $k$ и $\alpha/\varepsilon$. Вспомним, что при построении $(k+1/2)$-стратегии нам необходимо было ветвление $\alpha/\varepsilon$ в корне и $O(k^2)$ в сыновьях корня. Поэтому ветвление на всех нечётных уровнях ограничено $O(k^2)$ (мы считаем, что корень находится на уровне 0). Осталось оценить ветвление на чётных уровнях больше 0. На втором уровне опять ветвление равно отношению параметров $\alpha'$ и $\varepsilon'$ применяемых стратегий. Нетрудно заметить, что это отношение не зависит от исходных $\alpha$ и $\varepsilon$. В самом деле, во внуках $k$-стратегия вызывается с параметром $\alpha'$ не большим $\varepsilon/(6k)$ и с параметром $\varepsilon'$, не меньшим $\varepsilon/c_{k+1/2}$. Поэтому ветвление дерева во внуках корня ограничено величиной $6kc_{k+1/2}$. Аналогичное верно и для всех остальных чётных уровней, только с меньшим $k$.

Таким образом, $k$-стратегия будет выигрывать на дереве ветвления

$$\max\{\alpha/\varepsilon, O(k^2), 6(k - 1/2)c_k\} = \max\{\alpha/\varepsilon, O(k^2), 2^{O(k)^{4(k-1)}}\}.$$

При больших $k$ второй член меньше третьего и им можно пренебречь.

Теперь мы можем завершить доказательство теоремы Гача-Дея. Пусть $d$ есть степень двойки. Нам нужно построить стратегию с параметрами $\alpha = 1/d$ и каким-то $\beta > 1$, выигрывающую на одном дереве $T$ небольшой глубины и ветвления. Для этого мы последовательно вызываем построенную стратегию с параметрами $k = 2d$ и $\alpha = 1/(4d)$ по очереди для каждого из сыновей корня $T$ до тех пор, пока запрос корня впервые не превысит опасный порог $1/d - 1/(4d)$. В результате мы запросим не более $1/d$, а надкусим не менее $2d(1/d - 1/(4d)) > 1$. При каждом вызове запрос корня увеличивается не менее, чем на $(3/4)(1/(4d))(1/k)$, поэтому количество вызовов не превзойдёт $O(d^3)$. Поэтому нам достаточно $O(d^3)$ сыновей корня. При этом поддеревья в сыновьях должны годиться для $2d$-стратегии с параметрами $\alpha = 1/(4d)$ и $\varepsilon = (1/(4d))/c_{2d}^{O(d^3)}$. Поэтому в сыновьях достаточно деревьев глубины $O(d)$ и ветвления

$$\max\{c_{2d}^{O(d^3)}, 2^{O(k)^{4(k-1)}}\} = 2^{O(d)O(d^3)}.$$

Теорема Гача-Дея доказана. ►
**139** Докажите, что в теореме Гача – Дея глубина дерева не может быть меньше $d/4$: на дереве такой глубины (и бесконечного ветвления в каждой вершине) выигрышная стратегия есть у Менеджера, а не у Заказчика.

Верхняя оценка разницы между $КМ$ и $КА$ пока что существенно больше нижней: как мы видели, $КМ(x)$ (и даже $КР(x)$) превосходит $КА(x)$ не более чем на $O(\log n)$ для слов длины $n$. Ничего существенно лучшего не известно. Можно, впрочем, заменить $n$ на $КА(x)$, как показывает следующая задача.

**140** Докажите, что $КМ(x) \le KA(x) + O(\log KA(x))$. [Указание. Верно более сильное утверждение: $КМ(x|KA(x)) \le KA(x) + O(1)$. В самом деле, если $KA(x) = k$, то $x$ рано или поздно попадёт в растущее дерево слов априорной сложности менее $k+1$. Это дерево в каждый момент имеет ширину (максимальное число попарно несравнимых элементов) не более $2^{k+1}$, поэтому его можно покрыть не более чем $2^{k+1}$ растущими ветвями, следя за максимальными элементами дерева. Подробно см. теорему 127, с. 219.]

## 5.6. Теорема Левина – Шнорра

Определение априорной сложности гарантирует, что для любой перечислимой снизу полумеры $p$ выполняется неравенство $KA(x) \le -\log p(x) + O(1)$. Оказывается, что если $p$ является мерой, то это неравенство выполнено не только для $KA$, но и для (вообще, говоря большей) величины $KM$.

**Теорема 89.** Пусть $\mu$ — вычислимое распределение вероятностей на $\Omega$ и $p(x) = \mu(\Omega_x)$. Тогда существует такая константа $c$, что

$$КМ(x) \le -\log p(x) + c$$

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

Идею доказательства можно объяснить так: различие между $КМ$ и $КА$ возникает из-за невозможности выделить сплошные участки отрезка $[0, 1]$ по требованию. А это невозможно из-за того, что мы не знаем, какие из уже предъявленных требований возрастут, а какие нет, и не можем зарезервировать место. Но когда имеется не полумера, а вычислимая мера, то такой проблемы не возникает.

Если эти объяснения непонятны, их можно пропустить — сейчас мы изложим формальное доказательство.

Для каждого двоичного слова $x$ рассмотрим отрезок $\pi_x$ — часть отрезка $[0, 1]$, определяемую по следующим правилам (см. рис. 5.1):

* длина отрезка $\pi_x$ равна $p(x)$;

* $\pi_\Lambda = [0, 1]$ (где $\Lambda$ — пустое слово);

* для любого слова $x$ отрезок $\pi_x$ делится некоторой своей точкой на $\pi_{x0}$ (левая часть) и $\pi_{x1}$ (правая часть).

Мы будем сравнивать отрезки $\pi_x$ с аналогичными отрезками для равномерной меры: через $I_x$ мы обозначим отрезок, в котором двоичные записи чисел начинаются на $x$. Отрезки вида $I_x$ будем называть двоичными.
<figure><img src="image_15.png" /><figcaption>Рис. 5.1. Построение отрезков $\pi_x$.</figcaption></figure>

Теперь рассмотрим множество $G$ всех пар слов $\langle x, y \rangle$, для которых (двоичный) отрезок $I_x$ лежит строго внутри отрезка $\pi_y$. Множество $G$ перечислимо: поскольку функция $p$ вычислима, мы можем находить концы отрезков $\pi_y$ с любой точностью, и если они строго больше (или меньше) некоторого рационального числа, то рано или поздно это обнаружится. Кроме того, свойство $\langle x, y \rangle \in G$ сохраняется, если заменить $x$ на любое его продолжение (отрезок $I_x$ станет меньше) или заменить $y$ на любое начало (отрезок $\pi_y$ станет больше). Если $\langle x, y_1 \rangle \in G$ и $\langle x, y_2 \rangle \in G$, то отрезки $\pi_{y_1}$ и $\pi_{y_2}$ имеют общую внутреннюю точку (они оба содержат $I_x$), и потому слова $y_1$ и $y_2$ сравнимы. Поэтому по теореме 81 (с. 147) существует вычислимое отображение $\Sigma$ в себя, подграфик которого равен $G$. Используем его в качестве декомпрессора $D$ в определении монотонной сложности. При этом $KM_D(y)$ есть минус двоичный логарифм длины самого большого двоичного отрезка, лежащего строго внутри $\pi_y$. Остаётся заметить, что (строго) внутри любого отрезка длины $h$ есть двоичный отрезок длины не менее $h/4$, и воспользоваться оптимальностью. ►

[141] Проверьте, что сформулированное утверждение о двоичных отрезках действительно верно. [Указание. Пусть $u$ — степень двойки, для которой $h/4 \le u < < h/2$. Тогда отрезок длины $h$ должен пересечься по крайней мере с тремя последовательными отрезками длины $u$, и содержит внутри себя средний из них.]

Теорема 89 лежит в основе следующего способа оценки сложности (он применялся А. Н. Колмогоровым и его учениками для русских литературных текстов). Читая текст буква за буквой, экспериментатор пытается угадать следующую букву, формулируя свою догадку в виде распределения вероятностей на всех буквах алфавита. Затем открывается следующая буква и к оценке сложности добавляется величина $-\log p$, где $p$ — приписанная этой букве вероятность. Полученная величина (если считать деятельность экспериментатора вычислимой) является верхней оценкой сложности: в самом деле, экспериментатор задаёт вычислимую меру на последовательностях букв (в форме условных вероятностей следующей буквы при известном начальном отрезке), и сложность текста не больше логарифма этой меры.

Конечно, при реальном проведении таких опытов непрактично требовать явного указания вероятности для каждой из букв алфавита; разумно ограничиться каким-то классом предсказаний типа «буква А будет с вероятностью 0,5, остальные гласные равновероятны и в сумме имеют вероятность 0,3, все остальные буквы равновероятны». Отметим ещё, что происходит при этом скорее оценка сложности данного текста при условии жизненного опыта экспериментатора; ничего удивительного, что получится почти что нуль, если экспериментатор знает текст наизусть (и вообще оценка может уменьшиться, если он хорошо знаком с текстами того же автора).
Этот же приём в программах сжатия называется «арифметическим кодированием» (arithmetic coding) и даже был запатентован (много позже экспериментов Колмогорова, в 1970-е годы).

Теперь всё готово для формулировки критерия случайности (в смысле Мартин-Лёфа) в терминах монотонной сложности; последовательность случайна, если доказанное только что неравенство обращается для её начальных отрезков в равенство. Пусть $\mu$ — вычислимое распределение вероятностей на пространстве $\Omega$ бесконечных двоичных последовательностей и $p(x) = \mu(\Omega_x)$.

**Теорема 90** (Левина – Шнорра). Последовательность $\omega \in \Omega$ случайна по Мартин-Лёфу относительно $\mu$ тогда и только тогда, когда

$$- \log p(x) - KM(x) \le c$$

для некоторого $c$ и для всех начальных отрезков $x$ последовательности $\omega$.

◀ Доказательство состоит из двух частей. Для начала покажем, что если для данной последовательности $\omega$ разность $-\log p(x) - KM(x)$ принимает сколь угодно большие значения, то эта последовательность не случайна (множество $\{\omega\}$ является эффективно нулевым).

Пусть дано некоторое число $c$. Рассмотрим те слова $x$, у которых разность $-\log p(x) - KM(x)$ больше $c$. (Эту разность иногда называют дефектом случайности, но нужно быть осторожным — это слово употребляется во многих хотя и близких, но всё же различных смыслах; с одним из них мы уже встречались в предыдущей главе в применении к бесконечным последовательностям; другой описан в главе 14.) Множество таких слов обозначим $D_c$.

Множество $D_c$ перечислимо (поскольку $p$ вычислима, а $KM$ перечислима сверху, разность перечислима низку).

**Лемма 1.** Множество всех последовательностей, у которых некоторое начало принадлежит $D_c$, имеет меру не больше $2^{-c}$ (относительно рассматриваемой нами меры $\mu$).

Неформально говоря, эта лемма верна потому, что на этом множестве мера $\mu$ в $2^c$ раз меньше априорной вероятности на $\Sigma$ (а последняя в сумме не превосходит единицы). Более формально следует рассуждать так.

Рассматриваемое множество последовательностей есть объединение всех $\Omega_x$ при $x \in D_c$. В этом объединении можно оставить лишь минимальные $x \in D_c$, то есть те $x$, у которых никакие начала не принадлежат $D_c$. Пусть это будут $x_0, x_1, \dots$ (мы не утверждаем, что множество минимальных элементов будет перечислимо, так что эта последовательность может и не быть вычислимой).

Для каждого $x_i$ рассмотрим кратчайшее описание $p_i$ (согласно определению монотонной сложности: $x_i \le D(p_i)$, где $D: \Sigma \to \Sigma$ — оптимальный способ описания). Тогда $l(p_i) = KM(x_i) < -\log p(x_i) - c$. Кроме того, ни одно из $p_i$ не является началом другого (начше соответствующие $x_i$ были бы сравнимы). Поэтому $\sum_i 2^{-l(p_i)} \le 1$ (как сумма равномерных мер непересекающихся множеств $\Omega_{p_i}$). Соответствующие $p(x_i)$ в $2^c$ раз меньше, откуда и получаем требуемое. Лемма доказана.
По предположению рассматриваемая нами последовательность $\omega$ покрыта множеством из леммы при любом $c$. Поэтому, чтобы (в соответствии с определением эффективно нулевого множества) указать покрытие множества $\{\omega\}$ перечислимым семейством интервалов с суммарной $\mu$-мерой не больше $2^{-c}$, достаточно перечислить интервалы из $D_c$.

Тут, правда, возникает техническая трудность (которую мы уже обсуждали, говоря о тестах случайности). Для интервалов из $D_c$ мы знаем, что мера объединения не больше $2^{-c}$ (согласно лемме), в то время как определение требует, чтобы сумма мер интервалов не превосходила $2^{-c}$. Эту проблему нельзя решить, оставив в $D_c$ минимальные точки, поскольку их множество может уже не быть перечислимым. Вместо этого можно использовать такое утверждение:

**Лемма 2.** Всякое перечислимое множество слов $x_0, x_1, \dots$ можно преобразовать в перечислимое множество несравнимых слов, сохранив неизменным объединение $\cup_i \Omega_{x_i}$. Это преобразование эффективно (алгоритм, перечисляющий первое множество, можно вычислимо преобразовать в алгоритм перечисления второго).

В самом деле, если при перечислении появляется продолжение ранее рассмотренного слова, то его можно просто выбросить (соответствующий интервал в объединении и так покрыт). Если же появляется слово $y$, являющееся (собственным) началом ранее рассмотренного слова $x$, то нужно разбить добавляемое множество $\Omega_y \setminus \Omega_x$ в объединение интервалов и заменить $y$ на слова, задающие эти интервалы. Лемма 2 доказана.

После применения леммы 2 мы получаем перечислимое множество несравнимых слов; заметим, что эти слова уже не обязательно принадлежат $D_c$, но это и не важно. Достаточно, что они задают непересекающиеся интервалы и что объединение этих интервалов (согласно лемме 1) имеет $\mu$-меру не более $2^{-c}$.

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

Более подробно. Пусть последовательность $\omega$ принадлежит эффективно нулевому (по мере $\mu$) множеству $U$. Для каждого $c$ можно эффективно указать покрытие множества $U$ интервалами $\Omega_{x_0}, \Omega_{x_1}, \dots$, имеющими суммарную меру меньше $2^{-c}$. Если увеличить меры всех этих интервалов в $2^c$ раз, то их сумма останется меньше единицы. Применив к последовательности $p_i = 2^c \mu(\Omega_{x_i})$ теорему 59 (с. 112), мы получаем беспрефиксный способ описания, для которого сложность $i$ не превосходит $-\log \mu(\Omega_{x_i}) - c + 2$. Композиция этого способа описания с вычислимым отображением $i \mapsto x_i$ даёт беспрефиксный способ описания $D_c$, у которого

$$KP'_{D_c}(x_i) \le -\log \mu(\Omega_{x_i}) - c + 2.$$

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

По аналогии с построением оптимального способа описания будем считать, что $\hat{c}$ является описанием слова $v$, если $v$ является описанием слова $v$ относительно $D_c$. Здесь $\hat{c}$ — самоограниченная запись натурального числа $c$ длины $O(\log c)$. Для построенного способа описания $D$ уже можно написать неравенство, верное при всех $c$:

$$KP'_{D}(x_i) \le -\log \mu(\Omega_{x_i}) - c + O(\log c).$$

Поскольку монотонная сложность не превосходит префиксной, можно заменить $KP'_{D}(x_i)$ на $KM(x_i)$ и заключить, что у всех слов $x_i$ (для данного $c$) разность между минус логарифмом меры и монотонной сложностью не меньше $c - O(\log c)$. Для каждой последовательности из $U$ можно найти начало такого вида при любых $c$, поэтому разности между минус логарифмом меры и монотонной сложностью для начальных отрезков этой последовательности не ограничены.

Теорема Левина – Шнорра доказана. ►

**142** Показите, что в первой части доказательства (если разность не ограничена, то последовательность содержится в эффективно нулевом множестве) достаточно перечислимости $P$ сверху, а во второй части — снизу.

Приведённое доказательство теоремы Шнорра по существу доказывает немного больше. Вот что ещё из него можно заключить:

**Теорема 91.** В формулировке теоремы можно заменить монотонную сложность $KM(x)$ на априорную сложность $KA(x)$.

◀ Априорная сложность меньше, поэтому разность при переходе к априорной сложности только увеличится; остаётся доказать первую часть теоремы для априорной сложности. Для этого достаточно заметить при доказательстве леммы 1, что $\sum_i 2^{-KA(x_i)} \le 1$, поскольку эта сумма является суммой априорных вероятностей непересекающихся интервалов $\Omega_{x_i}$. ►

**Теорема 92.** В формулировке теоремы можно заменить монотонную сложность $KM(x)$ на префиксную сложность $KP(x)$.

◀ Здесь, напротив, мы увеличиваем сложность, а не уменьшаем, так что сравнения вызываем лишь вторая часть теоремы. Но в доказательстве мы как раз и получали оценку для префиксной сложности. ►

Именно такой критерий случайности («теорема Левина – Шнорра в форме Чейтина») сейчас наиболее распространён (см., например, [85]; об истории вопроса можно прочесть в обзоре [11]).

С философской точки зрения авторам кажется более естественным использовать монотонную (или априорную) сложность, хотя и префиксная сложность имеет свой резон (см. ниже выражение для дефекта случайности через префиксную сложность). Заметим, например, что при использовании префиксной сложности разность, о которой идёт речь в критерии случайности, может быть и отрицательной: скажем, для равномерной меры величина $-\log \mu(\Omega_x)$ есть длина слова $x$, а
префиксная сложность может превышать длину (на величину порядка логарифма длины), см. теорему 63, см. 117.

Кроме того, использование монотонной или априорной сложности позволяет усилить теорему следующим образом:

**Теорема 93.** Если последовательность $\omega$ не случайна (в смысле Мартин-Лёфа) по мере $\mu$, то величина $-\log p(x) - KM(x)$ не только не ограничена для её начальных отрезков, но и стремится к бесконечности.

◀ Вспомним доказательство: в нём для последовательности слов $x_i$ строился беспрефиксный способ описания, при котором слово $x_i$ имело описание $p_i$, причём длина $p_i$ (и тем самым префиксная сложность $x_i$ при этом способе описания) не превосходила $-\log \mu(\Omega_{x_i}) - c$. Чтобы получить нужную оценку для монотонной сложности, мы можем использовать (при каждом $i$) продолжения слова $p_i$ в качестве описаний продолжений слова $x_i$, при этом длина первых соответствует логарифму меры вторых, как это делалось при доказательстве теоремы 89 (с. 165).

Более формально можно воспользоваться неравенством $KM(xy) \le KP(x) + KM(y|x)$ (задача 135) и релятивизованным вариантом теоремы 89, утверждающим, что $KM(y|x) \le -\log \mu_x(\Omega_y)$ для любого вычислимого семейства мер, (вычислимо) зависящего от параметра $x$. При этом в качестве $\mu_x$ нужно взять меру, сосредоточенную на продолжениях слова $x$, для которой $\mu_x(\Omega_y) = \mu(\Omega_{xy})/\mu(\Omega_x)$.

Для случая равномерной меры (когда $-\log \mu(\Omega_x) = l(x)$) всё упрощается и можно просто сказать, что слово $p_iz$ является описанием слова $x_iz$ для любого слова $z$. ►

Для префиксной сложности это рассуждение уже не проходит, но для вычи-
слимой последовательности длин утверждение остаётся верным:

143 Пусть $A$ — разрешимое бесконечное множество длин (натуральных чисел), а $\omega$ — последовательность. Если $KP(x) \ge -\log \mu(\Omega_x) - c$ для некоторого $c$ и для любого начала $x$ последовательности $\omega$, длина которого принадлежит $A$, то $\omega$ случайна. [Указание. В доказательстве теорем 90 и 92 можно измельчать интервалы до нужного размера.]

Мы привели доводы в пользу использования монотонной сложности для ха-
рактеризации случайности по Мартин-Лёфу. С другой стороны, характеризация
случайности в терминах сложности начальных отрезков имеет некоторый дефект: в
то время как случайность последовательности нулей и единиц инвариантна относи-
тельно вычислимых перестановок индексов (и соответствующего изменения меры),
понятие начального отрезка и тем самым критерий случайности в терминах на-
чальных отрезков таковым не является. Как заметил Андрей Румянцев, используя
префиксную сложность, можно модифицировать критерий случайности, сделав его
инвариантным.

Пусть $F$ — конечное множество натуральных чисел, а $\omega$ — последовательность нулей и единиц. Через $\omega(F)$ будем обозначать сужение $\omega$ на $F$, то есть двоичное слово, образованное битами $\omega_i$ при $i \in F$ (в порядке возрастания индексов).
Пусть фиксирована вычислимая мера $\mu$ на $\Omega$. Для данного множества $F$ и слова $Z$, длина которого равна числу элементов $F$, можно рассмотреть событие $\omega(F) = Z$. Его вероятность будем обозначать $\mu_{F,Z}$.

**144** Докажите, что если последовательность $\omega$ случайна (в смысле Мартин-Лёфа) относительно меры $\mu$, то найдётся такое $c$, что

$$KP(F, \omega(F)) \geq -\log \mu_{F,\omega(F)} - c$$

для любого конечного множества $F$.

[Указание. Мера множества последовательностей, где это условие нарушается для фиксированного $c$, не превосходит $2^{-c}$, умноженного на сумму априорных вероятностей всех пар $F, Z$, то есть не больше $2^{-c}$.]

(Заметим, что если $F$ — начальный отрезок, то $F$ восстанавливается по $\omega(F)$, так что мы приходим к прежней формулировке.)

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

**145** Пусть $F_0 \subset F_1 \subset F_2 \subset \dots$ — вычислимая последовательность конечных множеств, в объединении дающих всё $\mathbb{N}$. Если для некоторой последовательности $\omega$ и для некоторого $c$ неравенство

$$KP(F_i, \omega(F_i)) \geq -\log \mu_{F_i, \omega(F_i)} - c$$

выполнено при всех $i$, то последовательность $\omega$ случайна в смысле Мартин-Лёфа по мере $\mu$.

[Указание: удобно переставить индексы и считать, что $F_i$ — начальные отрезки. Далее нужно воспользоваться задачей 143: повторить доказательство теоремы Левина – Шнорра, но использовать только интервалы нужных длин (измельчая неформатные).]

Из этого утверждения следует, например, что двумерная последовательность битов (отображение $\mathbb{Z}^2 \to \{0,1\}$) случайна в смысле Мартин-Лёфа по равномерной мере (все биты независимы, нули и единицы равновероятны) тогда и только тогда, когда любой квадрат $N \times N$ с центром в начале координат (при всех нечётных $N$) имеет префиксную сложность не меньше $N^2 - O(1)$.

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

**146** Пусть $\mu$ — вычислимая мера на пространстве $\Omega$. Покажите, что функция

$$t(\omega) = \sum_{x \le \omega} \frac{m(x)}{\mu(x)}$$

(сумма по всем конечным началам $x$ последовательности $\omega$; через $m(x)$ обозначается дискретная априорная вероятность слова $x$, а $\mu(x)$ обозначает меру интервала $\Omega_x$ является универсальным ограниченным в среднем тестом случайности.)
[Указание. Будем представлять себе перечислимую снизу функцию как сумму
характеристических функций интервалов с коэффициентами. Добавление нового
члена в такую сумму можно представлять себе как увеличение «веса» двоичного
слова, если значением функции на последовательности считать сумму весов вдоль
неё. Веса слов в таком случае должны быть перечислимой снизу функцией u на
словах, а условие на интеграл записывается как $\sum_x \mu(x)u(x) \le 1$. Максимальная
такая функция отличается от $m(x)$ множителем $1/\mu(x)$. Ещё надо уточнить, что
при $\mu(x) = 0$ для некоторого х дробь $m(x)/\mu(x)$ считается бесконечной.]

**147** Покажите, что в предыдущей задаче можно заменить сумму на максимум (точную верхнюю грань) и тем самым получить количественный вариант критерия случайности с префиксной сложностью. (Напимер, для случая равномерной меры ограниченный в среднем дефект случайности равен $\sup_n[n - KP(\omega_0 \dots \omega_{n-1})]$.)

[Указание. Перечислимую снизу функцию, которая принимает рациональное значение *a* в некотором эффективно открытом множестве и равна нулю снаружи, можно представить с помощью весов, равных *a* и размещённых в несравнимых вершинах. Любую перечислимую функцию *t* можно представить с точностью до постоянного множителя как сумму $t(\omega) = \sum t_k(\omega)$, где $t_k(\omega) = 2^k$, если $t(\omega) > 2^k$, и $t_k(\omega) = 0$ в противном случае. Представив $t_k$ как описано выше, мы добьёмся, чтобы в сумме предыдущей задачи все слагаемые были разными степенями двойки. Тогда сумма совпадает с наибольшим слагаемым с точностью до $O(1)$-множителя.]

Утверждение последней задачи было доказано в давней статье Гача [44]. По ходу доказательства в ней получается и утверждение задачи 146, которое недавно было переоткрыто Миллером и Ю и получило название "ample excess lemma" [105].

**148** (а) Покажите, что если последовательность $\omega$ случайна по вычислимой мере $\mu$, то разница $-\log \mu(x) - KP(x)$ не только ограничена сверху для начальных отрезков последовательности $\omega$, но и стремится к минус бесконечности с ростом длины начального отрезка. Другими словами, если $KP(x) \le -\log \mu(x) + c$ для некоторого $c$ и для бесконечно многих начальных отрезков некоторой последовательности $\omega$, то эта последовательность не случайна.

(б) Покажите, что если $KP(x) \le -\log \mu(x) + \log l(x) + c$ для некоторого $c$ и для всех начальных отрезков последовательности $\omega$, то эта последовательность не случайна (всюду имеется в виду случайность по Мартин-Лёфу).

[Указание: в обоих случаях утверждение вытекает из леммы об "ample excess" (задача 146).]

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

**Теорема 94.** (а) Оценка сверху: для любого слова $x$ выполнены неравенства

$$KA(x) \le KM(x) + O(1) \le l(x) + O(1).$$

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

$$KA((\omega)_n) = KM((\omega)_n) + O(1) = n + O(1).$$

(в) Для неслучайной (в смысле Мартин-Лёфа) по равномерной мере последовательности $\omega$ разность $n - KM((\omega)_n)$, и тем более $n - KA((\omega)_n)$, стремится к бесконечности.

(г) Последовательность $\omega$ случайна (в смысле Мартин-Лёфа) по равномерной мере тогда и только тогда, когда $KP((\omega)_n) \ge n - c$ для некоторого $c$ и для всех $n$. В этом случае $KP((\omega)_n) - n \to +\infty$ при $n \to \infty$. (Таким образом, нижний предел разности $KP((\omega)_n) - n$ равен $-\infty$ для неслучайной последовательности и $+\infty$ для случайной; промежуточные варианты невозможны.)

(д) Последовательность $\omega$ случайна (в смысле Мартин-Лёфа) по равномерной мере тогда и только тогда, когда $KP(F, \omega(F)) \ge |F| - c$ для некоторого $c$ и для всех конечных множеств $F$.

Другой вариант утверждения (г): последовательность $\omega$ случайна тогда и только тогда, когда сумма $\sum_n 2^{n-KP((\omega)_n)}$ конечна (задача 146).

Имеется ещё один критерий случайности по Мартин-Лёфу для случая равномерной меры, который интересен тем, что в нём можно ограничиться использованием обычной колмогоровской сложности (и обойтись без монотонной или префиксной). Даже удивительно, что этот критерий был найден только недавно (см. [105]), по скольку этим занимались ещё в конце 1960-х годов и подошли к нему очень близко (см. [196, 99]), а его доказательство достаточно просто и естественно и не выходит из круга идей, хорошо известных в то время.

**Теорема 95.** Пусть $f: N \to N$ — вычислимая функция и ряд $\sum 2^{-f(n)}$ сходится. Пусть $\omega$ — случайная (в смысле Мартин-Лёфа) по равномерной мере последовательность. Тогда

$$KS((\omega)_n | n) \ge n - f(n) - O(1)$$

(найдётся $c$, при котором для всех $n$ выполнено неравенство $KS((\omega)_n | n) \ge n - f(n) - c$).

◀ Пусть утверждение теоремы не выполнено. Это значит, что для любого $c$ найдётся такое $n$, что

$$KS((\omega)_n | n) < n - f(n) - c.$$

Другими словами, каково бы ни было $c$, последовательность $\omega$ покрыта некоторым интервалом $\Omega_x$, для которого

$$KS(x | n) < n - f(n) - c,$$

где $n$ — длина $x$. Для каждого $n$ таких интервалов не более $2^{n-f(n)-c}$, поэтому их суммарная мера не более $2^{-f(n)}2^{-c}$ при данном $n$ и не более

$$2^{-c} \left( \sum_n 2^{-f(n)} \right)$$
для интервалов всех длин. Поэтому последовательность $\omega$ образует эффективно нулевое множество: выбирая нужное $c$, получаем покрытие сколь угодно малой меры. Значит, она не случайна. (Заметим, что сумма ряда $\sum 2^{-f(n)}$ может быть невычислимой; это не важно, так как мы можем использовать любую верхнюю оценку для этой суммы.) ►

**Замечание.** В рассуждении мы использовали только перечислимость сверху, поэтому эта теорема верна при $f(n) = KP(n)$: для любой случайной по равномерной мере последовательности $\omega$ выполнено неравенство $KS((\omega)_n|n) \ge n - KP(n) - O(1)$. Как мы увидим в теореме 98, это условие является необходимым и достаточным.

Из теоремы 95 следует, например, что для случайной последовательности (по равномерной мере) обычная сложность начальных отрезков не меньше $n - 2 \log n$ – $O(1)$ или даже $n - \log n - 2 \log \log n - O(1)$, поскольку соответствующие ряды сходятся.

Чем меньше функция $f$, тем ближе ряд к расходящемуся и тем более сильным является утверждение теоремы. Оказывается, что при некоторых $f$ оно становится критерием случайности.

**Теорема 96.** Существует всюду определённая вычислимая функция $f$ с нату-
ральными аргументами и значениями, для которой $\sum_n 2^{-f(n)} < \infty$, обладающая
таким свойством: если для некоторой последовательности $\omega$ и для некоторого
с при всех $n$ выполнено неравенство

$$
KS((\omega)_n | n) \ge n - f(n) - c,
$$

то последовательность $\omega$ случайна (в смысле Мартин-Лёфа) по равномерной
мере.

◀ Нам нужно доказать, что любая неслучайная последовательность (то есть лю-
бая последовательность, содержащаяся в наибольшем эффективно нулевом множе-
стве) имеет «простые» начальные отрезки. При этом критерий «простоты» (точнее,
функцию $f$) нам предстоит выбирать самим.

Как это делается? Пусть, скажем, у нас есть некоторое семейство интервалов с
суммой длин не более $\varepsilon$. Пусть $F$ — множество задающих их двоичных слов (се-
мейство состоит из интервалов $\Omega_u$ при $u \in F$). Рассортируем слова множества $F$
(и тем самым интервалы семейства) по длинам и подсчитаем для каждого $n$ сум-
марную меру интервалов, соответствующих словам длины $n$. Выберем функцию $f$
таким образом, чтобы эта мера была примерно равна $2^{-f(n)}$. (Поскольку по усло-
вию $f(n)$ должно быть целым, то это равенство нельзя сделать точным, но можно
добиться ошибки не более чем в 2 раза. Для простоты мы не будем этого учи-
тывать.) Тогда по построению сумма ряда $\sum_n 2^{-f(n)}$ не превосходит $\varepsilon$. С другой
стороны, в $F$ имеется примерно $2^{n-f(n)}$ слов длины $n$ и каждое из них может быть
описано (при известном $n$ и других параметрах конструкции) своим номером, тре-
бующим $n - f(n)$ битов, что даёт верхнюю оценку сложности для слов из $F$. При
этом всякая покрытая нашими интервалами последовательность имеет начальный
отрезок в множестве $F$.
Как это соображение можно применить в нашей ситуации? Рассмотрим наи-
большее эффективно нулевое множество. Для любого ε > 0 имеется его покрытие
интервалами с суммой длины не больше ε, и описанным способом из этого покрытия
получается функция f с $\sum_n 2^{-f(n)} \le ε$. Далее нам нужно как-то соединить такие
функции для разных ε в одну. Будем делать это следующим образом.

Для каждого $c = 0, 1, 2, \dots$ рассмотрим покрытие с суммой мер меньше $2^{-3c}$ и построим по нему функцию $f$ описанным способом, а затем уменьшим её на $2c$. Таким образом для каждого $c$ мы получим функцию $f_c$, для которой

$$
\sum_n 2^{-f_c(n)} < 2^{-c}
$$

(вместо $2^{-3c}$ мы получаем $2^{-c}$, поскольку уменьшили функцию на $2c$), и множество слов $F_c$, содержащее $2^{n-f_c(n)-2c}$ слов длины $n$, причём любая неслучайная последовательность имеет начальный отрезок в $F_c$.

Далее мы определим $f(n)$ равенством

$$
2^{-f(n)} = \sum_{c} 2^{-f_c(n)},
$$

тогда

$$
\sum_n 2^{-f(n)} = \sum_n \sum_c 2^{-f_c(n)} = \sum_c \sum_n 2^{-f_c(n)} \le \sum_c 2^{-c} \le 1,
$$

и при этом $f(n) \le f_c(n)$ при любых $n$ и $c$. С другой стороны, множество $F_c$ пере-
числимо равномерно по $c$ (это гарантируется определением эффективно нулевого
множества), и потому любое слово $x$ длины $n$ в $F_c$ может быть задано (при из-
вестных $n$ и $c$) своим порядковым номером в перечислении, который содержит
$n - f_c(n) - 2c$ битов:

$$
KS(x | n, c) \le n - f_c(n) - 2c + O(1),
$$

откуда

$$
KS(x | n) \le n - f_c(n) - 2c + O(\log c) < n - f(n) - c
$$

для любого слова $x \in F_c$ длины $n$ (при достаточно больших $c$).

Пусть теперь $\omega$ — неслучайная последовательность. Из сказанного следует,
что она (для каждого $c$) имеет начало в $F_c$; если $n$ — длина этого начала (и $c$
достаточно велико), то

$$
KS((\omega)_n | n) < n - f(n) - c,
$$

что противоречит предположению теоремы.

Это рассуждение, однако, ещё не доказывает теорему — в ней требуется, чтобы функция $f$ была вычислима, в то время как $F_c$ мы можем лишь перечислять (и ни в какой момент не можем быть уверены, что больше слов данной длины не будет). Вспомним, однако, что нас интересуют покрытия интервалами, и в этих покрытиях можно заменить один большой интервал $\Omega_z$ на много маленьких $\Omega_{zt}$,
если в качестве *t* взять все слова некоторой фиксированной длины. За счёт этого можно добиться вычислимости функции $f_c$ — надо договориться, что минимально разрешённая длина выдаваемого при перечислении слова растёт со временем. Тогда количество выдаваемых слов длины *n* является вычислимой функцией от *n*, так как они могут появляться только до некоторого заранее известного момента. Это рассуждение можно провести параллельно для всех *c*, и тогда сумма $\sum_c 2^{-f_c(n)}$ также будет вычислима по *n*.

Наконец, имеется ещё совсем техническая трудность: мы строим функцию $f$ с натуральными значениями, поэтому надо её ещё округлить. ►

Две предыдущие теоремы вместе дают критерий случайности, в котором используется обычная (а не монотонная или префиксная) сложность. Этот критерий имеет некоторый «запас». А именно, можно заменить условную сложность $KS((\omega)_n|n)$ на безусловную сложность $KS((\omega)_n)$ или на условную префиксную сложность $KP((\omega)_n|n)$.

В самом деле, при такой замене сложность только увеличится, поэтому адаптации требует лишь теорема 96. Вариант с префиксной сложностью: надо воспользоваться тем, что для любого конечного множества $A$ и любого элемента $x \in A$ справедливо неравенство $KP(x|A) \le \log_2 |A| + O(1)$ (можно рассмотреть беспрефиксное кодирование словами длины $\log_2 |A|$). Немного сложнее удалить условие $n$ (для обычной, не префиксной сложности). В этом случае слово $x \in F_c$, имеющее длину $n$, надо задавать не его порядковым номером в множестве $F_{c,n}$ слов длины $n$ из множества $F_c$, а номером во всём $F_c$ (расположенном в порядке возрастания длин). Соответственно число битов, необходимое для этого, есть

$$ \log(|F_{c,0}| + |F_{c,1}| + \dots + |F_{c,n}|), $$

и всё будет в порядке, если последний член $|F_{c,n}|$ больше всех предыдущих вместе взятых (тогда порядковый номер увеличится не более чем в два раза от добавления предыдущих членов). Ясно, что этого можно достичь тем же приёмом (заменяя короткое слово на все его продолжения некоторой длины). Заметим, что это делается при данном $c$, то есть условие $c$ остаётся, но это не страшно (в итоге оно даёт вклад $O(\log c)$).

Отсюда получаем такой результат:

**Теорема 97.** Случайность последовательности $\omega$ (в смысле Мартин-Лёфа) по равномерной мере равносильна тому, что для любой вычислимой функции $f$ с конечной суммой ряда $\sum_n 2^{-f(n)}$ выполнено свойство

$$ KS((\omega)_n) \ge n - f(n) - O(1). $$

Этот критерий использует простую колмогоровскую сложность и именно его обычно называют «теоремой Миллера – Ю».

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

**Теорема 98.** Последовательность $\omega$ является случайной (в смысле Мартин-Лёфа) относительно равномерной меры тогда и только тогда, когда

$$KS((\omega)_n) \ge n - KP(n) - O(1).$$

◀ Если ряд $\sum_n 2^{-f(n)}$ сходится (для вычислимой функции $f$), то $KP(n) \le f(n) + O(1)$. Поэтому приведённое в теореме условие на $\omega$ сильнее, чем в теореме 97.

Таким образом, остаётся доказать утверждение в другую сторону, что мы уже обсуждали в замечании после теоремы 95. ▶

Заметим, что и в этой теореме можно заменить $KS((\omega)_n)$ на $KS((\omega)_n|n)$ (годится то же самое рассуждение).

**149** Убедитесь в этом.

Этот результат был доказан в работе Гача [44] (с. 391).

**150** Покажите, что в теореме 96 нельзя положить $f(n) = 2 \log n$. [Указание. Из теоремы 95 следует, что для случайной последовательности $\omega$ выполняется более сильное неравенство $KS((\omega)_n) \ge n - \log n - 2 \log \log n - O(1)$. Поэтому, если разбавить её очень редкими нулями на вычислимых местах, то получится последовательность, для которой $KS((\omega)_n) \ge n - 2 \log n - O(1)$, но не случайная. Аналогичное рассуждение показывает, что не годится никакая функция с вычислимоходящимся рядом $\sum 2^{-f(n)}$.]

Всё сказанное до сих пор, однако, не отвечает на естественный вопрос: а нельзя ли вообще обойтись без функции $f$ и потребовать, чтобы $KS((\omega)_n)$ было больше $n - O(1)$ (как для монотонной сложности)?

Такое требование было бы самым естественным, но, как сразу же заметил Мартин-Лёф, ничего хорошего не получается: если в последовательности встречаются сколь угодно длинные участки из нулей, то есть начальный отрезок длины $n$, который кончается на $k$ нулей (при большом $k$). Его сложность не больше $n - k + 2 \log k + O(1)$ (для беспрефиксного кодирования числа $k$ достаточно $2 \log k$ битов), и разница с длиной будет $k - 2 \log k - O(1)$. Если же в последовательности нет идущих подряд $k$ нулей (при некотором $k$), то сложность её начальных отрезков длины $n$ ограничена $\alpha n + O(1)$ при некотором $\alpha < 1$.

Можно оценить неизбежную разницу между длиной и сложностью более точно (см. [196, 99]):

**Теорема 99.** Найдётся такая константа $c$, что для любой последовательности $\omega \in \Omega$ при бесконечно многих $n$ выполнено неравенство

$$KS((\omega)_n) \le n - \log n + c.$$

◀ Для каждого $n$ выделим среди слов длины $n$ некоторую часть, составляющую $1/n$ от всех слов длины $n$. При этом сделаем это так, чтобы у любой бесконечной
последовательности было бесконечно много выделенных начал и чтобы множество выделенных слов было разрешимо.

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

Любое выделенное слово длины $n$ задается (при известном $n$) своим порядковым номером, который имеет $n - \log n$ битов. Поэтому его условная сложность (при известном $n$) не больше $n - \log n + O(1)$. Более того, если нумеровать все выделенные слова подряд, то порядковый номер не сильно увеличивается (число выделенных слов растёт почти как геометрическая прогрессия с показателем 2, и добавление всех предыдущих слов увеличивает их число не более чем в $O(1)$ раз).

Отсюда и следует утверждение теоремы. ►

**151** Предложите другое доказательство, использующее такое простое соображение: начало длины $k$ любой последовательности можно рассматривать как двоичную запись некоторого числа $N$ (можно приписать вначале единицу, чтобы не потерять нули), и следующие за этим началом $N$ битов последовательности позволяют восстановить все $k + N$ битов.

**152** Покажите, что утверждение теоремы верно не только для некоторого $c$, но и для всех $c$ (в том числе отрицательных). [Указание. Если ряд $\sum 2^{-f(n)}$ расходится, то можно немного увеличить функцию $f$, сохранив это свойство: найдётся функция $g$, для которой $g(n) - f(n) \to \infty$ и ряд $\sum 2^{-g(n)}$ расходится.]

**153** Покажите, что в теореме 99 (в варианте с условной сложностью) можно заменить логарифм на любую вычислимую функцию $f$, для которой ряд $\sum 2^{-f(n)}$ расходится.

В статье Мартин-Лёфа [99] без доказательства (со ссылкой на его неопубликованную работу) приводится утверждение с безусловной сложностью и произвольной вычислимой функцией $f$ с расходящимся рядом. Этот результат (также без доказательства и со ссылкой на Мартин-Лёфа) приведён и в обзоре [196]. (Как его доказать, мы не знаем.)

Отметим также, что утверждение теоремы 95 приведено в статье [99] в немного другом варианте:

**154** Докажите, что если последовательность $\omega$ случайна (в смысле Мартин-Лёфа по равномерной мере), а функция $f$ вычислима и ряд $\sum 2^{-f(n)}$ вычислимо сходится, то $\mathrm{KS}((\omega)_n | n) \ge n - f(n)$ для всех $n$, кроме конечного числа. [Указание. Если ряд вычислимо сходится, а неравенство нарушается бесконечно много раз, то хвосты ряда можно использовать для получения покрытий сколь угодно малой меры.]
А что будет, если требовать большой сложности начального отрезка не для всех (достаточно длинных) отрезков, а для бесконечного их числа? В той же статье Мартин-Лёфа [99] приводятся следующие результаты:

**155** Докажите, что для почти всех (по равномерной мере) последовательностей $\omega$ найдётся $c$, при котором $KS((\omega)_n|n) \ge n - c$ для бесконечно многих $n$.

[Указание: если это не так, то для всякого $c$ найдётся $N$, начиная с которого начальные отрезки длины $n$ имеют сложность меньше $n - c$. Для данных $c$ и $N$ множество таких последовательностей имеет меру меньше $2^{-c}$; с ростом $N$ множество растёт и объединение по $N$ имеет меру не больше $2^{-c}$ по непрерывности.]

**156** Пусть $KS((\omega)_n|n) \ge n - c$ для некоторой константы $c$ и бесконечно многих $n$. Тогда последовательность $\omega$ случайна в смысле Мартин-Лёфа (по равномерной мере). [Указание. Если $\omega$ покрыта одним из интервалов с общей мерой меньше $2^{-c}$, то достаточно длинные её начальные отрезки (при известной длине) можно описать порядковым номером среди слов данной длины, попадающих в один из этих интервалов, для чего достаточно $2 \log c + n - c$ битов.]

**157** Покажите, что утверждение предыдущей задачи можно усилить, заменив условную сложность на безусловную $KS((\omega)_n)$. [Указание: можно воспользоваться задачей 6 или, что ещё проще, задачей 55.]

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

Сравнительно недавно выяснилось, что это за множество — оказывается, это множество всех последовательностей, случайных в смысле Мартин-Лёфа с оракулом $0'$. Такие последовательности иногда называют «2-случайными» (а случайные по Мартин-Лёфу в обычном смысле, без оракула, называют «1-случайными»). См. [103, 128]; простое доказательство приведено в [9]. Аналогичный критерий 2-случайности можно сформулировать и в терминах префиксной сложности: надо потребовать, чтобы $KP((\omega)_n)$ было не меньше $n + KP(n) - c$ для некоторого $c$ и для бесконечно многих $n$ ([197], простое доказательство в [198]).

## 5.7. Случайное число Ω

Интересное применение критерия случайности составляет следующая теорема. Пусть $m$ — максимальная перечислимая снизу полумера на множестве натуральных чисел (например, $m(x) = 2^{-KP(x)}$, или распределение на выходе универсального вероятностного алгоритма, см. главу 4). Г. Чейтин предложил рассмотреть число

$$ \Omega = \sum_{n} m(n) $$

(которое можно назвать общей вероятностью остановки универсального вероятностного алгоритма) и сделал такое интересное наблюдение:
**Теорема 100.** Двоичная запись числа Ω является случайной по Мартин-Лёфу последовательностью относительно равномерной меры.

Заметим, что значение Ω зависит от выбора конкретной максимальной перечислимой снизу полумеры, но утверждение теоремы остаётся верным при любом таком выборе.

◀ Пусть нам известны первые $n$ двоичных знаков числа Ω. Они образуют число $\Omega_n$, которое есть приближение снизу к Ω с погрешностью не более $2^{-n}$. Будем перечислять снизу приближения к $m(0), m(1), ...$ параллельно, постепенно добавляя всё новые $m(i)$, пока найденные числа в сумме не дадут больше $\Omega_n - 2^{-n}$. (Такое рано или поздно случится, так как сумма ряда равна Ω и строго больше выбранной нами границы.) Составим список всех чисел $i$, которые встречаются в этой сумме.

Заметим, что в этом списке встречаются все числа $i$, у которых $m(i) \ge 2 \cdot 2^{-n}$ (поскольку если бы такое число было пропущено, то погрешность была бы больше $2^{-n}$), и в том числе все $i$ с $KP(i) < n - c$ (для некоторого $c$, зависящего от выбора функции $m$, но не от $n$). Поэтому минимальное число, не входящее в этот список, имеет сложность не меньше $n - c$. Значит, и сам этот список, и двоичное разложение числа $\Omega_n$, по которому этот список построен, имеют сложность не меньше $n - c'$ для некоторого другого $c'$ и для всех $n$. (Заметим, что это двоичное разложение определяет $n$, так что значение $n$ не надо указывать отдельно.) Остаётся воспользоваться критерием случайности с префиксной сложностью (см. теоремы 92 и 94). ►

Как мы уже говорили, можно сразу определять случайность действительных чисел в смысле Мартин-Лёфа (относительно обычной меры на прямой), если в определении эффективно нулевого множества требовать наличия алгоритма, который по каждому рациональному $\epsilon > 0$ выдаёт покрытие интервалами с рациональными концами и суммарной мерой не более $\epsilon$.

**158** Покажите, что определённая таким образом случайность равносильна случайности последовательности знаков в двоичном разложении.

**159** Покажите, что квадрат (синус, экспонента) случайного действительного числа случаен. [Указание. Прообраз множества меры нуль имеет меру нуль, и это можно эффективизировать.]

**160** Всегда ли сумма двух случайных действительных чисел случайна? [Указание: они могут быть «ависимы».]

На самом деле число Ω (точнее, числа типа Ω, поскольку для разных максимальных полумер они разные) — не просто любопытный курьёз. Оказывается, что класс таких чисел имеет несколько эквивалентных описаний [17, 70]. Мы приведём их, следуя [84].

### 5.7.1. Сводимость и полнота по Соловьею

Напомним, что действительное число $\alpha$ перечислимо снизу, если оно является пределом возрастающей вычислимой последовательности рациональных чисел. (Эквивалентное определение: если множество рациональных чисел, меньших $\alpha$,
перечислимо.) Желая как-то сравнивать скорость сходимости таких последовательностей, введём следующее определение.

Пусть $a_i \to \alpha$ и $b_i \to \beta$ — две строго возрастающие вычислимые последовательности, сходящиеся соответственно к $\alpha$ и $\beta$. Мы говорим, что $a_i$ «лучше сходится» к $\alpha$, чем $b_i \to \beta$, если существует всюду определённая вычислимая функция $h$, для которой

$$\alpha - a_{h(i)} \le \beta - b_i$$

для любого $i$. (Точнее следовало бы говорить «не хуже» вместо «лучше».)

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

Это позволяет дать такое определение: мы говорим, что $\alpha \prec_1 \beta$ (для двух перечислимых снизу чисел $\alpha$ и $\beta$), если возрастающая вычислимая последовательность $a_i \to \alpha$ сходится лучше, чем аналогичная последовательность $b_i \to \beta$.

Как мы уже говорили, выбор последовательностей тут не играет роли; можно не упоминать их и в определении, сказав, что $\alpha \prec_1 \beta$, если существует частичная вычислимая функция $\varphi$, определённая на всех рациональных числах $r < \beta$, для которой

$$\varphi(r) < \alpha \text{ и } \alpha - \varphi(r) \le \beta - r$$

для всех $r < \beta$.

**161** Докажите, что перечислимое снизу число $\alpha$ вычислимо тогда и только тогда, когда $\alpha \prec_1 \beta$ для любого перечислимого снизу числа $\beta$.

Вот ещё одна полезная эквивалентная формулировка:

**Теорема 101.** Соотношение $\alpha \prec_1 \beta$ выполнено тогда и только тогда, когда разность $\beta - \alpha$ перечислима снизу, то есть $\beta = \alpha + \rho$ для некоторого перечислимого снизу $\rho$.

◀ Заметим прежде всего, что если $\alpha$ и $\rho$ перечислимы снизу, то $\alpha \prec_1 \alpha + \rho$. В самом деле, имея $s < \alpha + \rho$, мы можем подождать, пока сумма растущих приближений к $\alpha$ и $\rho$ не превзойдёт $s$. В этот момент точность текущего приближения к $\alpha$ будет не хуже, чем к $\alpha + \rho$.

Остаётся доказать обратное: если $\alpha \prec_1 \beta$, то $\rho = \beta - \alpha$ перечислимо снизу. В самом деле, пусть вычислимая возрастающая последовательность $b_n$ сходится к $\beta$. Найдём для каждого её члена приближение $a_n$ к $\alpha$ с такой же или меньшей погрешностью. Тогда $b_n - a_n \le \beta - \alpha$ и $b_n - a_n \to \beta - \alpha$. Правда, последовательность $b_n - a_n$ может не быть возрастающей, но это легко поправить, заменив её $n$-й член на максимум из первых $n$ членов. ▶
Частным случаем этой теоремы является такое утверждение: пусть даны два вычислимых ряда $\Sigma a_i$ и $\Sigma b_i$ из неотрицательных рациональных чисел (кроме, быть может, $a_0$ и $b_0$, которые могут быть и отрицательными). Если $a_i \le b_i$ при всех $i > 0$, то для их сумм $\alpha$ и $\beta$ выполнено $\alpha \le 1 \le \beta$.

Верно и обратное утверждение: если $\alpha \le 1 \beta$, то можно найти ряды $\Sigma a_i = \alpha$ и $\Sigma b_i = \beta$ с такими свойствами ($0 \le a_i \le b_i$ при $i \ge 1$). В самом деле, $\beta = \alpha + \rho$ для перечислимого снизу $\rho$; представим $\alpha = \Sigma a_i$ и $\rho = \Sigma r_i$ и возьмём $b_i = a_i + r_i$.

**162** Покажите, что верно и более сильное утверждение и что не только ряд $a_i$ (как видно из приведённого рассуждения), но и ряд $b_i$ можно выбирать произвольно. А именно, если $\alpha \le 1 \beta = \Sigma b_i$, где $b_i \ge 0$, то найдётся представление $\alpha = \Sigma a_i$, где $0 \le a_i \le b_i$ при всех $i > 0$. (Все ряды вычислимы.) [Указание. Будем строить последовательность $a_i$ индуктивно, сохраняя такой инвариант: текущее приближение (снизу) к $\alpha$ имеет не большую погрешность, чем текущее приближение к $\beta$. Получив следующее приближение к $\beta$, мы применяем соотношение $\alpha \le 1 \beta$, чтобы найти не худшее приближение к $\alpha$. Если возникающее при этом $a_i$ окажется не больше $b_i$, то и хорошо; если больше, то его можно уменьшить до $b_i$ без нарушения инварианта.]

Из сказанного следует, что для любого перечислимого снизу $\alpha$ мы имеем

$$ \alpha \le 1 \ 2\alpha \le 1 \ 3\alpha \le 1 \dots, $$

поскольку все разности (равные $\alpha$) перечислимы снизу. Отсюда же видно, что обратные неравенства неверны, если $\alpha$ не вычислимо (если оба числа $\alpha$ и $-\alpha$ перечислимы снизу, то $\alpha$ вычислимо). Можно сказать, что наше отношение $\le 1$ «слишком чувствительно»: оно различает $\alpha$ и $2\alpha$, хотя их двоичные разложения отличаются всего лишь сдвином. Как его огрубить? Наиболее естественный способ, видимо, допустить умножение на константу.

Будем говорить, что перечислимое снизу число $\alpha$ сводится по Соловею к перечислимому снизу числу $\beta$, и писать $\alpha \le \beta$, если $\alpha \le 1 \ c\beta$ для некоторого целого $c > 0$. (Можно ввести обозначение: $\alpha \le c \beta$, если $\alpha \le 1 \ c\beta$. Тогда $\alpha \le \beta$, если $\alpha \le c \beta$ для некоторого $c$.) Это отношение, очевидно, тоже рефлексивно и транзивно.

**Теорема 102.** Среди перечислимых снизу чисел существует наибольшее в смысле сводимости по Соловею.

Действуем как с перечислимыми полумерами: складываем с некоторыми коэффициентами $w_i$ (годятся $w_i = 2^{-i}$) все перечислимые снизу числа $\alpha_i$ в интервале $[0, 1]$. Тогда сумму $\alpha = \Sigma w_i \alpha_i$ можно представить как $w_i \alpha_i$ плос перечислимое снизу число (сумма остальных членов ряда), откуда и следует требуемое. ►

Наибольшие в смысле этого порядка числа называются полными по Соловею.

Можно даже определить некоторую количественную характеристику для полных по Соловею чисел, которую можно было бы назвать «дефектом полноты»: для числа $\beta$ дефект полноты определяется как наименьшее $c$, при котором $\alpha \le 1 \ c\beta$. Здесь $\alpha$ — некоторое фиксированное полное по Соловею число; функция дефекта
зависит от выбора $\alpha$, но определена с точностью до ограниченного множителя. Дефект $\beta$ конечен тогда и только тогда, когда $\beta$ является полным.

Оказывается, что полные по Соловею числа и только они могут появляться как «число Ω» в описанной выше конструкции [161, 17].

**Теорема 103.** Сумма любой максимальной перечислимой снизу полумеры на множестве натуральных чисел является полным по Соловею перечислимым снизу числом. Наоборот, любое полное по Соловею положительное перечислимое снизу число в (0, 1) является суммой некоторой максимальной перечислимой снизу полумеры.

◀ Докажем, что произвольное перечислимое снизу число $\alpha$ сводится к сумме произвольной максимальной полумеры. Число $\alpha$ есть сумма вычислимого ряда $\sum a_i$ с неотрицательными (кроме первого) рациональными членами. (Говоря о вычислительности ряда, мы подразумеваем вычислимость функции $i \mapsto a_i$, а не суммы этого ряда.) С точностью до константы (которая не играет роли в определении полноты) этот ряд мажорируется нашей перечислимой снизу полумерой. Разница между полумерой и рядом перечислима снизу, и потому $\alpha$ сводится по Соловею к сумме полумеры.

С другой стороны, пусть число $\alpha \in (0, 1)$ полно по Соловею. Как представить его в виде суммы максимальной перечислимой снизу полумеры? Возьмём какую-нибудь максимальную полумеру $t_0, m_1, \dots$. В силу полноты $\sum m_i \le 1$ $c\alpha$ при некотором $c$, и потому $\alpha = \sum m_i/c + \tau$ для перечислимого снизу $\tau$. Поделив все $m_i$ на $c$ и добавив $\tau$ (скажем) к $t_0$, получим максимальную полумеру с суммой в точности $\alpha$. ►

Числа типа Ω имеют и ещё одно описание (помимо полноты по Соловею): это в точности перечислимые снизу случайные числа в интервале (0, 1). Доказательство содержит несколько шагов, и сейчас мы к нему перейдём.

### 5.7.2. Полные по Соловею числа случайны

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

Мы приведём сейчас (следуя подстрочному примечанию в статье Левина [84]) другое доказательство того же факта, которое не использует теорему Левина – Шнорра и вообще не апеллирует к понятию сложности.

Для начала напомним, что существование перечислимого снизу случайного числа может быть доказано без упоминания Ω (см. задачу 86). Поэтому достаточно доказать, что свойство случайности «наследственно вверх»: если $\alpha$ случайно и $\alpha \le \beta$, то и $\beta$ случайно.

Без ограничения общности можно считать, что $\alpha \le \beta$ (умножение на рациональную константу не меняет случайности). Мы должны доказать, что из неслучайности $\beta$ следует неслучайность $\alpha$. Для этого мы преобразуем покрытие $\beta$
перечислимым семейством интервалов в покрытие $\alpha$ другим семейством той же или меньшей меры. Пусть $b_i$ — возрастающая вычислимая последовательность рациональных чисел с пределом $\beta$. Будем следить параллельно за ростом $b_i$ и за появлением новых интервалов в покрытии для $\beta$. Если в покрытии появляется интервал, который целиком левее текущего $b_i$, то он к делу не относится ($\beta$ в нём заведомо не лежит). Если в покрытии появляется интервал, который целиком правее текущего $b_i$, то можно отложить его рассмотрение до момента, когда $b_i$ в него зайдёт (если этого никогда не случится, то интервал не покрывает $\beta$). Нако- нец, если интервал покрытия содержит $b_i$, мы вместо него рассматриваем интервал той же длины, который начинается с приближения $a_i$ к $\alpha$, которое имеет не боль- шую погрешность, чем $b_i$ (как приближение к $\beta$). Легко видеть, что если один из интервалов покрытия содержит $\beta$, то он рано или поздно будет преобразован в интервал той же длины, покрывающий $\alpha$. Поэтому из неслучайности $\beta$ следует неслучайность $\alpha$, что и требовалось доказать.

Итак, случайность наследуется вверх и потому полные по Соловею числа слу- чайны.

**Замечание.** Вторую часть рассуждения можно переформулировать так: пусть $\alpha$ и $\beta$ перечислимы снизу; если одно из них случайно, то сумма $\alpha + \beta$ случайна. Оказывается, что верно и обратное: если перечислимые снизу $\alpha$ и $\beta$ оба не слу- чайны, то и сумма $\alpha + \beta$ не случайна. (Мы дадим ниже несколько доказательств этого факта.)

### 5.7.3. Критерий случайности в терминах предсказаний

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

Наблюдатель глядит на возрастающую последовательность рациональных чисел (которые сообщаются ему по очереди). Время от времени он делает предсказания такого типа: «последовательность в будущем возрастёт по сравнению с текущим значением не более чем на $\delta$». Здесь $\delta$ — неотрицальное рациональное число (вы- бираемое наблюдателем). Будем считать, что наблюдатель выигрывает, если

(1) одно из его предсказаний остаётся верным навсегда;

(2) общая сумма всех использованных им чисел $\delta$ мала (меньше рационального $\varepsilon > 0$, которое сообщается наблюдателю до начала игры).

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

В терминах этой игры можно дать критерий случайности:

**Теорема 104.** Пусть $a_i$ — вычислимая возрастающая последовательность рациональных чисел, сходящаяся к (перечислимому снизу) числу $\alpha$. Наблюдатель
имеет вычислимую стратегию, обеспечивающую ему выигрыш в описанной игре, если и только если $\alpha$ не случайно.

◀ Вычислимая стратегия в такой игре сразу же даёт последовательность отрезков, имеющих сумму длин не больше $\varepsilon$ и покрывающих $\alpha$; отрезки легко преобразовать в интервалы чуть большей длины.

С другой стороны, если $\alpha$ не случайно, то существует последовательность интервалов с малой суммой мер, его покрывающей. Эти интервалы можно использовать для предсказания. А именно, когда мы обнаруживаем, что текущее приближение покрыто одним из интервалов, мы предсказываем, что оно никогда не выйдет из этого интервала. Когда и если оно выйдет, снова ожидаем попадания в один из интервалов и т. д. При этом мы будем брать самый первый (раньше других появившийся) из интервалов, покрывающих текущее приближение. Это гарантирует, что рано или поздно мы выберем интервал, покрывающий $\alpha$, и соответствующее ему предсказание останется верным навсегда. ▶

Утверждение теоремы может быть переформулировано без использования игровой терминологии.

**Теорема 105.** Пусть $a_i$ — вычислимая возрастающая последовательность рациональных чисел, сходящаяся к $\alpha$. Число $\alpha$ не случайно тогда и только тогда, когда для каждого рационального $\varepsilon > 0$ можно эффективно указать вычислимую последовательность неотрицательных рациональных чисел $h_0, h_1, \dots$, для которой $\sum_i h_i < \varepsilon$ и $\alpha \le a_i + h_i$ для некоторого $i$.

◀ Это соответствует игре, в которой предсказания делаются на каждом шаге. Как мы говорили, это не важно, так как можно использовать нулевые $h_i$.) ▶

Мы рассматривали также критерий случайности по Мартин-Лёфу, предложенный Соловеем (теорема 31, с. 76); в нём шла речь не о покрытии для каждого $\varepsilon$, а об одном покрытии конечной меры, покрывающем $\alpha$ бесконечно много раз. Аналогичную модификацию допускает и предыдущая теорема:

**Теорема 106.** Пусть $a_i$ — вычислимая возрастающая последовательность рациональных чисел, сходящаяся к $\alpha$. Число $\alpha$ не случайно тогда и только тогда, когда существует вычислимая последовательность неотрицательных рациональных чисел $h_i$ с конечной суммой $\sum_i h_i$, для которой $\alpha \le a_i + h_i$ для бесконечно многих $i$.

◀ Если $\alpha$ не случайно, то мы можем применить предыдущую теорему к $\varepsilon = 1, 1/2, 1/4, 1/8, \dots$, и затем сложить все полученные последовательности, предварительно сдвинув $i$-ю последовательность вправо на $i$ (от этого её свойства не нарушатся). Каждая из последовательностей даст по крайней мере одно $i$, для которого $\alpha \le a_i + h_i$, и благодаря сдвигу таких $i$ будет бесконечно много.

С другой стороны, если $\alpha \le a_i + h_i$ для бесконечно многих $i$, то мы получаем последовательность интервалов с конечной суммой длин, которая покрывает $\alpha$ бесконечно много раз (точнее говоря, отрезков, но их можно увеличить до интервалов). Остаётся воспользоваться критерием Соловея — или вспомнить его доказательство: множество точек, покрытых этими интервалами в $\mathfrak{M}$ или более слоёв, эффективно открыто и имеет меру $O(1/m)$. ▶
Из доказанных только что критериев случайности сразу же вытекает такое следствие (на первый взгляд удивительное). Рассмотрим вычислимую последовательность положительных рациональных чисел $a_i$, для которой $\sum a_i$ сходится. Служайность суммы не изменится, если каждый член умножить на ограниченный отделённый от нуля множитель. (В самом деле, все $h_i$ можно умножить на константу.)

Докажем теперь обещанное утверждение:

**Теорема 107.** Если $\alpha$ и $\beta$ перечислимы снизу и не случайны, то и их сумма $\alpha + \beta$ не случайна.

◀ Естественная идея: попытаться воспользоваться критерием с предсказаниями: если в игре с $\alpha$ мы предсказываем рост $h$, а в игре с $\beta$ мы предсказываем рост $k$, то в игре с $\alpha + \beta$ можно предсказать рост $h + k$. Но тут возникает трудность: если возобновлять такие предсказания после их нарушения, то одно и то же значение $h$ может комбинироваться с разными $k$ и войдёт в сумму многократно.

Выход состоит в том, чтобы использовать предсказания одного и того же размера для $\alpha$ и $\beta$. Чтобы сделать предсказание для $a_i + b_i$ (после того, как предыдущее окажется негодным), мы ожидаем, пока текущие приближения $a_i$ и $b_i$ попадут внутрь соответствующих покрытий (по предположению $\alpha$ и $\beta$ не случайны и покрыты перечислимыми семействами интервалов малых мер). Возьмём максимальные $h$ и $k$, при которых $(a_i, a_i + h)$ и $(b_i, b_i + k)$ целиком содержатся в (обнаружившейся части) соответствующих покрытий. Наше предсказание будет интервалом $(a_i + b_i, a_i + b_i + 2\delta)$, где $\delta = \min(h, k)$ (другими словами, мы утверждаем, что $a_i + b_i$ в будущем возрастёт не более чем на $2\delta$).

Остаётся проверить две вещи. Во-первых, убедимся, что одно из предсказаний останется верным навсегда. В самом деле, $\alpha$ и $\beta$ покрыты какими-то интервалами, вместе со своими $\sigma$-окрестностями для какого-то $\sigma > 0$. Текущие приближения $a_i$ и $b_i$ рано или поздно попадут в эти интервалы, если после этого нам придётся делать предсказание, то $h$ и $k$ будут выбраны не меньше $\sigma$, интервал предсказания покроет $\alpha + \beta$, и это предсказание уже не нарушится никогда.

Во-вторых, мы должны убедиться, что общая сумма длин предсказаний мала. В самом деле, когда интервал предсказания $(a_i + b_i, a_i + b_i + 2\delta)$ становится непригодным, это гарантирует, что либо $a_i$, либо $b_i$ с тех пор увеличилось как минимум на $\delta$. Значит, общая мера покрытия справа от текущих приближений уменьшилась по крайней мере на $\delta$, что гарантирует оценку на сумму всех предсказаний (удвоенная сумма мер покрытий). В этом рассуждении мы используем то, что оба интервала $(a_i, a_i + \delta)$ и $(b_i, b_i + \delta)$ целиком входят в покрытие, поэтому важно, что мы брали минимум из $h$ и $k$. ►

Вернёмся к критерию случайности из теоремы 105. Предлагаемое там условие может быть ослаблено в двух отношениях. Во-первых, вместо вычислимой последовательности $h_i$ можно рассматривать перечислимую снизу последовательность. Во-вторых, можно заменить $h_i$ на весь остаток (хвост ряда) $h_i + h_{i+1} + ...$:

**Теорема 108.** Пусть дана вычислимая возрастающая последовательность рациональных чисел $a_i$ с пределом $\alpha$. Предположим, что для каждого рационального $\varepsilon > 0$ можно эффективно указать перечислимую снизу последова-
тельность неотрицательных действительных чисел $h_i$, для которой $\sum h_i < \varepsilon$ и $\alpha \le a_i + h_i + h_{i+1} + ...$ для некоторого $i$. Тогда число $\alpha$ не случайно.

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

Покрашенная зона представляет собой объединение перечислимого семейства отрезков общей длины не более $\sum h_i$ (общее количество краски). Если $\alpha < a_i + h_i + ... + h_{i+1} + ...$, то точка $\alpha$ будет покрашена, так как вся краска в правой части неравенства накладывается в один слой справа от $a_i$ и не поместится левее $\alpha$. (В условии теоремы было нестрогое неравенство, но это не важно, поскольку все $h_i$ можно, скажем, удвоить. По тем же причинам не важно, что мы покрыли $\alpha$ отрезками, а не интервалами.) ►

Отсюда можно вывести ещё одну формулировку критерия случайности:

**Теорема 109.** Пусть $\alpha = \sum r_i$ — сумма вычислимого ряда из неотрицательных рациональных чисел (и тем самым перечислимо снизу). Число $\alpha$ не случайно тогда и только тогда, когда для каждого $\varepsilon > 0$ можно эффективно указать перечислимое множество $W \subset \mathbb{N}$, для которого $(1) \sum_{i \in W} r_i < \varepsilon$ и (2) $W$ имеет конечное дополнение (содержит все натуральные числа, начиная с некоторого).

◀ Если $\alpha$ не случайно, то его можно покрыть интервалами малой меры и включить в $W$ те $i$, для которых отрезок $[r_0 + ... + r_{i-1}, r_0 + ... + r_i]$ покрывается целиком. В обратную сторону утверждение прямо следует из теоремы 108, надо положить $a_i = r_0 + ... + r_{i-1}$ и $h_i = r_i$ при $i \in W$ (и $h_i = 0$ при $i \notin W$). ►

Из этого критерия сразу видно, что сумма двух неслучайных перечислимых снизу чисел неслучайна (надо взять пересечение множеств $W_1$ и $W_2$ для каждого из них), так что мы получаем новое доказательство теоремы 107.

Использованный при доказательстве теоремы 108 приём оказывается полезным и в других ситуациях, например, в следующей задаче (это рассуждение сообщил авторам Л. Бьенвеню, оригинальное рассуждение в [70] существенно сложнее).

**163** Пусть $U$ — эффективно открытое подмножество отрезка, имеющее меру меньше 1 и содержащее все неслучайные последовательности (скажем, одно из множеств универсального теста Мартин-Лёфа). Докажите, что мера $U$ является перечислимым снизу случайным числом.

[Указание. Пусть мера множества $U$ равна $\alpha$. Имея покрытие числа $\alpha$ интервалами малой меры, мы можем построить покрытие наименьшего числа вне $U$ интервалами той же меры. Как только текущее приближение к $\alpha$ попадает в некоторый интервал, мы предполагаем, что оно не выйдет из этого интервала и красив имеющееся на данный момент дополнение к $U$ слева направо. Если наше положение окажется истинным (а когда-то оно окажется), то мы действительно покрасим наименьшее число вне $U$ (покрашенная часть есть объединение отрезков, а не интервалов, но это не важно).]
5.7.4. Случайные перечислимые снизу числа полны

Теперь уже несложно доказать обратную импликацию [70]: любое перечислимое снизу случайное число является полным по Соловею. Рассмотрим два перечислимых снизу числа $\alpha$ и $\beta$ и сходящиеся к ним возрастающие вычислимые последовательности $a_i \to \alpha$ и $b_i \to \beta$. Рассмотрим приращения $h_i = a_{i+1} - a_i$ первой последовательности. Попробуем применить их в качестве предсказаний для второй. Другими словами, мы сдвигаем интервал $(a_0, a_1)$ так, чтобы его левый конец пришёлся на $b_1$. Затем мы ждём, пока $b_i$ выйдет из полученного интервала. Пусть $b_{i_1}$ — первый такой член. Сдвинем $(a_1, a_2)$ так, чтобы его левый конец пришёлся на $b_{i_1}$, и подождём появления $b_{i_2}$ справа от этого интервала. И так далее.

<figure><img src="image_16.png" /><figcaption>Рис. 5.2. Приращения для $a_i$ используются как предсказания для $\beta$.</figcaption></figure>

Есть две возможности:

(1) предсказатель выигрывает, то есть какой-то из сдвинутых интервалов содержит все оставшиеся $b_i$, очередное $i_k$ не определено;

(2) процесс продолжается бесконечно.

Во втором случае $\alpha \le 1$, поскольку разность $\beta - \alpha$ оказалось представленной в виде суммы вычислимого ряда (промежутки между сдвинутыми интервалами). Отсюда мы заключаем, что при полном $\alpha$ и неполном $\beta$ этот случай невозможен.

Следовательно, при полном $\alpha$ и неполном $\beta$ имеет место первый случай, и мы получаем последовательность отрезков с конечной суммой длин, покрывающих $\beta$. Повторив это рассуждение для $\alpha/2$ (которое тоже полное), мы получим другую такую последовательность, для $\alpha/4$ третью и так далее. Суммы длин для этих последовательностей не превосходят $\alpha$, $\alpha/2$, $\alpha/4$, ..., поэтому можно эффективно указать покрытие числа $\beta$ со сколь угодно малой суммой. (Само $\alpha$ не вычислимо, но это нам и не нужно, достаточно верхней оценки.)

Эти рассуждения можно провести для любого неполного $\beta$, взяв в качестве $\alpha$ произвольное полное перечислимое снизу число. Тем самым мы доказали, что неполное число $\beta$ не является случайным, что завершает доказательство обещанного результата:

**Теорема 110.** Перечислимое снизу действительное число случайно тогда и только тогда, когда оно полно по Соловею.

5.7.5. Медленная сходимость и функции Соловея

Мы уже встречались с несколькими результатами такого типа: предел возрастающей вычислимой последовательности рациональных чисел случаен тогда и только
тогда, когда она сходится медленно. Сейчас мы рассмотрим ещё несколько результатов в этом направлении [7, 53].

Пусть дан вычислимый ряд $\Sigma r_i$ с неотрицательными членами и конечной суммой. Тогда $r_i$ не превышает $O(m(i))$, где $m(i)$ — априорная вероятность натурального числа $i$ (в смысле главы 4), а префиксная сложность $KP(i)$, равная $-\log m(i)$, не превышает $-\log r_i$ (с точностью до аддитивной константы). Будем говорить, что ряд медленно сходится в смысле Соловея, если эта верхняя оценка для $r_i$ является $O(1)$-точной при бесконечно многих $i$, то есть если $r_i \ge \varepsilon m(i)$ при некотором $\varepsilon > 0$ и бесконечно многих $i$. Переформулировка: ряд быстро сходится (не является медленно сходящимся в смысле Соловея), если $r_i/m(i) \to 0$.

Исторически функцией Соловея (Solovay function) называют вычислимую верхнюю оценку $S(i)$ для префиксной сложности $KP(i)$, если эта оценка точна в бесконечном числе мест, то есть если $KP(i) \le S(i) + c$ для некоторого $c$ и всех $i$, а также $KP(i) \ge S(i) - c$ для некоторого $c$ и бесконечно многих $i$. Таким образом, ряд $\Sigma r_i$ медленно сходится в смысле Соловея тогда и только тогда, когда $-\log r_i$ является функцией Соловея. (Обычно, говоря о функциях Соловея, имеют в виду функции с целыми значениями, так что в данном случае надо ещё произвести округление.) Мы приведём несколько результатов, связывающих случайность с медленной сходимостью, по большей части следуя [7, 53].

**Теорема 111.** Сумма вычислимого сходящегося ряда с неотрицательными рациональными членами случайна тогда и только тогда, когда этот ряд медленно сходится в смысле Соловея.

Другими словами, сумма ряда $\alpha = \Sigma r_i$ не случайна тогда и только тогда, когда $r_i/m(i) \to 0$.

Пусть $r_i/m(i) \to 0$. Тогда для произвольного $\varepsilon > 0$ мы можем положить $h_i = \varepsilon m(i)$ и получить перечислимую снизу последовательность, которую можно использовать в теореме 108. Следовательно, $\alpha$ не случайно.

Приведём альтернативное рассуждение, показывающее, что $\alpha$ не является полным по Соловею. Вспомним доказательство теоремы 103: если $r_i \le m(i)$, то $\Sigma r_i \le 1 \le \Sigma cm(i)$. А если $r_i \le cm(i)$, то $\Sigma r_i \le c \Sigma m(i)$. Это остаётся верным, если неравенство $r_i \le cm(i)$ верно не для всех $i$, а только начиная с некоторого. Следовательно, если $r_i/m(i) \to 0$, то для $\alpha = \Sigma r_i$ выполнено свойство $\alpha \le c \Sigma m(i)$ при любом $c > 0$. Может ли тогда $\alpha$ быть полным? Нет, и вот почему. Если оно полно, то $\Sigma m(i) \le d \alpha$ при некотором $d$. Но тогда $\alpha \le c d \alpha$ при всех $c > 0$, в том числе и сколь угодно малых. Выходит, что $\alpha \le 1/2 \alpha$, а отсюда следует вычислимость $\alpha$: по любому приближению снизу к нему можно указать двое более точное!

Осталось доказать обратное утверждение: предположив, что число $\alpha = \Sigma r_i$ не случайно, установить, что $r_i/m(i) \to 0$. Представим себе отрезок $[0, \alpha]$, разбитый на участки длиной $r_0, r_1, \dots$ (слева направо). Имея покрытие числа $\alpha$ интервалами с малой суммой мер, мы рассмотрим те из участков, которые покрыты целиком (вместе с концами). Это перечислимое множество, а их суммарная мера не превосходит меры покрытия. Если мера покрытия не больше $2^{-2^n}$, то мы можем умножить соответствующие $r_i$ на $2^n$ и их сумма не превзойдёт $2^{-n}$. Заметим также, что все участки, начиная с некоторого, покрыты. Таким способом мы получаем полумеру
$M^n$, для которой $M^n(i)/r_i \ge 2^n$ для всех достаточно больших $i$, а сумма $\sum_i M^n(i)$ не превосходит $2^{-n}$. Сложив теперь все $M^n$, мы получим перечислимую снизу полумеру $M$, для которой $r_i/M(i) \to 0$. Следовательно, это верно и для максимальной полумеры. ►

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

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

**164** Пусть $U$ — оптимальный беспрефиксный способ описания. Рассмотрим функцию $f(p, x, n)$, которая равна $l(p)$, если $U$ на входе $p$ останавливается за $n$ шагов и даёт $x$, и равна (скажем) $2l(p) + 2l(x) + 2\log n$ в противном случае. Покажите, что $f(p, x, n)$ является верхней оценкой для $KP(p, x, n)$, которая точна, когда $p$ является кратчайшим описанием $x$ и его обработка требует $n$ шагов. Выведите отсюда существование функций Соловея.

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

### 5.7.6. Свойство Соловея для ряда определяется его суммой

Отметим для начала такой простой факт: медленная сходимость ряда сохраняется при вычислимой перестановке его членов. Это сразу следует из того, что вычислимая перестановка $\pi$ меняет априорную вероятность не более чем в константу раз: $m(\pi(i)) = \Theta(m(i))$. Более интересен вопрос о группировке членов. Поскольку мы хотим разрешить бесконечные группы, рассмотрим двумерный вычислимый ряд $\sum_{i,j} a_{ij}$ с неотрицательными рациональными членами. Его можно разбить на группы:

$$ \alpha = \sum_{i,j} a_{ij} = (a_{00} + a_{01} + \dots) + (a_{10} + a_{11} + \dots) + \dots = \sum_{i} A_{i}, $$

где $A_i = \sum_j a_{ij}$.

Мы хотим показать, что ряды $\sum A_i$ и $\sum a_{ij}$ одновременно обладают (или не обладают) свойством Соловея. (Мы уже видели, что это свойство сохраняется при перестановке, поэтому корректно определено для второго ряда.)
Тут, правда, нужны некоторые дополнительные пояснения и условия. Во-первых, $\sum A_i$ не является вычислимым рядом, а только перечислим снизу. Это, однако, не мешает распространить на него определение медленной сходимости: перечислимые ряды тоже оцениваются сверху пририорной вероятностью, и мы требуем, чтобы эта оценка была $O(1)$-точна на бесконечном множестве. Дав такое определение, мы видим, что интересующее нас утверждение неверно без дополнительных предположений: пусть, например, все ненулевые члены входят в группу $A_1$; тогда ряд $\sum A_i$ сходится с максимально возможной скоростью, а ряд $\sum a_{ij}$ может сходиться медленно. Следующая теорема указывает такие дополнительные предположения:

**Теорема 112.** Пусть каждая группа $A_i$ ряда содержит лишь конечное число ненулевых членов. Тогда свойства $A_i/m(i) \to 0$ и $a_{ij}/m(i,j) \to 0$ равносильны.

Здесь $m(i,j) = 2^{-KP(i,j)+O(1)}$ — априорная вероятность пары $\langle i,j \rangle$ (или её кода при каком-то вычислимом кодировании).

◀ Вспомним прежде всего, что $m(i) = \sum_j m(i,j)$ с точностью до ограниченного множителя. (В самом деле, правая часть есть перечислимый снизу сходящийся ряд. С другой стороны, уже первый член $m(i,0)$ равен $m(i)$ с интересующей нас точностью.) Поэтому $a_{ij}/m(i,j) \to 0$ влечёт $A_i/m(i) \to 0$: лишь для конечного число пар $\langle i,j \rangle$ выполнено неравенство $a_{i,j} > \varepsilon m(i,j)$, и эти пары входят лишь в конечное число групп.

Сложнее обратное утверждение: $A_i/m(i) \to 0$ влечёт $a_{ij}/m(i,j) \to 0$. (Именно здесь нам важно, что в каждой группе лишь конечное число ненулевых членов.) Нам нужно построить перечислимую снизу функцию $\tilde{m}(i,j)$ с конечной суммой, для которой $a_{ij}/\tilde{m}(i,j) \to 0$, используя тот факт, что $A_i/m(i) \to 0$. Естественная идея: разбить $m(i)$ в сумму $\sum \tilde{m}(i,j)$ в той же пропорции, в которой $A_i$ разбивается в $\sum a_{ij}$. Для этого, однако, мы должны уметь вычислять $A_i$, а не только перечислять снизу. Это было бы легко, если бы мы знали, сколько ненулевых членов есть среди $a_{ij}$ при данном $i$, но эта информация не вычислима, так что нам придётся действовать иначе. (Для группировки ряда в группы с конечным числом членов этот способ проходит.)

Будем действовать «с другого конца». Мы можем положить $\tilde{m}(i,j)$ равным $ca_{ij}$ для некоторой константы $c$, пока это не нарушает свойства $\sum_j \tilde{m}(i,j) \le m(i)$. Глядя на рост $m(i)$ в правой части, мы позволяем левой части подрасти соответствующим образом, в благоприятных условиях до $ca_{ij}$. Если (согласно нашему предположению) $A_i/m(i) \to 0$, то для любой константы $c$ при всех достаточно больших $i$ выполнено неравенство $ca_i \le m(i)$ и граница $m(i)$ не мешает росту. Следовательно, $a_{ij}/\tilde{m}(i,j) \le 1/c$ при всех достаточно больших $i$, и потому это верно для всех пар $\langle i,j \rangle$, кроме конечного числа (при каждом $i$ лишь конечное число ненулевых членов). Таким образом, для каждого $c$ мы построили свою полумеру $\tilde{m}_c(i,j)$, для которой $a_{ij}/\tilde{m}_c(i,j) \le 1/c$ почти всюду (а сумма не больше $\sum m(i) \le 1$). Остаётся выполнить это построение при всех $c = 2^{2n}$ и сложить $m_{2^{2n}}$ с коэффициентами $2^{-n}$. ▶

Как следствие этой теоремы мы получаем другое доказательство того, что свойство Соловьева для вычислимого ряда зависит только от суммы ряда. В самом деле, если для двух вычислимых рядов $\sum_i a_i = \sum_j b_j$, то эти ряды могут быть получе-
<figure><img src="image_17.png" /><figcaption>Рис. 5.3. Два ряда с одинаковой суммой могут быть представлены как результаты различных группировок третьего.</figcaption></figure>

ны различной группировкой слагаемых (отметим все точки деления и группируем интервалы между ними по-разному, рис. 5.3).

Помимо альтернативного доказательства инвариантности, мы получаем некоторое усиление теоремы 111: в ней рациональные числа $r_i$ (члены ряда) были вычислимы, а теперь их можно задавать перечислением снизу, при условии, что каждое из них меняется (возрастает) лишь конечное число раз. Точнее говоря, мы требуем, чтобы $r_i = \lim_n r(i, n)$, где $r$ — вычислимая функция двух натуральных аргументов с рациональными значениями, неубывающая по $n$ и принимающая при каждом $i$ (и всевозможных $n$) лишь конечное число значений. Тогда неслучайность числа $\Sigma r_i$ равносильна условию $r_i/m(i) \to 0$. В самом деле, каждое $r_i$ можно представить как сумму вычислимого ряда из приращений, в котором лишь конечное число членов绝�но от нуля. После этого замена ряда на двумерный не меняет ни свойства Соловея (как мы видели в предыдущей теореме), ни суммы (очевидным образом).

Вспомним, что перечислимая сверху функция $f(n)$ с натуральными аргументами является верхней оценкой для $KP(n)$ с точностью до $O(1)$, если и только если $\Sigma_n 2^{-f(n)} < \infty$ (теорема 62). Теперь мы можем дополнить это утверждение:

**Теорема 113.** Эта оценка точна для бесконечно многих $n$ ($KP(n) \ge f(n)$ — с для некоторого $c$ и бесконечно многих $n$), если и только если сумма $\Sigma_n 2^{-f(n)}$ случайна.

◀ В самом деле, убывающие целочисленные верхние оценки для $f(n)$ дают как раз возрастающие (и меняющиеся конечное число раз) нижние оценки для $2^{-f(n)}$, так что можно сослаться на только что доказанное утверждение. ▶

### 5.7.7. Регуляторы сходимости и функция $ВВ(n)$

Мы уже видели несколько разных уточнений интуитивной идеи «медленно сходящегося ряда». Но, пожалуй, самый естественный подход мы ещё не пробовали. Он состоит в следующем. Если $a_n \to \alpha$, то для всякого $\varepsilon > 0$ найдётся $N$, для которого $|a_n - \alpha| < \varepsilon$ при всех $n > N$. Минимальное такое $N$ (рассматриваемое как функция от $\varepsilon$) называют регулятором сходимости $a_n$ к $\alpha$, и сходимость естественно считать медленной, если регулятор быстро растёт (с убыванием $\varepsilon$). Сейчас мы покажем, как в этих терминах можно характеризовать свойство Соловея.

Вспомним, что в разделе 1.2 (с. 30) мы определили $В(n)$ как наибольшее число, сложность которого не превосходит $n$. Там речь шла о простой сложности (мы ещё не рассматривали других), но аналогичное определение можно дать и для префиксной сложности: обозначим через $ВР(n)$ наибольшее число, префиксная сложность которого не превосходит $n$.
**165** Фиксируем оптимальный беспрефиксный декомпрессор, задающий префиксную сложность. Покажите, что максимальное время его работы на описаниях длины не более *n* заключено между *BP(n - с)* и *BP(n + с)* при некотором *c* и всех *n*. [Указание: годится то же рассуждение, что и для простой сложности (см. раздел 1.2).]

Докажем теперь эквивалентность различных вариантов понятия «медленно сходящегося ряда».

**Теорема 114.** Вычислимый ряд с неотрицательными рациональными членами $\sum r_i$ обладает свойством Соловея (⇔ имеет случайную сумму) тогда и только тогда, когда его регулятор сходимости быстро растёт: $N(2^{-m}) > BP(m-c)$ для некоторого $c$ и для всех $m$.

Пусть $\alpha = \sum r_i = \lim a_i$, где $a_i = r_0 + \dots + r_{i-1}$. Предположим, что число $\alpha$ случайно. Мы должны показать, что из $|\alpha - a_i| < 2^{-m}$ следует $KP(i) > m - O(1)$, и тем самым установить, что $N(2^{-m}) \ge KP(m-O(1))$. Поскольку $KP(i) \ge KP(a_i) + O(1)$, достаточно доказать, что любое рациональное $2^{-m}$-приближение к $\alpha$ имеет префиксную сложность не меньше $m - O(1)$. Это немного более сильное утверждение, чем в теореме Левина-Шнорра, где речь не о произвольном приближении, а о первых $m$ битах. Тем не менее оно может быть доказано примерно тем же способом. Вот как это делается.

Пусть $c$ — произвольное натуральное число. Рассмотрим эффективно открытое множество $U_c$, которое строится так. Для каждого рационального $r$ возьмём окрестность с центром в $r$ и радиусом $2^{-KP(r)-c}$; множество $U_c$ представляет собой объединение всех таких окрестностей. Поскольку функция $KP$ перечислима сверху, это объединение эффективно открыто. Общая длина всех окрестностей равна $2 \cdot 2^{-c} \sum_r 2^{-KP(r)} \le 2^{-(c-1)}$. Если бы $\alpha$ принадлежало бы всем $U_c$, то оно не было бы случайным. Значит, найдётся $U_c$, которому оно не принадлежит — а это как раз означает, что префиксная сложность всех $2^{-m}$-приближений к $\alpha$ не меньше $m - O(1)$.

В другую сторону мы можем использовать теорему Левина-Шнорра без каких-либо изменений: если $N(2^{-m}) > BP(m-c)$, то $KP(i) \ge m-c$ для любого $i$, при котором $a_i$ приближает $\alpha$ с ошибкой не более $2^{-m}$. Следовательно, $m$-битовое начало двоичного разложения $\alpha$ имеет сложность не менее $m - O(1)$: зная его, мы можем дождаться появления $a_i$, которое отличается от $\alpha$ не более чем на $2^{-m}$. ►

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

Переводя определение $BP(m)$ на язык априорной вероятности, мы можем определить $BP(m)$ как минимальное $N$, для которого все $n > N$ имеют априорную вероятность менее $2^{-m}$. Но раз уж мы перешли к априорной вероятности, то логичнее рассмотреть другое понятие: обозначим через $BP'(m)$ минимальное $N$, для
которого сумма априорных вероятностей всех $n > N$ меньше $2^{-m}$. Вообще говоря, $ВР'(m)$ может быть больше $ВР(m)$, но оказывается, что $ВР'(m)$ тоже может быть использовано для характеризации случайности:

**Теорема 115.** Пусть $a_i$ — вычислимая возрастающая последовательность рациональных чисел, которая сходится к случайному числу $\alpha$. Тогда $N(2^{-m}) \ge 2^{-m}BP'(m-c)$ для некоторого $c$ и для всех $m$.

◀ Числа $i > N(2^{-m})$ имеют (с точностью до константы) ту же априорную вероятность, что и соответствующие $a_i$. Поэтому достаточно доказать, что сумма априорных вероятностей всех рациональных чисел в $2^{-m}$-окрестности числа $\alpha$ есть $O(2^{-m})$. (В самом деле, при $i > N(2^{-m})$ число $a_i$ попадает в эту окрестность.)

Как обычно, мы будем рассуждать с другого конца и покроем все $\alpha$, для которых это свойство неверно, семейством интервалов малой меры. Зафиксируем некоторое $c$ и рассмотрим все интервалы с рациональными концами, обладающие следующим свойством: сумма априорных вероятностей всех рациональных чисел внутри интервала по крайней мере в $c/2$ раз превышает его длину. Мы докажем, что мера объединения всех таких интервалов есть $O(1/c)$ (на самом деле не превосходит $4/c$).

Достаточно доказать это для конечного набора интервалов с этим свойством. Более того, можно считать, что в этом наборе нет ни одного лишнего интервала (от выбрасывания которого объединение не уменьшится). Упорядочим интервалы набора в порядке возрастания левых концов:

$$ (l_0, r_0), (l_1, r_1), (l_2, r_2), \dots, $$

где $l_0 \le l_1 \le l_2 \le \dots$; легко видеть, что правые концы также неубывают (иначе один из интервалов был бы лишним): $r_0 \le r_1 \le r_2 \le \dots$. Теперь заметим, что если взять интервалы через один, то они будут непересекающимися (если два интервала через один пересекаются, то интервал между ними, очевидно, лишиний). Соответственно мы получаем два семейства непересекающихся интервалов: с чётными номерами и с нечётными номерами. Рассмотрим одно из семейств; в нём длина каждого интервала в $c/2$ раз меньше, чем сумма априорных вероятностей всех рациональных чисел внутри него, и потому сумма длин всех интервалов не больше $2/c$. Всего для двух семейств получается оценка $4/c$, как мы и обещали.

Остаётся заметить, что случайное $\alpha$ не покрывается этими интервалами при некотором $c$. ►

С этим утверждением связаны различные естественные вопросы (на которые авторы не знают ответа). Насколько сильно могут отличаться $ВР(m)$ и $ВР'(m)$? Можно ли в описании $ВР(m)$ в терминах времени работы машин использовать префиксно-корректные машины вместо беспрефиксных? Можно ли вывести последний результат из теоремы Левина – Шнорра с априорной сложностью? Можно ли использовать аналогичные методы, чтобы установить, что $\sum_{x \in X} 2^{-l(x)}$ случайно для всякого беспрефиксного множества $X$, которое содержит область определения оптимального беспрефиксного декомпрессора?
Возвращаясь к «философскому смыслу» числа Ω, заметим, что его можно рас-
сматривать как бесконечный аналог объектов сложности *n*, рассмотренных в тео-
реме 15 (с. 36). Между ними есть и более формальная связь.

Теорема 116. Пусть Ωₙ — двоичное слово, составленное из первых n бит-
тов двоичной записи числа Ω. Тогда Ωₙ обладает свойствами, указанными в
теореме 15 с точностью до логарифмической поправки в значении п: любой из
указанных в этой теореме объектов может быть алгоритмически получен из
Ωₙ при известном п и наоборот (в обоих случаях — с поправкой O(log n) в
значении п).

◀ Мы уже видели, что по Ωₙ можно построить число t, большее ВР(n) (но-
мер приближения, которое превысит Ωₙ). Разница между префиксной и обычной
сложностью (из-за которой В(n) может быть больше ВР(n)) компенсируется из-
менением n на O(log n).

Теперь покажем, что верно и обратное: зная B(n) и n, можно найти Ω<sub>n-O(log n)</sub>.
В самом деле, сделаем B(n) шагов приближения снизу к Ω. Надо проверить, что в
полученном приближении снизу по крайней мере n - O(log n) знаков будут «окон-
чательными» (то есть будут совпадать с соответствующими знаками числа Ω). Если
это не так, то существует конечная двоичная дробь β из n - O(log n) знаков, раз-
деляющая достигнутое приближение и окончательное значение Ω. Эта дробь имеет
сложность n - O(log n); с другой стороны, зная β, мы можем найти число, боль-
шее B(n) — достаточно подсчитать число шагов, после которых приближение к Ω
впервые пересекает границу β. При достаточно большой константе в O(log n) эти
два обстоятельства противоречат друг другу. ►

Отсюда видно, что знание n + O(log n) битов в числе Ω позволяет ответить
на любой вопрос о завершении работы программы длины не более *n*. Поскольку
любой перечислимый вопрос, например, вопрос о выводимости формул длины *n*,
может быть представлен в таком виде, то — при достаточном художественном
воображении — можно, следуя Чейтину, назвать число Ω «числом мудрости», в
котором содержится информация обо всём на свете.

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

5.8. Эффективная размерность Хаусдорфа

В классической теории меры хорошо известно понятие размерности Хаусдорфа (часто упоминаемое в связи с «фракталами»). Его можно определить так. Пусть $\alpha > 0$ — некоторое действительное число. Будем говорить, что множество А является $\alpha$-нулевым, если для всякого $\varepsilon > 0$ его можно покрыть счётным семейством интервалов $I_k$ с

$$
\sum_k \mu(I_k)^\alpha < \varepsilon.
$$

Это определение предполагает, что А является подмножеством некоторого про-
странства, в котором выделен класс «интервалов» с определённой на них мерой μ.
Мы ограничимся случаем канторовского пространства, считая, что интервалами являются множества $\Omega_x$, состоящие из бесконечных продолжений слова x. Мера интервала $\Omega_x$ равна $2^{-I(x)}$.

Несколько простых замечаний.

(1) Подмножество $\alpha$-нулевого множества является $\alpha$-нулевым множеством.

(2) При $\alpha = 1$ мы получаем обычное определение множества меры нуль.

(3) При $\alpha > 1$ любое подмножество $A \subset \Omega$ является $\alpha$-нулевым (его можно покрыть $2^n$ интервалами, соответствующими $2^n$ словам длины $n$, и сумма $\alpha$-степеней их мер стремится к нулю при $n \to \infty$).

(4) Если $0 < \alpha < \alpha'$, то любое $\alpha$-нулевое множество является и $\alpha'$-нулевым (мера $\mu(I)$ интервала $I$ не превосходит 1, и потому $\mu(I)^{\alpha'} < \mu(I)^{\alpha}$).

**166** Предложите естественное определение $\alpha$-нулевого множества для подмножеств прямой и проверьте, что множество $A \subset [0, 1]$ является $\alpha$-нулевым тогда и только тогда, когда множество двоичных записей всех чисел из $A$ является $\alpha$-нулевым согласно определению. [Указание: по существу надо проверить, что разрешение рассматривать произвольные промежутки на прямой, а не только половины, четверти и т.п., не меняет класса нулевых множеств.]

Из наших замечаний следует, что для любого множества $A \subset \Omega$ есть некоторая граница $d \in [0, 1]$ с таким свойством: при $\alpha > d$ множество $A$ является $\alpha$-нулевым, а при $\alpha < d$ — нет. (При $\alpha = d$ множество может быть $\alpha$-нулевым, а может и не быть.) Эта граница называется хаусдорфовой размерностью множества $A$.

**167** Канторово множество на отрезке получается, если выбросить из отрезка среднюю треть (1/3, 2/3), у каждого из двух полученных отрезков выбросить среднюю треть и так далее. Докажите, что получится компактное множество, гомеоморфное $\Omega$ и имеющее хаусдорфову размерность $\log_3 2$.

[Указание. Верхняя оценка для размерности получается, если в качестве покрытия использовать все отрезки, оставшиеся к некоторому шагу — точнее, немного большие их интервалы. Чтобы получить нижнюю оценку, заметим, что (1) в силу компактности можно рассматривать конечные покрытия интервалами; (2) если есть покрытие канторова множества, то можно посмотреть отдельно на части этого покрытия, покрывающие первую и последнюю треть множества; любую из них можно увеличить в три раза до покрытия целого множества в силу самоподобия; если $\alpha$ меньше границы, то одно из покрытий будет лучше исходного, и так можно увеличивать размер интервалов, в конце концов прида к противоречию.]

**168** Предложите естественное определение размерности множеств в пространстве $(\mathbb{R}^3)$ по Хаусдорфу. Объясните, почему мера тел равна 3, поверхностей — 2, линий — 1, а точек — 0. Покажите, что в пространстве существует множество любой размерности от 0 до 3.

Теперь понятно, каким будет эффективный аналог понятия хаусдорфовой размерности (см. [163, 130]). Будем говорить, что множество $A \subset \Omega$ является эффективно $\alpha$-нулевым (для данного $\alpha > 0$), если существует алгоритм, который по рациональному $\varepsilon > 0$ указывает покрытие множества $A$ интервалами, у которых сумма $\alpha$-степеней мер не превосходит $\varepsilon$.
Как и в классическом случае, при увеличении $\alpha$ (и при уменьшении $A$) это свойство сохраняется. Принципиальная разница с классическим определением (как и для нулевых множеств) возникает дальше:

**Теорема 117.** При любом рациональном $\alpha > 0$ существует наибольшее по включению эффективно $\alpha$-нулевое множество.

◀ Доказательство этой теоремы повторяет аналогичное рассуждение для эффективно нулевых множеств в главе 3. Счётное объединение $\alpha$-нулевых множеств (классических) является $\alpha$-нулевым; аналогичным образом объединение перечислимого семейства эффективно $\alpha$-нулевых множеств является эффективно $\alpha$-нулевым. С другой стороны, при рациональном (и даже при любом вычислимом) $\alpha$ можно эффективно перечислить все эффективно $\alpha$-нулевые множества (точнее, алгоритмы, порождающие необходимые покрытия) — надо перечислять все, при этом корректируя излишние меры при необходимости. ▶

[169] Покажите, что это наибольшее множество состоит из тех и только тех последовательностей $\omega$, для которых разность $\alpha n - KP((\omega)_n)$ не ограничена сверху. [Указание: рассуждение аналогично доказательству теоремы Левина – Шнорра в варианте для префиксной сложности.]

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

**Теорема 118.** Наибольшее эффективно $\alpha$-нулевое множество существует тогда и только тогда, когда $\alpha$ перечислимо снизу.

◀ Пусть $\alpha$ перечислимо снизу. Это значит, что постепенно мы получаем всё более и более точные приближения к $\alpha$ с недостатком. Тем самым требования к покрытию (сумма $\alpha$-степеней мер любого конечного числа интервалов меньше $\varepsilon$) постепенно ослабевают, и мы можем «снять с полки» (как говорили про фильмы во время перестройки) и пропустить на выход забракованные ранее, а ныне знанные безопасными интервалы. Легко понять, что если алгоритм удовлетворяет требованиям для предельного $\alpha$, то рано или поздно любой порождённый им интервал будет пропущен.

Напротив, пусть существует наибольшее эффективно $\alpha$-нулевое множество. Рассмотрим соответствующий ему алгоритм. Его можно использовать для получения нижних оценок на $\alpha$. В самом деле, если этот алгоритм при некотором $\varepsilon$ выдал интервалы, для которых сумма $\beta$-степеней мер больше $\varepsilon$, то это означает только одно: выбранное нами $\beta$ меньше $\alpha$. Пробуя разные $\beta$, разные $\varepsilon$ и разные коечные наборы интервалов, мы получим перечислимое множество оценок снизу для $\alpha$.

Остаётся лишь показать, что эти оценки могут сколь угодно близко подходить к $\alpha$. Предположим, что это не так и что они все меньше некоторого $\alpha' < \alpha$. В этом случае всякое эффективно $\alpha$-нулевое множество будет и эффективно $\alpha'$-нулевым, чего не бывает, как мы увидим дальше (существуют множества любой эффективной размерности, см. задачу 170, с. 199). ▶
Теперь естественно дать такое определение. Эффективной хаусдорфовой размерностью множества $A \subset \Omega$ называется точная нижняя грань всех $\alpha$, при которых $A$ является эффективно $\alpha$-нулевым. Это число находится в промежутке $[0, 1]$ и не меньше (классической) хаусдорфовой размерности. (Первоначально определение эффективной хаусдорфовой размерности было предложено в терминах вычислимых мартингалов, см. [93, 100], где установлены приводимые ниже свойства размерности; об этом варианте определения см. далее в разделе 9.10.)

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

**Теорема 119.** Эффективная хаусдорфова размерность множества есть точная верхняя грань эффективных хаусдорфовых размерностей его элементов.

(Говоря об эффективной хаусдорфовой размерности точки $\omega \in \Omega$, мы имеем в виду размерность синглетона $\{\omega\}$.)

◀ Очевидно, размерность множества не меньше размерности любого его подмножества. Остаётся проверить, что если размерности всех синглетонов, образованных элементами некоторого множества $A$, меньше некоторого рационального $r$, а $r'$ больше $r$ (и тоже рационально), то размерность множества в целом не превосходит $r'$. А это сразу следует из теоремы 117: все синглетоны лежат в наибольшем эффективно $r'$-нулевом множестве, поэтому $A$ является его подмножеством и имеет размерность не больше $r'$. ▶

Как же найти эффективную размерность синглетона? Оказывается, она имеет следующее простое описание в терминах колмогоровской сложности.

**Теорема 120.** Эффективная хаусдорфова размерность множества $\{\omega\}$, где $\omega = \omega_0\omega_1\omega_2\dots$, равна

$$ \liminf_{n \to \infty} \frac{KS(\omega_0\omega_1\dots\omega_{n-1})}{n}. $$

(В формулировке теоремы говорится о простой колмогоровской сложности начальных отрезков. Однако это не принципиально: поскольку разница между различными вариантами сложности имеет порядок $O(\log n)$ для слов длины $n$, при делении на $n$ и переходе к пределу она исчезает.)

◀ Надо доказать неравенство в две стороны.

Предположим, что нижний предел меньше некоторого рационального $r$. Надо проверить, что множество $\{\omega\}$ является эффективно $r'$-нулевым для любого рационального $r' > r$.

Рассмотрим для каждого $n$ все слова длины $n$, имеющие сложность меньше $rn$. Таких слов не больше $O(2^{rn})$. Условие про нижний предел гарантирует, что при бесконечно многих $n$ начальный отрезок последовательности $\omega$ оказывается в числе таких слов. Рассмотрим все интервалы $\Omega_z$, порождённые этими словами $z$. Мера каждого из $\Omega_z$ в степени $r'$ есть $2^{-r'n}$, и суммарная $r'$-мера равна $O(2^{(r-r')n})$, что с ростом $n$ убывает как геометрическая прогрессия. Ряд $\sum_n 2^{(r-r')n}$ сходится, и если
отбросить некоторый его начальный кусок (рассматривать слова длины $N$ и более), то суммарная $r$'-мера этих слов может быть сделана сколь угодно малой (выбором достаточно большого $N$). Между тем по предположению о нижнем пределе остаток будет по-прежнему покрывать $\omega$. В одну сторону неравенство доказано.

Напротив, пусть $\{\omega\}$ имеет эффективную размерность меньше $r$ для некоторого рационального $r$. Покажем, что нижний предел, о котором идёт речь в теореме, не превосходит $r$.

По определению для каждого рационального $\varepsilon > 0$ можно эффективно перечислять последовательность интервалов, про которую известно, что один из них содержит $\omega$ и сумма ряда из $r$-степеней длин не больше $\varepsilon$. Сделаем это для $\varepsilon = 1, 1/2, 1/4, \dots$ и получим последовательность интервалов, у которых сумма $r$-степеней длин ограничена и которые покрывают $\omega$ бесконечно много раз. Другими словами, мы нашли вычислимую последовательность слов $x_0, x_1, \dots$ с такими свойствами:

* $\sum 2^{-rl(x_i)} < \infty$;

* $x_i$ является началом $\omega$ при бесконечно многих $i$.

Из первого условия следует, что $m(i) \ge c2^{-rl(x_i)}$ при некотором положительном $c$ и всех $i$ (здесь $m$ — наибольшая полумера на натуральных числах, рассмотренная в главе 4). Переходя к логарифмам, получаем оценку для префиксной сложности $KP(x_i) \le KP(i) + O(1) \le rl(x_i) + O(1)$. Остаётся заметить, что длины $x_i$ стремятся к бесконечности (поскольку ряд сходится), что среди $x_i$ имеется бесконечно много начал последовательности $\omega$ и что простая сложность не превосходит префиксной. (А также вспомнить определение нижнего предела и заметить, что если последовательность бесконечно много раз не превосходит $r$, то её нижний предел не превосходит $r$.) ►

**170** Выведите из этой теоремы, что для любого действительного $\alpha \in [0, 1]$ существует множество (и даже одноэлементное множество) с эффективной размерностью $\alpha$. [Указание: сложность начальных отрезков можно увеличивать, добавляя случайные биты, и уменьшать, добавляя нулевые биты.]

**171** Покажите, что для эффективно замкнутого подмножества в пространстве $\Omega$ (дополнение которого представляет собой объединение перечислимого семейства интервалов) хаусдорфова размерность совпадает с эффективной хаусдорфовой размерностью. [Указание: покрытия в силу компактности можно считать конечными, и искать их перебором.]

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

**173** Покажите, что для всякого $\alpha \in [0, 1]$ существует множество с (классической) хаусдорфовой размерностью $\alpha$. [Указание. Можно взять множество последовательностей, у которых на некоторых местах стоят нули.]

**174** Докажите, что определение эффективной хаусдорфовой размерности не изменилось бы, если вместо наличия для каждого $\varepsilon$ покрытия с суммой степеней
меньше ε мы бы требовали наличия одного покрытия с конечной суммой степеней, но покрывающего каждый элемент множества бесконечно много раз. [Указание. Если такое покрытие есть для некоторого α, то для большего α' те же самые интервалы дадут меньше члены ряда, и уменьшение будет тем больше, чем длиннее двоичное слово. Остаётся заметить, что можно выбросить из покрытия все короткие двоичные слова, так как оно было в бесконечное число слоёв.]

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

## 5.9. Случайность по различным мерам

### 5.9.1. Переход от одной меры к другой

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

Оговорка такая: если некоторая последовательность имеет положительную ве- роятность по вычислимой мере, то она случайна по этой мере (поскольку, очевидно, не может содержаться в нулевом множестве). Такая последовательность обязатель- но вычислима. Это можно доказать, сославшись на пункт (ж) теоремы 79, а также с помощью такого простого рассуждения. Пусть {$ω$} имеет положительную веро- ятность ε относительно вычислимой меры μ. Посмотрим на μ-меры множеств Ωх, где х — начала ω. С ростом х они убывают, оставаясь большими или равными ε. Дождёмся момента, когда они станут меньше 1,1ε. У каждого такого начала х лишь одно из слов х0 и х1 имеет меру больше 0,9ε, и его можно найти, раз мера вычи- слима, поэтому с этого места последовательность можно вычислимо продолжать.

Исключим этот особый случай и будем рассматривать только безатомные вы- числимые меры, для которых одноэлементные множества имеют меру 0. Тогда множества случайных последовательностей по двум таким мерам находятся в есте- ственном взаимно однозначном соответствии.

**Теорема 121.** Пусть μ₁ и μ₂ — две безатомные вычислимые меры. Тогда существует взаимно однозначное соответствие между множествами МЛ-слу- чайных по μ₁ и μ₂ последовательностей, которое в обе стороны задаётся вы- числимым отображением Σ → Σ.

Другими словами, существуют две машины М₁₂ и М₂₁ с оракулом, при этом если оракулом является случайная по μ₁ последовательность ω, то $M_{12}^ω$ будет слу- чайной по μ₂ последовательностью, и наоборот, причём эти отображения (на слу- чайных последовательностях) взаимно обратны.
Следуя [196], построим взаимно однозначное соответствие между последовательностями, случайными по мере $\mu_1$, и случайными точками отрезка $[0, 1]$ (по равномерной мере). А именно, как мы уже не раз делали, разобьём отрезок $[0, 1]$ на два: левый $\pi_0$ длиной $\mu_1(\Omega_0)$ и правый $\pi_1$ длиной $\mu_1(\Omega_1)$, каждый из них разобьём на две части аналогичным образом и так далее. Последовательности $\omega$ поставим в соответствие общую точку всех отрезков $\pi_x$, где $x$ — начала $\omega$. Условие безатомности гарантирует, что эта общая точка единственна.

Это отображение является изоморфизмом пространств с мерой, а именно пространства $\Omega$ с мерой $\mu_1$ и отрезка $[0, 1]$ с равномерной мерой. Оно не является взаимно однозначным, так как концам отрезков соответствуют сразу две последовательности, но это множество меры нуль. Вычислимость меры гарантирует, что при этом эффективно нулевые множества соответствуют эффективно нулевым, а случайные последовательности — случайным, и тут уже нет неоднозначности (концы отрезков вычислимы и не случайны, как и соответствующие им последовательности вида $x000...$ и $x111...$).

Остаётся сделать так для обеих мер $\mu_1$ и $\mu_2$ и воспользоваться отрезком с равномерной мерой на нём как промежуточным шагом. Вычислимость соответствующих отображений также следует из вычислимости мер $\mu_1$ и $\mu_2$. ►

В теории вычислимости говорят, что две последовательности (два множества натуральных чисел: последовательность отождествляется с множеством позиций, где в ней единицы) эквивалентны по Тьюрингу (лежат в одной тьюринговой степени), если каждая из них вычислима относительно другой (= с оракулом для другой). Классы эквивалентности называются тьюринговыми степенями. Доказанная теорема показывает, в частности, что множество тьюринговых степеней случайных по (безатомной вычислимой) мере $\mu$ последовательностей не зависит от выбора меры $\mu$.

175 Докажите, что любая последовательность, случайная по некоторой вычислимой мере $P$ (не обязательно безатомной), либо вычислима, либо эквивалентна по Тьюрингу последовательности, случайной по равномерной мере. [Указание. Построим вложенные отрезки для последовательности (обозначим её $\omega$), как это было описано выше, и рассмотрим их общую точку. Если она не единственна, то $\omega$ вычислима. Если общая точка $z$ единственна, то она случайна по мере Лебега на отрезке и вычислима с оракулом для $\omega$. Напротив, $\omega$ вычислима, если даны приближения к $z$: поскольку мы знаем, что $z$ случайна, то $z$ не может совпадать с (вычислимыми) границами отрезков.]

### 5.9.2. Последовательности, не случайные по вычислимым мерам

Пусть дана некоторая последовательность $\omega$. Всегда ли можно подобрать вычислимую меру, относительно которой последовательность $\omega$ будет случайной? Оказывается, что нет.

**Теорема 122.** Существует бесконечная последовательность нулей и единиц, не случайная ни по какой вычислимой мере на $\Omega$.
Последовательности, случайные по некоторой вычислимой мере, были названы «правильными» в статье [196] (в английском переводе этой статьи использован термин “proper”).

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

Критерий случайности (в смысле Мартин-Лёфа) по вычислимой мере $P$ можно переформулировать следующим образом. Для каждого слова $x$ рассмотрим величину

$$d_P(x) = -\log_2 P(\Omega_x) - KA(x).$$

Назовём её дефектом случайности двоичного слова $x$ относительно вычислимой меры $P$. Объяснение этого названия: последовательность $\omega$ случайна (в смысле Мартин-Лёфа) тогда и только тогда, когда дефекты случайности её начальных отрезков ограничены.

Слова «дефект случайности» могут употребляться в самых разных смыслах; мы уже говорили об ограниченных в среднем и по вероятности дефектах для бесконечных последовательностей, а в главе 14 мы будем говорить о дефекте случайности элемента внутри конечного множества. Но в этом разделе, говоря о дефекте случайности, мы имеем в виду именно функцию $d_P$, определённую выше.

Приведённое определение предполагает, что $P(\Omega_x) > 0$; если $P(\Omega_x) = 0$, то дефект естественно считать бесконечным.

Дефект случайности всегда неотрицателен (с точностью до константы, см. теорему 89).

**176** Докажите, что для любого слова $x$ хотя бы одно из слов $x0$ и $x1$ имеет не больший дефект случайности, чем само $x$. (Вычислимая мера, относительно которой вычисляется дефект, фиксирована.)

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

Введя понятие дефекта, вернёмся к доказательству теоремы 122.

► Чтобы построить «неправильную» последовательность $\omega$, нам надо позабоититься, чтобы для каждой вычислимой меры $P$ у $\omega$ были начальные отрезки со сколь угодно большим дефектом относительно $P$. Получается счётное число требований: для каждой меры $P$ и для каждой константы $c$ мы должны обеспечить начальный отрезок, у которого дефект относительно $P$ не меньше $c$.

Применяя диагональную конструкцию, мы строим искомую последовательность постепенно: на каждом шаге мы прибавляем к уже построенной части кусок, после которого выполнено очередное требование. Таким образом, нужно проверить, что для любого конечного слова $x$ и любой вычислимой меры $P$ существует продолжение у слова $x$, имеющее сколь угодно большой дефект случайности относительно $P$. В самом деле, будем продолжать $x$ так, чтобы добавление очередного бита уменьшало меру $P$ не менее чем (скажем) в полтора раза. Это можно сделать
вычислимо, поэтому сложность будет расти медленно, а мера убывать быстро, и в какой-то момент мы достигнем требуемого. ►

По существу то же самое рассуждение можно изложить с помощью так называемых «генерических» последовательностей. Напомним, что подмножество А пространства Ω называется всюду плотным, если оно пересекается с любым интервалом. Знаменитая теорема Бэра утверждает, что пересечение счётного семейства всюду плотных открытых множеств (открытые множества — объединения интервалов) непусто (и даже всюду плотно).

[177] Докажите это утверждение, взяв произвольное конечное слово и прибавляя к нему фрагменты так, чтобы попасть внутрь очередного открытого всюду плотного множества.

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

[178] Докажите, что никакая генерическая последовательность не удовлетворяет усиленному закону больших чисел. [Указание. Множество последовательностей, у которых есть начало длины более N, на 99% состоящее из единиц, является эффективно открытым и всюду плотным. Аналогично для нулей вместо единиц.]

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

В отличие от случайности, определение генерической последовательности не предполагает никакой меры.

[180] Докажите, что генерическая последовательность не может быть случайной ни по какой вычислимой мере. [Указание: достаточно построить эффективно открытое всюду плотное множество сколь угодно малой меры. Для этого можно из двух половинок каждого интервала выбирать меньшую (или чуть-чуть большую) по мере.]

В статье [196] указан другой метод построения «неправильной» последовательности: как говорит замечание после определения 4.4 в этой статье, несложно показать, что характеристическая последовательность универсального перечислимого множества не является случайной ни по какой вычислимой мере. Правда, там не указано, в каком смысле понимается универсальность. Скорее всего утверждение, которое авторы этой статьи имели в виду, вытекает из следующего результата:

[181] Покажите, что существует перечислимое множество, характеристическая последовательность которого не случайна ни по какой вычислимой мере.
[Указание. Поскольку сложности начальных отрезков будут логарифмически
ми для любого перечислимого множества, достаточно гарантировать, что их меры
быстро убывают. Разделим натуральный ряд на счётное число арифметических про-
грессий; i-я из них будет отвечать за i-ю вычислимую меру. Мы будем добиваться,
чтобы последовательность битов, записанная на месте i-й прогрессии, была не слу-
чайна относительно проекции i-й меры на эти координаты, выбирая направление,
в котором мера заметно убывает. (Далее мы используем теорему 123). Это постро-
ение предполагает, что i-й алгоритм действительно задёт меру; поскольку мы на
самом деле этого не знаем, получается перечислимое (а не разрешимое) множе-
ство.]

Интересно, что не все перечислимые неразрешимые множества обладают ука-
занным в этой задаче свойством:

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

[Указание (Л. Бьенвеню). Пусть $a_i$ — вычислимая последовательность рациональных чисел, плотная в $[0, 1]$. Построим вычислимое отображение пространства $\Omega$ в себя: последовательности $\alpha$, интерпретируемой как двоичная дробь в $[0, 1]$, становится в соответствие последовательность $\omega$, у которой $\omega_i = 1$ при $a_i < \alpha$ и $\omega_i = 0$ при $a_i > \alpha$. (При этом $\omega_i$ не определено, если $\alpha$ встречается среди $a_1, \dots, a_i$.) Это отображение определено почти всюду по равномерной мере. Образ равномерной меры — вычислимая мера на $\Omega$, а образ перечислимого снизу случайного числа — случайная по этой мере последовательность, являющаяся характеристикой функцией перечислимого неразрешимого множества. (Для неразрешимости важна плотность $a_i$ в $[0, 1]$.) См. разделы 5.7 и 5.9.3.]

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

183. Докажите, что существует невычислимый оракул А с таким свойством:
никакая вычислимая относительно А последовательность не случайна по равномер-
ной мере.

[Указание. Этот оракул надо строить диагональным методом, по частям. Во-первых, можно всегда добавить кусок, который гарантирует, что он не вычисляется i-й машиной Тьюринга. С другой стороны, можно добавить кусок, который гарантирует, что i-я машина Тьюринга с этим оракулом либо вычисляет не всюду определённую последовательность, либо вычисляет последовательность, в которой есть начало большого дефекта. В самом деле, если свободную часть оракула можно подобрать так, чтобы машина вычислила очень длинную последовательность, то сделаем это первым встретившимся способом и получим простое длинное начало. Если же так подобрать нельзя, то машина заведомо не вычислит всюду определённой последовательности.]
Утверждение последней задачи следует из двух интересных (но трудных) результатов, выходящих за рамки нашей книги. Первый из них доказал В. Выюгин [186]: можно построить вероятностную машину, которая с положительной вероятностью выдаёт последовательности, обладающие указанным в задаче свойством.

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

Во-вторых, утверждение этой задачи можно вывести из недавних (но уже знаменитых) результатов о «низких множествах», см. книги Ниса [127] и Доуни — Хиршфельдта [37]: существует перечислимое неразрешимое множество А, добавление которого в качестве оракула не меняет класса случайных последовательностей (а также не меняет префиксной сложности, хотя сейчас это нам не важно). Соответственно никакая А-вычислимая последовательность не может быть случайной, поскольку она очевидно не является А-случайной. (Отметим, что здесь мы получаем множество А с дополнительным условием перечислимости.)

Таким образом, мы видим, что по самым разным причинам бывают последовательности, к которым не сводятся по Тьюрингу никакие случайные. Но в обратную сторону ситуация другая: всякая последовательность сводится по Тьюрингу к случайной по равномерной мере последовательности (см. ниже теорему 126, с. 214). Доказательство этой теоремы показывает также, что всякая тьюрингова степень выше 0' (к которой сводится проблема остановки) содержит случайную последовательность, см. задачу 190 на с. 216.

**184** Покажите, что существует последовательность, эквивалентная (по Тьюрингу) случайной по равномерной мере последовательности, но не случайная ни по какой вычислимой мере. [Указание. На чётных местах поместим генерическую последовательность, а на нечётных — ту случайную по равномерной мере, к которой она сводится. Надо использовать ещё тот факт, что если последовательность случайна по мере P, то подпоследовательность её членов с чётными номерами случайна относительно проекции P на эти координаты, см. теорему 123.]

Последовательности, не случайные ни по какой вычислимой мере, в некотором смысле аналогичны нестохастическим по Колмогорову конечным объектам (см. раздел 14.2). Более того, несложно показать, что если последовательность случайна по некоторой вычислимой мере, то её начальные отрезки являются стохастическими (задача 348, с. 475).

### 5.9.3. Случайность по образу меры

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

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

Во-первых, у нас как раз для этого есть определение случайности по Мартин-Лёфу относительно меры $\mu$, и можно объявить «правдоподобными» случайные в этом смысле последовательности.

Во-вторых, мы можем посмотреть вовнутрь машины и спросить: а в какие последовательности мы готовы поверить на выходе датчика случайных битов? естественно считать, что в МЛ-случайные по равномерной мере. Соответственно, на выходе мы ожидаем их образы.

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

Пусть $\mu$ — вычислимое распределение вероятностей на $\Omega$, а $f: \Sigma \to \Sigma$ — непрерывное вычислимое отображение. Рассмотрим образ меры $\mu$ при этом отображении, то есть меру $\nu$ на пространстве $\Sigma$, для которой

$$ \nu(U) = \mu(f^{-1}(U)) $$

при $U \subset \Sigma$. Другими словами, $\nu$ — это распределение случайной величины $f(\omega)$, если $\omega$ — случайная величина с распределением $\mu$. Вообще говоря, $\nu$ не обязана быть сосредоточена на бесконечных последовательностях, то есть в нашей терминологии может быть не мерой, а полумерой. Предположим, однако, что это не так и что $\nu$ является мерой. (В этом случае, как мы видели, $\nu$ задаёт вычислимую меру на $\Omega$.)

**Теорема 123.** (а) Если $\omega$ — случайная по мере $\mu$ последовательность, то её образ $f(\omega)$ будет бесконечной последовательностью, случайной по мере $\nu$.

(б) Всякая случайная по мере $\nu$ последовательность может быть получена таким образом (равна $f(\omega)$ для некоторой случайной по мере $\mu$ последовательности $\omega$).

(Говоря о случайности в этой теореме, мы имеем в виду случайность в смысле Мартин-Лёфа.)

Прежде всего докажем, что образ $\mu$-случайной последовательности не может быть конечным словом. В самом деле, рассмотрим бесконечные последовательности, входящие в прообраз этого конечного слова $z$, то есть в прообраз $\Sigma_z \setminus (\Sigma_{z0} \cup \Sigma_{z1})$. Прообраз $\Sigma_z$ есть эффективно открытое множество (объединение перечислимого семейства интервалов), прообраз $\Sigma_{z0} \cup \Sigma_{z1}$ — также эффективно открытое множество, являющееся подмножеством первого. Нам надо доказать, что прообраз разности (то есть разность прообразов) не содержит случайных последовательностей, то есть является эффективно нулевым относительно меры $\mu$ множеством. Это следует из такой общей леммы:

**Лемма 1.** Пусть $\mu$ — вычислимая мера на $\Omega$, а $U \subset V$ — два эффективно открытых множества, причём $\mu(V \setminus U) = 0$. Тогда $V \setminus U$ является
эффективно нулевым множеством (не содержит случайных последовательностей).

**Доказательство.** Очевидно, достаточно рассмотреть один интервал $I$ множества $V$ (ограничив $U$ этим интервалом). По мере перечисления интервалов множества $U$ обнаруживается всё большая часть интервала $I$, входящая в $U$. При этом мера обнаруженной части стремится к мере интервала $I$ (непрерывность меры), и рано или поздно мы дождёмся момента, когда разность по мере будет меньше $\varepsilon$, какое бы $\varepsilon > 0$ нам бы ни задали. Лемма 1 доказана. (Заметим в скобках, что это рассуждение годится для любого открытого $V$; эффективность мы не использовали.)

Чтобы завершить доказательство пункта (а), осталось показать, что образ $\mu$-случайной последовательности $\omega$ не может быть $\nu$-неслучайным, то есть содержаться в эффективно $\nu$-нулевом множестве. Но если бы $f(\omega)$ можно было покрыть интервалами сколь угодно малой меры, то беря $f$-прообразы этих интервалов, мы бы получили покрытие последовательности $\omega$ сколь угодно малой меры (прообраз эффективно открытого множества открыт и по определению имеет ту же меру). Утверждение (а) доказано.

**185** Докажите количественный вариант этого утверждения: ограниченный в среднем дефект случайности последовательности $f(\omega)$ по мере $\nu$ превосходит ограниченный в среднем дефект случайности последовательности $\omega$ по мере $\mu$ не более чем на константу, зависящую от мер и от отображения, но не от последовательности $\omega$. (В этой задаче, говоря о дефектах случайности, мы имеем в виду определение раздела 3.5 для бесконечных последовательностей.)

Докажем теперь утверждение (б), используя понятие дефекта (для конечных последовательностей, в смысле определения на с. 202). Пусть последовательность $\tau$ случайна по мере $\nu$. Это значит, что дефекты её начальных отрезков относительно этой меры ограничены. Теперь применим следующую лемму, которую можно рассматривать как аналог утверждения (б) для конечных последовательностей:

**Лемма 2.** Пусть $\mu$ — произвольное двоичное слово, для которого $\nu(\Omega_\mu) > 0$. Тогда существует двоичное слово $w$, для которого $\mu \le f(w)$ (слово и является началом $f(w)$) и $d_\mu(w) \le d_\nu(u) + O(1)$.

(Имеется в виду, что константа в $O(1)$ не зависит от слова $u$, но может зависеть от выбора $f$, $\mu$ и $\nu$; через $d_\mu$ и $d_\nu$ обозначены соответствующие дефекты.)

**Доказательство.** Рассмотрим прообраз множества $\Sigma_u$ при отображении $f$. Это эффективно открытое множество в $\Sigma$, которое мы обозначим через $F_u$. По построению $\mu$-мера множества $F_u$ (сосредоточенная на бесконечных последовательностях) равна $\nu(\Omega_u)$. Если дефект $d_\nu(u)$ мал, то эта мера не может быть сильно меньше априорной вероятности слова $u$.

Рассмотрим теперь априорную вероятность множества $F_u$, то есть вероятность того, что универсальная вероятностная машина $M$ на выходе даст элемент из $F_u$, или, другими словами, вероятность того, что машина $f \circ M$ (к выходу $M$ дополнительно применяем $f$) даст некоторое продолжение слова $u$. Сравнивая машину $f \circ M$ с универсальной, заключаем, что априорная вероятность множества $F_u$ лишь в константу раз превышает априорную вероятность слова $u$, которая не более чем
в $2^{d_v(u)}$ раз превышает $v(u)$, которое равно $\mu$-мере множества $F_u$. Таким образом мы получаем неравенство для двух мер множества $F_u$ (априорной вероятности, которую мы обозначим через $A$, и меры $\mu$):

$$ \frac{A(F_u)}{\mu(F_u)} \le O(2^{d_v(u)}). $$

Множество $F_u$ представимо в виде объединения (пусть неперечислимого) непересекающихся интервалов, и ясно, что для одного из интервалов $\Sigma_w$ выполнено аналогичное неравенство:

$$ \frac{A(\Sigma_w)}{\mu(\Sigma_w)} \le O(2^{d_v(u)}). $$

Поскольку $\Sigma_w \subset F_u$, то $f(w) \ge u$, а неравенство даёт оценку $d_\mu(w) \le d_v(u) + O(1)$, что и требовалось. Лемма 2 доказана.

Продолжая доказательство утверждения (б) теоремы, применим доказанную лемму к начальным отрезкам $t_0, t_1, t_2, \dots$ случайной по мере $v$ последовательности $\tau$ (имеющим длины $0, 1, 2, \dots$). Их $v$-дефекты ограничены, и по лемме можно найти последовательность $w_0, w_1, \dots$ слов с ограниченными $\mu$-дефектами, для которых $f(w_i)$ является продолжением $t_i$. Если бы $w_i$ ещё продолжали друг друга, то мы достигли бы желаемого. Но это ниоткуда не следует. Тем не менее, применяя обычное рассуждение с компактностью, можно из последовательности $w_i$ выделить либо бесконечную подпоследовательность, состоящую из равных слов, либо бесконечную подпоследовательность, сходящуюся к некоторой бесконечной последовательности $\omega$ (последнее означает, что любой начальный отрезок $\omega$ является начальным отрезком всех членов подпоследовательности, начиная с некоторого).

В первом случае последовательность $\tau$ вычислима, будучи образом конечного слова $w$, встречающегося среди $w_i$ бесконечно много раз. Это не противоречит случайности, если эта вычислимая последовательность имеет (как одноэлементное множество) положительную $v$-меру, но в этом случае в качестве $\omega$ можно взять любое бесконечное $\mu$-случайное продолжение слова $w$ (оно существует, так как $\mu$-дефект слова $w$ конечен и $\mu(\Omega_w) > 0$).

Осталось рассмотреть второй случай, когда бесконечная подпоследовательность последовательности $w_i$ сходится к некоторой последовательности $\omega$.

Здесь нам понадобится некоторая подготовка, так что мы сделаем отступление и докажем, что дефект почти монотонен. Вспомним критерий случайности Левина – Шнорра (теоремы 91 и 93). Мы видели, что для случайных в смысле Мартин-Лёфа последовательностей дефект их начальных отрезков ограничен, а для неслучайных — стремится к бесконечности. В частности, не бывает последовательностей, у которых определённый таким образом дефект неограничен, но не стремится к бесконечности. Почему так происходит? На этот вопрос даёт ответ следующая теорема.

**Теорема 124.** Пусть фиксирована вычислимая мера $P$. Тогда существует такая константа $c$, что для любого слова $x$ и для любого его продолжения у выполняется неравенство:

$$ d_P(y) \ge d_P(x) - 2 \log d_P(x) - c. $$
Смысл этой теоремы: любое продолжение конечной последовательности с большим дефектом имеет (почти столь же) большой дефект. Или: любое начало (конечной) последовательности с малым дефектом имеет (почти столь же) малый дефект.

Для любого $k$ рассмотрим перечислимое множество всех конечных последовательностей, у которых дефект больше $k$. Все их бесконечные продолжения образуют открытое множество $S_k$, у которого $P$-мера не больше $2^{-k}$. Рассмотрим теперь меру $P_k$ на $\Omega$, которая равна нулю вне $S_k$ и в $2^k$ раз превосходит $P$ внутри $S_k$. (Формально говоря, мера множества $U$ равна $2^k P(U \cap S_k)$). Отметим, что $P_k$ не является вычислимой мерой в нашем смысле слова, поскольку мера всего пространства не равна 1 (и даже не обязана быть вычислимой, а всего лишь перечислима снизу). Но $P_k$ вполне можно считать перечислимой снизу полумерой (оставшуюся до 1 вероятность считаем мерой пустого слова).

Рассмотрим теперь сумму

$$ \sum_k \frac{1}{2k^2} P_k, $$

которая задаёт некоторую перечислимую снизу полумеру $S$ (двойка в знаменателе добавлена, чтобы сумма ряда $\Sigma 1/(2k^2)$ была меньше единицы; меру пустого слова надо вновь увеличить). При этом

$$ -\log S(x) \le -\log P(x) - k + 2\log k + O(1) $$

для всех слов $x$, являющихся продолжениями какого-либо слова с дефектом больше $k$. Поскольку $S$ не больше априорной вероятности на дереве (с точностью до $O(1)$-множителя), получаем требуемое утверждение.

В этом рассуждении мы предполагали, что дефект $x$ конечен, то есть что $P(\Omega_x) \ne 0$. Но если это не так, то для любого продолжения у мера $P(\Omega_y)$ также нулевая, и дефект бесконечен. ►

Вернёмся к доказательству теоремы 123. Мы остановились на последовательности слов (подпоследовательности последовательности $w_i$), которая сходится к некоторой точке $\omega \in \Omega$. Все $w_i$ имеют малые дефекты. Заметим, что в этом случае:

(1) любой начальный отрезок $\omega$ является начальным отрезком одного из слов $w_i$, а их $\mu$-дефекты ограничены, поэтому по теореме 124 и $\mu$-дефекты начальных отрезков $\omega$ ограничены, и потому $\omega$ является $\mu$-случайной;

(2) по ранее доказанному в пункте (а) последовательность $f(\omega)$ бесконечна;

(3) последовательность $f(\omega)$ не может иметь начальных отрезков, не являющихся начальными отрезками $\tau$, поскольку в этом случае у $\omega$ был бы начальный отрезок, образ которого несовместим с $\tau$, и этот отрезок был бы (в силу сходимости) начальным отрезком сколь угодно далёких $w_i$, образы которых имеют сколь угодно длинное общее начало с $\tau$.

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

Теорема 123 имеет и другие доказательства. Следующее рассуждение было предложено Ан. А. Мучником:

**186** Дайте прямое доказательство утверждения (б), используя лишь определение эффективно нулевого множества.
[Указание. Для данного $\epsilon$ рассмотрим покрытие $Z_\epsilon$ наибольшего эффективно μ-нулевого множества интервалами суммарной μ-меры меньше $\epsilon$; пусть $F$ — замкнутое множество бесконечных последовательностей, оказавшихся непокрытыми. Все последовательности из $F$ случайны, поэтому функция $f$ всюду определена на $F$ (значения — бесконечные последовательности). Образ $F$ будет замкнутым множеством, и его мера больше $1 - \epsilon$ (прообраз содержит $F$); дополнение является открытым множеством, имеет меру не больше $\epsilon$ и покрывает все точки, не имеющие прообразов в $F$. Единственная оставшаяся проблема — надо эффективизировать доказательство теоремы о компактности образа компактного множества при непрерывном отображении и заключить, что дополнение к образу $F$ не просто открыто, но и эффективно открыто равномерно по $\epsilon$.]

Аналогичное рассуждение позволяет получить и количественную версию утверждения (б), показывающую, что оценка задачи 185 точна: ограниченный в среднем $\nu$-дефект последовательности $\omega$ совпадает с точностью до $O(1)$-слагаемого с точной нижней гранью ограниченных в среднем $\mu$-дефектов всех $f$-прообразов этой последовательности.

**187** Докажите утверждение, которое можно рассматривать как конечный аналог пункта (а) теоремы 123: если $u$ и $w$ — два двоичных слова, причём $u \le f(w)$, то

$$d_{\nu}(u) \le d_{\mu}(w) + 2 \log d_{\mu}(w) + O(1).$$

[Указание. Последовательности с большим $\nu$-дефектом покрываются множеством малой $\nu$-меры, поэтому их прообразы покрываются множеством малой $\mu$-меры и потому имеют большой $\mu$-дефект. Отметим, что это утверждение является обобщением теоремы 124.]

Теорема 123 имеет довольно неожиданные следствия. Приведём несколько примеров.

**188** Пусть последовательность $\omega$ — случайна в смысле Мартин-Лёфа относительно бернуллиевой меры (все испытания независимы) с вероятностью единицы $1/3$. Докажите, что существует последовательность $\omega'$, случайная относительно равномерной меры, которая получается из $\omega$ заменой некоторых нулей на единицы. [Указание. Рассмотрим случайную последовательность независимых случайных точек, равномерно распределённых на $[0, 1]$, точнее, последовательность случайных битов, записанных в двумерную таблицу, строки которой — бесконечные двоичные дроби. Заменим точки, большие $2/3$, на единицы, а остальные на нули. Доказанная теорема утверждает, что получится последовательность, случайная по бернуллиевой мере с вероятностью единицы $1/3$, и что всякая случайная по этой мере последовательность может быть получена таким образом. Аналогично для границы $1/2$, откуда и следует утверждение задачи.]

Другое следствие теоремы 123 и его обобщения мы сейчас обсудим.

### 5.9.4. Теорема Ламбальгена

Рассмотрим вероятностную машину, которая получает с помощью датчика случайных битов последовательность $\omega_0\omega_1\omega_2\dots$, и выдаёт на выход последователь-
igkeit $\omega_0\omega_2\omega_4...$ (пропуская каждый второй бит). Ясно, что распределение веро-
ятностей на выходе такой машины будет равномерным, и теорема 123 даёт такие
два утверждения:

(а) если $\omega_0\omega_1\omega_2...$ — случайная по равномерной мере последовательность, то
и последовательность $\omega_0\omega_2\omega_4...$ случайна по той же мере;

(б) для всякой случайной по равномерной мере последовательности $\omega_0\omega_2\omega_4...$
можно найти такую последовательность $\omega_1\omega_3\omega_5...$, что их смесь $\omega_0\omega_1\omega_2...$ будет
случайной.

Первое несложно усмотреть непосредственно, а второе совсем не так очевидно.
Это утверждение можно переформулировать для пар последовательностей: если
$\alpha$ — случайная по равномерной мере последовательность, то можно найти после-
довательность $\beta$, для которой пара $\langle\alpha, \beta\rangle$ будет случайной (в естественном смысле,
относительно независимых равномерных мер на координатах).

Возникает вопрос: хорошо, такая $\beta$ существует, но какими она должна
дать свойствами, чтобы пара $\langle\alpha, \beta\rangle$ была случайной? Ясно, что $\beta$ сама должна
быть случайной (по уже доказанному), но этого мало. Скажем, нельзя положить
$\beta = \alpha$, поскольку пара $\langle\alpha, \alpha\rangle$ не случайна. (Ей соответствует последовательность
$\omega_0\omega_1\dots$, в которой каждый бит повторяется дважды.)

Ответ на этот вопрос такой: последовательность $\beta$ должна быть случайной по
равномерной мере, даже если разрешить использовать (в определении случайно-
сти) $\alpha$ в качестве оракула. Это утверждает следующая теорема Ламбальгена [73].
Пусть $P$ и $Q$ — два вычислимых распределения на пространстве $\Omega$. Рассмотрим
произведение этих распределений; получится вычислимое распределение на $\Omega \times \Omega$
(которое изоморфно $\Omega$, и определения случайности на него очевидно переносятся).

**Теорема 125.** Пара последовательностей $\langle\xi, \eta\rangle$ случайна по Мартин-Лёфу относительно распределения $P \times Q$ тогда и только тогда, когда выполнены два условия:

(1) последовательность $\xi$ случайна в смысле Мартин-Лёфа по мере $P$;

(2) последовательность $\eta$ случайна в смысле Мартин-Лёфа с оракулом $\xi$ по мере $Q$.

Говоря о случайности с оракулом, мы имеем в виду, что алгоритм, перечисляю-
щий покрытие, теперь имеет $\xi$ в качестве оракула (от этого перечислимых множеств
и неслучайных последовательностей может стать больше, а случайных — меньше).

Можно ещё отметить, что $\xi$ и $\eta$ входят симметрично, поэтому условие (1)
можно было бы усилить, разрешив $\eta$ в качестве оракула. Но несимметричный вари-
ант кажется более естественным, его можно прочесть так: «выбрать пару случайно
означает случайно выбрать первый член пары, а затем, зная первый член, случайно
выбрать второй».

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

(1) Если последовательность $\xi$ не случайна и покрывается интервалами малой $P$-меры, то эти интервалы (умноженные на всё $\Omega$ по второй координате) дают покрытие пары $\langle\xi, \eta\rangle$ той же меры (относительно $P \times Q$). Можно также сослаться на теорему 123.
(2) Пусть для всякого $\epsilon$ можно перечислять (с оракулом $\xi$) семейство интервалов малой $Q$-меры, покрывающее $\eta$. Этот же процесс можно запустить и с любым другим оракулом, и он будет порождать какие-то интервалы, используя конечную информацию относительно оракула.

Таким образом мы получим (по данному $\epsilon$) некоторое перечислимое (без оракула) семейство прямоугольников с таким свойством: $Q$-мера сечения, в котором первая координата равна $\xi$, не больше $\epsilon$. Такое семейство легко переделать в семейство прямоугольников общей меры не больше $\epsilon$, если принудительно урезать прямоугольники так, чтобы в любом сечении мера была не больше $\epsilon$ и при этом сечения, где это неравенство и так выполнялось, не менялись. Получаем противоречие со случайностью пары $\langle\xi, \eta\rangle$.

Теперь докажем, что если пара $\langle\xi, \eta\rangle$ не случайна, то не выполнено одно из условий (1) и (2). Пусть имеется семейство прямоугольников с общей мерой не больше $\epsilon$, покрывающее $\langle\xi, \eta\rangle$. Пусть $U$ — объединение этих прямоугольников. Поэтому, при каких значениях первой координаты $x$) сечение $U_x = \{y \mid \langle x, y \rangle \in U\}$ имеет меру больше $\sqrt{\epsilon}$. Соответствующее подмножество (одномерное, по первой координате) имеет меру не больше $\sqrt{\epsilon}$ и его можно представить в виде перечислимого объединения интервалов. При этом для точки $\langle\xi, \eta\rangle$, покрытой исходным семейством прямоугольников, верно одно из двух: либо $\xi$ покрыта построенным семейством интервалов общей меры не более $\sqrt{\epsilon}$, либо $\langle\xi, \eta\rangle$ покрыта семейством прямоугольников, которые в $\xi$-сечении имеют $Q$-меру не больше $\sqrt{\epsilon}$. Во втором случае $\eta$ покрыта $\xi$-перечислимым семейством интервалов суммарной $Q$-меры не более $\sqrt{\epsilon}$.

Хотелось бы сделать так для каждого $\epsilon$ и заключить, что либо $\xi$ не случайна, либо $\eta$ не случайна с оракулом $\xi$. Первое гарантировано, если при всех $\epsilon$ имеет место первый вариант ($\xi$ покрыта интервалами); второе — если при всех $\epsilon$ случается второе. Но что делать, если при некоторых $\epsilon$ случается одно, а при других — другое?

Тут помогает такой трюк: выполним указанное построение для $\epsilon = 2^{-2k}$ при всех $k$. Тогда для каждого $k$ получится семейство $V(k)$ интервалов по первой координате, имеющих общую $P$-меру не более $2^{-k} = \sqrt{2^{-2k}}$. Теперь есть две возможности: либо при бесконечно многих $k$ это семейство покрывает $\xi$, либо для всех достаточно больших $k$ это семейство не покрывает $\xi$.

В первом случае для каждого $K$ объединим все семейства $V(k)$ при $k \ge K$; получится семейство интервалов с мерой не более $2 \cdot 2^{-K}$, и оно покрывает $\xi$ уже при любом $K$, так что $\xi$ не случайна.

Во втором случае есть способ (для всех $k$, начиная с некоторого, пусть нам и неизвестного) получить $\xi$-перечислимое покрытие для $\eta$, имеющее малую меру, и потому $\eta$ не случайна с оракулом $\xi$. ►

Эта теорема также имеет количественный вариант (см. [183]): можно доказать, что ограниченный в среднем дефект случайности пары $\langle\xi, \eta\rangle$ относительно меры $P \times Q$ равен сумме дефекта $\xi$ относительно $P$ и дефекта $\eta$ относительно $Q$ с оракулом $\xi$ и дополнительным условием, равным первому дефекту (округлённому до ближайшего целого числа). Правда, чтобы придать точный смысл этому утвержде-
нию, нужно определить понятие дефекта с оракулом и условием (как функцию последовательности, оракула и условия), но это можно сделать и получить таким образом формулу, аналогичную формулу для префиксной сложности пары. (Интелесно, что прямого способа вывести это из формулы для префиксной сложности пары, используя выражение для дефекта через префиксную сложность, не видно.)

Естественно попытаться обобщить эту теорему на случай зависимых величин и доказать что-нибудь в таком роде: пара $\langle \xi, \eta \rangle$ случайна относительно вычислимого распределения на $\Omega \times \Omega$, если $\xi$ случайна относительно проекции этого распределения на первую координату (эту проекцию называют маргинальным распределением), а $\eta$ случайна относительно условного распределения (при данном значении первой координаты) с оракулом $\xi$. Однако это не так просто. Во-первых, надо определить условное распределение (что можно сделать, если $\xi$ случайно, как доказал Хайято Такахаши); во-вторых, условная вероятность может не быть вычислимой, и надо как-то определять случайность. Эти вопросы разбираются в его статьях [164, 165], но критерия совсем без дополнительных ограничений пока получить не удалось.

### 5.9.5. Теорема Кучеры – Гача

Вернёмся к образу множества случайных последовательностей при вычислимых отображениях. Вопрос о том, какие последовательности могут (не вызывая отторжения гипотезы о случайности) появиться на выходе вероятностной машины, имеет смысл и в общем случае, без предположения о том, что вероятность появления конечной последовательности равна нулю. Пусть, как и прежде, имеется вычислимое распределение вероятностей $\mu$ на множестве $\Omega$, а также вычислимое непрерывное отображение $f: \Sigma \to \Sigma$. Тогда возникает распределение вероятностей на $\Sigma$, являющееся образом $\mu$ при отображении $f$. Мы, однако, не предполагаем, что оно сосредоточено на бесконечных последовательностях, так что получается некоторая перечислимая снизу полумера $v$, вообще говоря, не являющаяся мерой.

Мы можем теперь рассмотреть образы $\mu$-случайных последовательностей при отображении $f$. Как связано это множество с полумерой $v$? Можно ли утверждать, что оно определяется полумерой $v$ (как это было для случая мер, когда оно состояло из $v$-случайных последовательностей)? Может быть, верен аналог теоремы Левина – Шнорра и образы $\mu$-случайных последовательностей — это те и только те последовательности, у начальных отрезков которых отношение (непрерывной) априорной вероятности к $v$ ограничено?

К сожалению, рассуждения, использованные для случая мер, не работают, когда $v$ является лишь полумерой. (Проблемы возникают в обе стороны.) Более того, как недавно обнаружили Л. Бьенвеню и К. Портер, образ множества $\mu$-случайных последовательностей вообще не определяется полумерой $v$:

189 Покажите, что существуют вычислимые отображения $f_1, f_2: \Sigma \to \Sigma$, которые порождают одну и ту же выходную полумеру (как образ равномерной меры на $\Omega$), но для которых образы $f_1(R)$ и $f_2(R)$ множества $R$ случайных по Мартин-Лёфу последовательностей (относительно равномерной меры) различны.
[Указание. Будем рассматривать машины $f_1$ и $f_2$, которые печатают на выходе только нули (конечное или бесконечное число нулей). Такая машина, ограниченная на $\Omega$, описывается убывающей последовательностью равномерно эффективно открытых множеств $A_1 \supset A_2 \supset \dots$, где $A_i$ состоит из тех входов, для которых на выходе появляется $i$ или больше нулей. Выходное распределение машины при этом задаётся мерами множеств $A_i$. Остаётся построить две последовательности вложенных множеств, у которых меры одинаковы, но у одной пересечение содержит случайную точку, а у второй не содержит. Это делается так: рассмотрим перечислимое снизу случайное число $\omega$ и вычислимую возрастающую последовательность рациональных чисел $r_i$ с пределом $\omega$, и возьмём вложенные интервалы $(r_i, \omega + 1/i)$. Их пересечение содержит $\omega$, но если взять интервалы тех же длин с левой границей в нуле, то пересечение будет пусто (а если взять с серединой в $1/2$, пересечение будет состоять только из неслучайного числа $1/2$).]

Тем не менее следующий факт (который бы следовал из сформулированного выше «критерия», будь он верным: достаточно было бы взять в качестве $f$ универсальную вероятностную машину, выходное распределение которой совпадает с непрерывной априорной вероятностью!) всё же можно доказать (это сделали Кучера [69] и Гач (см. [46]):

**Теорема 126.** Пусть $\alpha$ — произвольная последовательность нулей и единиц. Тогда существует случайная (в смысле Мартин-Лёфа) по равномерной мере последовательность $\omega$, а также вычислимое отображение $f: \Sigma \to \Sigma$, для которого $f(\omega) = \alpha$.

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

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

▲ Будем доказывать несколько более сильное утверждение и построим вычислимое непрерывное отображение $f$ (одно для всех $\alpha$), для которого образ $f(R)$ множества $R$ случайных относительно равномерной меры последовательностей покрывает всё $\Omega$.

Более того, мы для любого эффективно открытого множества $U$ (объединения перечислимого семейства интервалов) с достаточно малой мерой построим вычислимое отображение $f$, для которого образ $f(\Omega \setminus U)$ покрывает всё $\Omega$. Поскольку в качестве $U$ можно взять покрытие максимального эффективно нулевого множества, отсюда следует требуемое утверждение.

Вот идея конструкции. Прежде всего, мы будем представлять себе область определения отображения $f$ (канторовское пространство) не как двоичное дерево, а как дерево с ветвлением $2^{k_0}, 2^{k_1}, \dots$ (где целые положительные числа $k_i$ достаточно быстро растут, см. далее). Мы вкладываем в него двоичное дерево (при этом остаётся много свободного места), и отображаем это вложенное дерево на полное двоичное
дерево (естественным образом). Другими словами, среди сыновей корня в новом дереве (слов длины $k_0$) мы выбираем какие-то два слова $s_0$ и $s_1$, затем у каждого их них выбираем по два продолжения длины $k_0 + k_1$ (слова $s_{00}$ и $s_{01}$ и $s_0$ и слова $s_{10}$ и $s_{11}$ у $s_1$), и так далее; $f$ отображает $s_v$ в $v$.

После этого мы смотрим, какие интервалы появляются в множестве $U$. Если они не включают в себя точки, соответствующие путям двоичного поддерева, то они никому не мешают: образ дополнения к $U$ по-прежнему содержит все двоичные последовательности. Если же какой-то путь попадёт в $U$, то есть один из интервалов, задающих $U$, попадёт в вершину двоичного поддерева, то эту вершину нужно заменить на запасную, найдя подходящего брата, и заново вложить соответствующий кусок двоичного поддерева, продолжив и отображение $f$. Это можно делать, пока испорченных вершин не станет слишком много: у корня надо испортить почти всех сыновей ($=всех, кроме одного$); сын корня будет испорчен, если у него самого почти все сыновья испорчены и так далее, пока мы не дойдём до первоисточников порчи, то есть интервалов множества $U$. Этих интервалов наберётся не менее чем на

$$ \left( \frac{2^{k_0} - 1}{2^{k_0}} \right) \cdot \left( \frac{2^{k_1} - 1}{2^{k_1}} \right) \cdot \left( \frac{2^{k_2} - 1}{2^{k_2}} \right) \cdot \dots, \quad (*) $$

так что проблем с запасными вершинами не будет, если размер $U$ меньше этой границы. Остаётся выбрать числа $k_0, k_1, \dots$ достаточно большими и быстро растущими, чтобы это произведение было строго положительным (или даже близким к единице).

Изложим это рассуждение более подробно. Выбрав (вычислимую) последовательность положительных целых чисел $k_0, k_1, k_2, \dots$, мы рассматриваем в качестве вершин нового дерева слова длины $k_0$ (получается ветвление $2^{k_0}$), затем слова длины $k_0 + k_1$ (так что на следующем уровне ветвление $2^{k_1}$) и так далее. Слова этих длин становятся вершинами некоторого дерева $T$; мы будем их называть $T$-вершинами, если нужно подчеркнуть различие с полным двоичным деревом.

Сначала мы выбираем (произвольным вычислимым образом) некоторое двоичное поддерево в $T$, и отображаем с помощью $f$ его вершины в вершины полного двоичного дерева. Затем мы перечисляем интервалы эффективно открытого множества $U$. Можно считать без ограничения общности, что эти интервалы соответствуют $T$-вершинам (имеют нужную длину). Когда появляется новый интервал, мы делаем следующее:

* Объявляем соответствующую $T$-вершину плохой.

* Распространяем плохие $T$-вершины к корню: если у $T$-вершины все или почти все ($=все, кроме одного$) сыновья плохие, то её тоже считаем плохой. В итоге может добавиться некоторая цепочка плохих $T$-вершин в направлении корня.

* Если плохие $T$-вершины пересеклись с текущим двоичным поддеревом, то корректируем его: берём ближайшую к корню плохую $T$-вершину, и заменяем её в поддереве на хорошего брата. (Отец ближе к корню, поэтому хороший, поэтому есть два хороших сына — так что найдётся хороший брат, не входящий в поддерево.) Затем из заменённой $T$-вершины выращиваем поддерево
из хороших $T$-вершин (и снова это возможно, так как у хорошей $T$-вершины всегда есть два хороших сына в $T$).

* Доопределяем отображение $f$ на вновь появившейся части двоичного поддерева.

Единственный случай, когда этого сделать не удастся — когда корень дерева станет плохой вершиной. В этом случае все его $T$-сыновья (кроме, возможно, одного) будут плохими, каждый из них либо окажется интервалом из $U$, либо будет иметь всех (кроме, возможно, одного) плохих сыновей, и так далее. В итоге получится дерево из плохих вершин, имеющее ветвление не меньше $2^{k_0} - 1$ (в корне), $2^{k_1} - 1$ (на следующем уровне) и так далее, а листья соответствуют интервалам $U$, так что размер $U$ не меньше произведения (*). Получаем положительную нижнюю оценку на размер $U$, если это произведение сходится — а оно сходится в том и только том случае, когда ряд $\sum 2^{-k_i}$ сходится. Поэтому, взяв (скажем) $k_i = \lceil 2 \log i \rceil$ (при $i \ge 2$) и достаточно малое множество $U$, мы гарантируем, что корень никогда не станет плохим.

Почему эта конструкция даёт нужный результат? Надо заметить, что

* множество плохих $T$-вершин может только увеличиваться;

* на каждом шаге конструкции двоичное поддерево не содержит ни одной плохой $T$-вершины;

* если $T$-вершина была исключена из двоичного поддерева, то эта $T$-вершина никогда вновь не попадёт в двоичное поддерево (и переопределять $f$ на ней не придётся).

Все эти свойства ясны по построению. (Последнее: если $T$-вершина была исключена из двоичного поддерева, то кто-то из её предков был в этот момент плохим, каковым он и остался, так что вновь в двоичное поддерево она попасть не сможет.)

Остаётся доказать, что при таком построении $f$ для любой последовательности $\alpha \in \Omega$ найдётся $f$-прообраз, не входящий в выброшенное открытое множество $U$. По построению в каждый момент $t$ найдётся прообраз $\omega_t$, не входящий в уже построенную часть $U$. Кроме того, с ростом $t$ последовательности $\omega_t$ сходятся к некоторому пределу $\omega$ (индукцией по уровню доказываем, что на этом уровне будет стабилизация, так как число возможных изменений ограничено). Надо проверить, что $\omega$ не принадлежит $U$ и что $f(\omega) = \alpha$.

Если $\omega$ принадлежит $U$, то $\omega$ попадает в некоторый интервал $U$, который рано или поздно обнаружится. После этого момента $\omega_t$ не могут лежать в $U$, что противоречит сходимости. Покажем, что $f(\omega) = \alpha$. Пусть $z$ — произвольное конечное начало $\alpha$; покажем, что $f(\omega)$ начинается на $z$. Пусть $k$ — длина $z$. На каждом шаге имеется некоторая ветвь в дереве (большого ветвления), состоящая из $k$ блоков и отображающаяся в $z$. Эта ветвь стабилизируется с ростом $t$, и после стабилизации в $f$ добавляется часть, гарантирующая, что $f(\omega)$ начинается на $z$. ►

**190** Покажите, что построенная в доказательстве теоремы случайная последовательность будет вычислимой с двумя оракулами $\alpha$ и $\omega'$ (проблема остановки). [Указание: предельное положение вложенного дерева вычислимо относительно $\omega'$.]

---

[Указание: предельное положение вложенного дерева вычислимо относительно $\omega'$.]
191 Выведите из доказательства теоремы, что для всякой последовательности $\alpha$ найдётся случайная последовательность $\omega$, к которой она сводится по Тьюрингу, причём для получения $n$ битов последовательности $\alpha$ используется не более $n + o(n)$ первых битов последовательности $\omega$. [Указание. Вместо двоичного дерева, которое мы вкладываем, можно рассматривать дерево ветвления $2^{m_i}$; тогда нужна сходимость произведения $(1 - 2^{m_i}/2^{k_i})$, то есть ряда $\sum 2^{m_i-k_i}$. Можно положить, например, $m_i = i$ и $k_i = i + 2 \log i$.]

В порядке философических спекуляций можно объяснить смысл утверждения теоремы Кучеры – Гача так. Для любой последовательности можно представить объяснение, почему её появление не удивительно: про случайные последовательности это как бы подразумевается определением случайности, и остаётся пристроить к датчику случайных чисел машину, реализующую вычислимое отображение $f$.

Утверждение теоремы можно интерпретировать как парадокс: с одной стороны, если некоторая последовательность $\alpha$ с положительной вероятностью вычислима относительно случайно взятой последовательности (в том смысле, что множество тех последовательностей, к которым $\alpha$ сводится, имеет положительную меру), то $\alpha$ вычислима. В самом деле, множество всех возможных оракулов разбивается на счётное число частей (соответствующих возможным машинам с оракулом), поэтому одна из частей имеет положительную меру. Поэтому априорная вероятность $\alpha$ положительна и $\alpha$ вычислима. С другой стороны, для каждой последовательности $\alpha$ есть случайная по Мартин-Лёфу последовательность $\omega$, относительно которой $\alpha$ вычислима. Противоречия тут нет, потому что нулевое множество тех последовательностей, относительно которых $\alpha$ вычислима, не обязано быть эффективно нулевым.
# 6. Общая классификация сложностей

## 6.1. Сложность разрешения

Начав с простой колмогоровской сложности $KS$, мы рассматривали затем также префиксную сложность $KR$ и монотонную сложность $KM$. Все три определялись с помощью кратчайших описаний, но способы описаний были из разных классов. Для простой сложности это были просто вычислимые функции, для префиксной сложности — вычислимые непрерывные отображения $\Sigma \to N_\perp$, для монотонной — вычислимые непрерывные отображения $\Sigma \to \Sigma$.

Для единообразия можно считать, что простая колмогоровская сложность определяется с помощью непрерывных вычислимых отображений $N_\perp \to N_\perp$, должным образом определив это понятие. Топология на множестве $N_\perp$ и само это множество были описаны в разделе 4.4.3 (с. 104). Несложно проверить, что непрерывные отображения $N_\perp \to N_\perp$ бывают двух видов: если $\perp$ отображается в некоторое натуральное число (а не в $\perp$), то отображение постоянно; если же $\perp$ отображается в $\perp$, то натуральные числа могут отображаться куда угодно независимо друг от друга: отображения второго типа находятся во взаимно однозначном соответствии с частичными функциями из $N \in N$, если значение $\perp$ ставить в соответствие точкам, на которых функция не определена. Как и раньше, естественно назвать отображение $f: N_\perp \to N_\perp$ вычислимым, если множество пар $(x, y)$, для которых $y \le f(x)$, перечислимо. Ясно, что все постоянные отображения вычислимы, а среди непостоянных вычислимы как раз те, которым соответствуют вычислимые в обычном смысле функции (вычислимость функции равносильна перечислимости графика). Поэтому ничего нового мы не получаем: добавляются постоянные функции, отображающие элемент $\perp$ и все натуральные числа в некоторое с, но с точки зрения сложности они ничего не дают. (Формально говоря, такие функции следует отличать от функций, которые соответствуют постоянным всюду определённым функциям $N \to N$, поскольку первые отображают $\perp$ в натуральное число, а вторые — в $\perp$.)

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

Одна из клеток в этой таблице пока не заполнена; она соответствует способам описания, которые являются вычислимыми непрерывными отображениями $N_\perp \in \Sigma$. Сейчас мы определим этот вид сложности, который называется сложностью разрешения и будет обозначаться $KR$ (иногда его ещё обозначают $KD$, но в последнее