# Колмогоровская сложность и алгоритмическая
случайность

Nikolay Vereshchagin, Vladimir Andreevich Uspensky, Alexander Shen

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

► To cite this version:

Nikolay Vereshchagin, Vladimir Andreevich Uspensky, Alexander Shen. Колмогоровская сложность и алгоритмическая случайность. , pp.575, 2013, 978-5-4439-0212-8. <lirmm-00786255>

HAL Id: lirmm-00786255

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00786255

Submitted on 25 Nov 2015

HAL is a multi-disciplinary open access archive
for the deposit and dissemination of scientific re-
search documents, whether they are published or not.
The documents may come from teaching and research
institutions in France or abroad, or from public or pri-
vate research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
Н.К. Верещагин

В. А. Успенский

А. Шень

КОЛМОГОРОВСКАЯ СЛОЖНОСТЬ И
АЛГОРИТМИЧЕСКАЯ СЛУЧАЙНОСТЬ

Москва

Издательство МЦНМО

2013
Верещагин Н. К. и др.

B77 Колмогоровская сложность и алгоритмическая случайность / Н. К. Верещагин, В. А. Успенский, А. Шень. — М.: МЦНМО, 2013. — 576 с.

ISBN 978-5-4439-0212-8

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

Предлагаемая книга содержит подробное изложение основных понятий алгоритмической теории информации и теории вероятностей, а также наиболее важных работ, выполненных в рамках «колмогоровского семинара по сложности определений и сложности вычислений», основанного А. Н. Колмогоровым в начале 1980-х годов.

Книга рассчитана на студентов и аспирантов математических факультетов и факультетов теоретической информатики.

ББК 22.12

Электронная версия книги является свободно распространяемой
и доступна по адресу ftp://ftp.mccme.ru/users/shen/kolmbook/

В оформлении форматов использованы фрагменты
рукописи статьи А. Н. Колмогорова [65].

Николай Константинович Верещагин

Владимир Андреевич Успенский

Александр Шень

КОЛМОГОРОВСКАЯ СЛОЖНОСТЬ
И АЛГОРИТМИЧЕСКАЯ СЛУЧАЙНОСТЬ

Издательство Московского центра

непрерывного математического образования

119002, Москва, Большой Власьевский пер., 11. Тел. (499) 241-74-83

Подписано в печать 02.11.2012 г. Формат 70×100¹/₁₆.

Бумага офсетная. Печать офсетная. Печ. л. 36. Тираж 1000. Заказ.

Отпечатано в ППП «Типография „Наука“».

121099, Москва, Шубинский пер., д. 6.
Памяти Андрея Мучника
Предисловие

Понятие **колмогоровской сложности** (или, как ещё говорят, **алгоритмической энтропией**) появилось в 1960-е годы на стыке теории алгоритмов, теории информации и теории вероятностей.

Идея А.Н. Колмогорова, опубликованная им в знаменитой статье 1965 года [63], состояла в том, чтобы измерять количество информации, заключённой в индивидуальных конечных объектах (а не в случайных величинах, как в шенноновской теории информации). Оказалось, что это возможно (хотя лишь с точностью до ограниченного слагаемого).

На несколько лет раньше сходные идеи высказывал Р. Соломонов (см. [160] и другие его статьи, ссылки на которые даны в [85])<fnref n="1" />. Он исходил из несколько другой мотивировки, пытаясь ввести понятие «априорной вероятности» — с какими вероятностями мы ожидаем появления тех или иных объектов, если ничего не знаем о порождающем их процессе? Оказалось, что вопросы эти тесно связаны. В самом первом приближении можно сказать так: если объект простой, то он имеет большую априорную вероятность, а если сложный — то малую. (К сожалению, работы Соломонова приобрели известность в основном лишь после того, как Колмогоров упомянул их в своей статье.)

В 1965 году американский математик Г. Чейтин (тогда только что окончивший школу) представил к публикации две своих статьи [19] и [20], напечатанные в 1966 и 1969 годах. Во второй из них он дал то же определение алгоритмической сложности, что и Колмогоров.

Основные свойства колмогоровской сложности были исследованы в 1970-е годы. К. П. Шнорр и Л. А. Левин (ученик Колмогорова) установили связь понятия сложности с алгоритмическим определением случайности (предложенным учением ком Колмогорова шведским математиком П. Мартин-Лёфом). При этом они ввели некоторый новый вариант понятия сложности (так называемую монотонную сложность). Идеи Соломонова об априорной вероятности привели к (введённому Левиным и позднее Чейтиным) понятию префиксной сложности, которое оказалось не только философски важным, но и технически удобным. Были найдены применения понятия сложности как в теории алгоритмов, так и в теории вероятностей.

Интерес к колмогоровской сложности (заслуженный — это, безусловно, одно из базисных понятий теории алгоритмов, имеющее фундаментальное значение) возрос в последние десятилетия, когда появилась монография Ли и Витаньи [85] (первое издание вышло в 1993 году). Без преувеличения можно сказать, что практически

<footnote n="1">¹«Я пришел к аналогичной концепции, еще не зная работ Соломонова», писал Колмогоров в названной выше статье [63]</footnote>
всё известное к тому моменту о колмогоровской сложности вошло в эту книгу (в основной текст или в упражнения). Книга включает в себя подробный рассказ об истории области, ссылки на первые публикации и так далее. Затем вышли книги К. Калюде [16], А. Ниса [127], а также Р. Доуни и Д. Хиршфельдта [37]; в них вошли многочисленные результаты, полученные в последние годы (в частности, связывающие понятия сложности и случайности с классической теорией вычислимости).

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

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

В конце книги в качестве приложения воспроизведен текст небольшой брошюры одного из авторов (В.У.), написанной по материалам его лекции для студентов младших курсов и старшеклассников (23 июля 2005 года в летней школе «Со временная математика» в Дубне; первое издание брошюры вышло в 2006 г. в из дательстве МЦНМО). На этой лекции было рассказано о различных подходах к математическому определению понятия случайности, и мы приводим её текст (с небольшими изменениями), чтобы читатель, не имеющий возможности или охоты подробно изучать соответствующие разделы основного текста, мог составить некоторое представление об этой теме.

К сожалению, с названиями, обозначениями и терминологией в этой области большая путаница — отчасти и по вине авторов этой книги. Например, в Приложении 2 использована терминология, отличная от терминологии, принятой в основном тексте. Там, в частности, появляются термины хаотический, типический и не предсказуемый<fnref n="1" />. Но суть, конечно, не в терминах, а в стоящих за ними понятиях. Каждый из названных терминов отражает некоторое специфическое свойство случайного объекта; хаотичность опирается на представление о колмогоровской сложности, типичность — на представление о мере множества, непредсказуемость — на представление о выигрывающем плане игры. Понятия хаотичности, типичности и непредсказуемости допускают строгие определения, каждое из которых может претендовать на то, что оно-то и есть истинное определение случайности. Совпадение по объёму понятий хаотичности и типичности для двоичных последовательностей, установленное теоремой Левина — Шнорра, является глубоким фактом, не очевидным априори и демонстрирующим адекватность соответствующих определе-

<footnote n="1">¹ Термины «хаотический» и «типический» дороги автору приложения тем, что были одобрые Колмогоровым и впервые публично прозвучали в 1986 г. на открытии Первого Всемирного конгресса Общества математической статистики и теории вероятностей им. Бернулли в докладе «Алгоритмы и случайность» А. Н. Колмогорова и В. А. У. Они же были использованы в статьях [67, 182, 167, 120].</footnote>
ний. Само основное понятие называют алгоритмической сложностью, колмогоровской сложностью, а также алгоритмической (или колмогоровской) энтропией. Мы будем считать все эти слова синонимами.

Термин «энтропия» в рассматриваемую тематику был введён Колмогоровым и не был для него случайным. Основатель теории информации Клод Шеннон построил её на вероятностном фундаменте. Колмогоров имел амбициозный план построить параллельную теорию, заменив вероятностный фундамент алгоритмическим. Для него было естественным сохранить основной термин шенноновской теории, термин «энтропия», но наполнить его новым содержанием. В своей статье [64] Колмогоров писал:

Обычно пользуются вероятностным определением энтропии, которое относится, однако, не к индивидуальным объектам, а к «случайным», т. е. по существу к распределениям вероятностей в каких-либо классах объектов. (...) Далеко не все применения теории информации укладываются разумным образом в такую интерпретацию её основных понятий. (...) Насколько я знаю, первой печатной публикацией, содержащей замысел перестройки теории информации, удовлетворяющей высказанному пожеланию, является статья Соломонова [160], опубликованная в 1964 г. Я пришел к аналогичной концепции, еще не зная работ Соломонова в 1963–1964 гг., и опубликовал первую заметку на эту тему [63] в начале 1965 г. (...) Замысел определения очень прост: энтропия $H(x|y)$ есть минимальная длина записанной в виде последовательности нулей и единиц «программы» $P$, которая позволяет построить объект $x$, имея в своем распоряжении объект $y$:

$$H(x|y) = \min_{A(P,y)=x} I(P).$$

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

(...) Предшествующее краткое изложение должно оправдать два общих тезиса:

1) основные понятия теории информации должны и могут быть обоснованы без помощи обращения к теории вероятностей и так, что понятия «энтропия» и «количество информации» оказываются применимы к индивидуальным объектам;

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

Ещё раньше, 23 апреля 1965 года, Колмогоров так формулировал свой замысел, выступая в Институте философии Академии наук СССР с докладом «Понятие „информация“ и основы теории вероятностей»:
Возникают последовательно такие проблемы:

1. Нельзя ли теорию информации (и понятие «количество информации» освободить от вероятностей?)

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

(цитируется по стенограмме, опубликованной в сборнике [68], с. 126).

Ещё большая путаница, чем с терминами, происходит с обозначениями. В оригинальной статье Колмогорова [63] сложность слова х обозначалась K(x), а в его же статье 1969 года [64] использовалось обозначение H(x) и для шенноновской энтропии, и для алгоритмической сложности. В других работах (например, у Ли и Витаньи) K(x) обозначает префиксную сложность, а для исходного понятия используется обозначение С(x). Чтобы избежать путаницы, мы вообще не будем использовать обозначение K(x), а писать KS(x) для исходного варианта сложности и KP(x) для префиксной сложности. Есть и другие варианты понятия сложности; монотонную сложность (в её наиболее естественной форме) мы будем обозначать КМ(x), а сложность разрешения — KR(x). (При этом некоторая путаница остаётся — у Ли и Витаньи монотонная сложность называется Km(x), а обозначение КМ(x) используется для логарифма априорной вероятности, которые мы обозначаем КА(x). Надеемся, это не собьёт читателя с толку.)

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

* * *

В начале 1980-х годов на механико-математическом факультете МГУ по инициативе А.Н. Колмогорова и при участии А.Л. Семёнова начал работу семинар «Сложность определений и сложность вычислений» (его наследником является «Колмогоровский семинар», работающий и поныне). Авторы книги глубоко признательны всем своим коллегам по этому семинару, без которых эта книга не могла бы возникнуть, в том числе А. Звонкину, Е. Асарину и В. Вовку (ученикам Колмогорова), С. Ф. Сопрунову, В. Выюгину, А. Ромащенко, М. Вялому, С. Тарасову, А. Чернову, М. Выюгину, С. Посицельскому, К. Макарычеву, Ю. Макарычеву, М. Ушакову, М. Устинову, С. Сальникову, А. Румянцеву, Д. Мусатову, В. Подольскому, И. Межирову, Ю. Притыкину, М. Раскину, А. Ходыреву, П. Карповичу, А. Минасяну, Е. Калининой, Г. Челнокову, И. Разенштейну, М. Андрееву, А. Савину, М. Дектярёву, А. Савчику, А. Кумку, В. Арзуманяну, А. Махлину.

Лягушку и её проекции (для обложки) нарисовала Марина Фейгельман; обложку оформила Ольга Лехтонен. Как всегда, мы благодарны (в частности, за помощь при подготовке оригинал-макета) Виктору Шувалову.

Во время написания книги авторы пользовались финансовой поддержкой фонда Сороса, шведского фонда STINT, Российского фонда фундаментальных исследований по грантам РФФИ 01-01-00493-а, 01-01-01028-а, 03-01-00475-а, 06-01-00122-а,
09-01-00709-а, 12-01-00864-а, CNRS, а также французского Agence National de Recherche по гранту ANR-08-EMER-008 NAFIT.

Книга не была бы написана, если бы не поддержка (научная и человеческая) зарубежных коллег, в том числе Брюно Бауэнса, Лорана Бьенвеню, Гарри Бюрмана, Сергея Воробьёва, Пола Витаньи, Питера Гача, Брюно Дюрана, Криса Калюде, Михала Коуцки, Леонида Левина, Вольфганга Меркле, Джо Миллера, Андре Ниса, Яна Раймана, Майкла Сипсера, Стива Симпсона, Денниса Хиршфельдта, Матьё Хойрупа и многих других.

Авторы благодарны судьбе за предоставленную возможность научного и человеческого общения с Андреем Мучником (1958–2007), выдающимся математиком, глубоким мыслителем и замечательным человеком, многие годы участвовавшим в работе колмогоровского семинара. Мы посвящаем наш скромный труд его памяти.

Н. К. Верещагин, В. А. Успенский, А. Шень

2 ноября 2012 г.
# О чём эта книга?

## Что такое колмогоровская сложность?

«На пальцах» это проще всего объяснить так. Существуют программы, которые сжимают файлы (для экономии места в архиве, без потери информации). Возможно, вы встречались с ними: наиболее распространённые называются zip, gzip, bzip2, compress, rar, arj (есть и другие).

Применив такую программу к некоторому файлу (с текстом, данными, программой), мы получаем его сжатую версию (которая, как правило, короче исходного файла). По ней можно восстановить исходный файл (с помощью парной программы-«декомпрессора»; часто сжатие и восстановление объединены в одну программу).

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

Это описание весьма приблизительно и нуждается в уточнениях — как технических, так и принципиальных. Начиём с технического: вместо файлов (последовательностей байтов) мы будем рассматривать двоичные слова (конечные последовательности битов, то есть нулей и единиц). Длиной такого слова называется число знаков (так что слово 1001, скажем, имеет длину 4, а пустое слово имеет длину 0).

Более существенны другие отличия:

* Мы рассматриваем только программы восстановления файла из архива и не рассматриваем программы сжатия файлов в архив. Точнее, назовём декомпрессором произвольный алгоритм (программу), который получает на вход двоичные слова и выдаёт на выход также двоичные слова. Если декомпрессор $D$ на входе $x$ даёт $y$, мы пишем $D(x) = y$ и говорим, что $x$ является описанием $y$ при данном $D$ (относительно данного $D$). Декомпрессоры мы также будем называть способами описания.

* Мы не требуем, чтобы декомпрессор был определён на всех словах. При некоторых $x$ вычисление $D(x)$ может зацикливаться (не останавливаться) и не давать результата. Мы также не накладываем никаких ограничений на время работы $D$: на некоторых входах программа $D$ может дать ответ лишь после очень долгой работы.
Используя терминологию теории вычислимых функций, можно сказать, что способ описания есть вычислимая функция из $\Xi$ в $\Xi$, где $\Xi$ — множество всех двоичных слов. Напомним, что с каждым алгоритмом $D$, входами и выходами которого являются двоичные слова, мы связываем функцию $d$, которая определена на слове $x$ тогда и только тогда, когда $D$ даёт результат на слове $x$; при этом значение $d(x)$ равно результату применения $D$ ко входу $x$. Функции $d$, получаемые таким образом из всевозможных алгоритмов $D$, называются вычислимыми функциями из $\Xi$ в $\Xi$. Обычно используют одну и ту же букву для обозначения алгоритма и вычисляемой им функции, и вместо $d(x)$ пишут $D(x)$. Мы также будем следовать этой традиции в тех случаях, когда это не вызывает путаницы.

Пусть фиксирован некоторый способ описания (декомпрессор) $D$. Для данного слова $x$ рассмотрим все его описания, то есть все слова $y$, для которых $D(y)$ определено и равно $x$. Длину самого короткого из них и называют колмогоровской сложностью слова $x$ при данном способе описания $D$:

$$KS_D(x) = \min\{l(y) \mid D(y) = x\}.$$

Здесь и далее $l(y)$ обозначает длину слова $y$. Индекс $D$ подчёркивает, что определение зависит от выбора способа $D$. Минимум пустого множества, как обычно, считается равным $+\infty$, так что $KS_D(x)$ бесконечно для тех $x$, которые не входят в область значений функции $D$ (не могут быть результатами декомпрессии, не имеют описаний).

Это определение кажется бессодержательным, поскольку для разных $D$ получаются разные определения, в том числе абсурдные. Например, если $D$ нигде не определён, то $KS_D$ всегда бесконечно. Если $D(y) = \Lambda$ (пустое слово) при всех $y$, то сложность пустого слова равна нулю (поскольку $D(\Lambda) = \Lambda$ и $l(\Lambda) = 0$), а сложность всех остальных слов бесконечна.

Более осмысленный пример: если программа-декомпрессор копирует вход на выход и $D(x) = x$ при всех $x$, то каждое слово имеет единственное описание (самого себя) и $KS_D(x) = l(x)$.

Естественно, для любого слова $x$ можно подобрать способ описания $D$, при котором $x$ имеет малую сложность. Достаточно положить $D(\Lambda) = x$, и тогда $KS_D(x)$ будет равно нулю. Можно также подобрать способ описания, благоприятствующий целому классу слов: например, для слов из одних нулей хорош такой способ описания:

$$D(\text{bin}(n)) = 000 \dots 000 \quad (n \text{ нулей}),$$

где $\text{bin}(n)$ — двоичная запись числа $n$. Легко проверить, что длина слова $\text{bin}(n)$ примерно равна $\log_2 n$ (не превосходит $\log_2 n + 1$). Мы получаем, что для построенного способа описания сложность слова из $n$ нулей близка к $\log_2 n$ (и много меньше длины слова, то есть $n$). Зато все другие слова (содержащие хотя бы одну единицу) имеют бесконечную сложность.

На первый взгляд кажется, что определение сложности настолько сильно зависит от выбора способа описания, что никакая общая теория невозможна.
## Оптимальные способы описания

Способ описания тем лучше, чем короче описания. Поэтому естественно дать такое определение: способ $D_1$ не хуже способа $D_2$, если

$$KS_{D_1}(x) \le KS_{D_2}(x) + c$$

при некотором $c$ и при всех $x$.

В этом определении требует пояснения константа $c$. Мы соглашаемся пренебрежать увеличением сложности не более чем на константу. Конечно, можно сказать, что это лишает определение практического смысла, так как константа $c$ может быть сколь угодно велика — однако без такого «огрубления» обойтись не удаётся.

Пример. Пусть даны два произвольных способа описания $D_1$ и $D_2$. Покажем, что существует способ описания $D$, который не хуже их обоих.

В самом деле, положим

$$D(0y) = D_1(y),$$

$$D(1y) = D_2(y).$$

Другими словами, первый бит описания мы воспринимаем как номер способа описания, а остальную часть — как собственно описание. Ясно, что если у является описанием $x$ при $D_1$ (или $D_2$), то $0y$ (соответственно $1y$) является описанием $x$ при $D$, и это описание всего лишь на один бит длиннее. Поэтому

$$KS_D(x) \le KS_{D_1}(x) + 1,$$

$$KS_D(x) \le KS_{D_2}(x) + 1$$

при всех $x$, так что способ $D$ не хуже обоих способов $D_1$ и $D_2$.

Этот приём используется на практике. Например, формат zip-архива предусматривает заголовок, в котором указывается номер используемого метода сжатия, а затем идёт сам сжатый файл. При этом использование $N$ различных способов описания приводит к тому, что начальные $log_2 N$ битов (или около того) приходится зарезервировать для указания используемого способа.

Несколько обобщив эту же идею, можно доказать такую теорему:

**Теорема 1** (Соломонова – Колмогорова). Существует способ описания $D$, который не хуже любого другого: для всякого способа описания $D'$ найдётся такая константа $c$, что

$$KS_D(x) \le KS_{D'}(x) + c$$

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

Способ описания, обладающий указанным в теореме свойством, называют **оптимальным**.

◀ Напомним, что по нашему определению способами описания являются вычислимые функции. Программы, их вычисляющие, можно считать двоичными словами. Будем при этом предполагать, что по программе можно определить, где она
кончается (такой способ записи по-английски называется self-delimiting; подходящего русского слова, пожалуй, нет, и мы будем называть такие программы «самоограниченными»). Формально говоря, самоограниченность означает, что никакая программа не может быть началом другой программы. Если выбранный способ записи программ не таков, то его можно модифицировать. Например, можно продублировать каждый знак в записи программы (заменив 0 на 00 и 1 на 11), а в конце программы добавить группу 01.

Теперь определим новый способ описания D, положив

$$D(py) = p(y),$$

где $p$ — произвольная программа (при выбранном способе записи), а $y$ — любое двоичное слово. Другими словами, $D$ читает слово слева направо, выделяя из него начало-программу. (Если таковой не оказывается, $D$ делает что угодно, например, зациливается.) Далее $D$ применяет найденную программу ($p$) к остатку входа ($y$) и выдаёт полученный результат. Самоограниченность гарантирует, что вход алгоритма $D$ однозначно разлагается на программу и остаток: если $py = p'y'$, то одна из программ $p, p'$ является началом другой, что противоречит самоограниченности.

Покажем, что $D$ не хуже любого другого способа описания $P$. Пусть $p$ — программа, вычисляющая функцию $P$, причём записанная в выбранной нами форме. Если слово $y$ является кратчайшим описанием слова $x$ относительно $P$, то $py$ будет описанием $x$ относительно $D$ (не обязательно кратчайшим). Поэтому при переходе от $P$ к $D$ длина описания увеличится не более чем на $l(p)$, и

$$KS_D(x) \le KS_P(x) + l(p).$$

Видно, что константа (то есть $l(p)$) зависит лишь от выбора способа описания $P$, но не от $x$. ►

По существу здесь используется тот же приём, что и в предыдущем примере, только вместо двух способов описания соединяются все мыслимые способы — каждый со своим префиксом. Именно так устроены так называемые «саморазархивирующиеся» архивы (self-extracting archives). Такой архив представляет собой исполняемый файл, в котором, однако, собственно программа занимает лишь небольшой начальный кусок. Эта программа загружается в память, после чего читает и разархивает остаток архива.

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

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

Фиксируем некоторый оптимальный способ описания $D$ и будем называть колмогоровской сложностью слова $x$ значение $KS_D(x)$. В обозначении $KS_D(x)$ будем опускать индекс $D$ и писать просто $KS(x)$.
Замена оптимального способа на другой оптимальный способ приводит к изменению сложности не более чем на константу: для любых оптимальных способов $D_1$ и $D_2$ найдётся такая константа $c(D_1, D_2)$, что

$$|KS_{D_1}(x) - KS_{D_2}(x)| \le c(D_1, D_2)$$

при всех х. Это неравенство записывают как

$$KS_{D_1}(x) = KS_{D_2}(x) + O(1),$$

понимая под $O(1)$ произвольную ограниченную функцию от х.

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

Каков же тогда смысл колмогоровской сложности, если ни про какое конкретное слово ничего нельзя сказать?

В защиту этого понятия можно сказать следующее. Свойства оптимального способа, построенного при доказательстве теоремы Колмогорова – Соломонова, зависят от использованного способа записи программ (то есть от выбора языка программирования). Два таких способа приводят к сложностям, отличающимся не более чем на константу, которая есть длина интерпретатора одного языка программирования, написанного на другом языке. Можно надеяться, что при естественном выборе языков эта константа будет измеряться тысячами или даже сотнями. Тем самым, если мы говорим о сложностях порядка сотен тысяч (скажем, для текста романа) или миллионов (скажем, для ДНК), то уже не так важно, какой именно язык программирования мы выбрали.

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

## Сложность и информация

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

Если слово х имеет сложность $k$, мы говорим, что х содержит $k$ битов информации. Естественно ожидать, что число битов информации в слове не превосходит
его длины, то есть что $KS(x) \le l(x)$. Так и оказывается (но только надо добавить константу, о чём мы уже говорили).

**Теорема 2.** Существует такая константа $c$, что

$$KS(x) \le l(x) + c$$

для любого слова х.

◄ Мы уже говорили, что если $P(y) = y$ при всех у, то $KS_P(x) = l(x)$. В силу оптимальности найдётся такое $c$, что

$$KS(x) \le KS_P(x) + c = l(x) + c$$

при всех х. ►

Утверждение этой теоремы обычно записывают так: $KS(x) \le l(x) + O(1)$. Из него вытекает, в частности, что колмогоровская сложность любого слова конечна (то есть что любое слово имеет описание).

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

**Теорема 3.** Для любого алгоритма $A$ существует такая константа $c$, что

$$KS(A(x)) \le KS(x) + c$$

для всех х, при которых $A(x)$ определено.

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

$$D'(p) = A(D(p))$$

$(D'$ применяет сначала $D$, а затем $A$). Если $p$ является описанием некоторого $x$ относительно $D$, причём $A(x)$ определено, то $p$ является описанием $A(x)$ относительно $D'$. Взяв в качестве $p$ кратчайшее описание $x$ относительно $D$, находим, что

$$KS_{D'}(A(x)) \le l(p) = KS_D(x) = KS(x),$$

а в силу оптимальности

$$KS(A(x)) \le KS_{D'}(A(x)) + c \le KS(x) + c$$

при некотором $c$ и при всех х, что и требовалось доказать. ►

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

Ещё один пример. Пусть х и у — два слова. Соединим их в одно, приписав у
к х справа. Сколько битов информации будет иметь полученное слово? Естествен-
но ожидать, что количество информации в нём не превосходит суммы количеств
информации в х и в у. И действительно это так, — правда, с некоторой поправкой.

**Теорема 4.** Существует такая константа $c$, что при любых $x$ и $y$ выполнено
неравенство

$$
KS(xy) \le KS(x) + 2 \log KS(x) + KS(y) + c.
$$

(Здесь и далее $\log$ обозначает двоичный логарифм, если иное основание не
указано явно.)

◀ Попробуем для начала доказать теорему без добавочного члена 2 log KS(x), её ослабляющего. Это естественно делать так. Пусть D — оптимальный способ описания, используемый при определении колмогоровской сложности. Рассмотрим новый способ описания D'. Именно, если D(p) = x и D(q) = y, будем считать pq описанием слова ху, то есть положим D'(pq) = ху. Тогда сложность слова ху относительно D' не превосходит длины слова pq, то есть l(p) + l(q). Если в качестве p и q взять кратчайшие описания, то получится KS<sub>D'(xy)</sub> ≤ KS<sub>D(x)</sub> + KS<sub>D(y)</sub>, и остаётся воспользоваться оптимальностью D и перейти от D' к D (при этом возникает константа c).

Что неверно в этом рассуждении? Дело в том, что определение D' некорректно:
мы полагаем D'(pq) = D(p)D(q), но D' не имеет средств разделить p и q. Вполне
может оказаться, что есть два разбиения слова на части, дающие разные результаты:
p₁q₁ = p₂q₂, но D(p₁)D(q₁) ≠ D(p₂)D(q₂).

Есть два способа исправить эту ошибку. Первый, который мы и применим,
состоит в том, чтобы перед словом *p* написать длину слова *p* в двоичной записи.
При этом в этой двоичной записи мы удвоим каждый бит, а после неё напишем 01,
чтобы алгоритм мог понять, где кончается двоичная запись и начинается само *p*.
Более точно, обозначим через *bin(k)* двоичную запись числа *k*, а через *x̄* результат
удвоения каждого бита в слове *x*. (Напимер, *bin(5) = 101*, а *bin(5) = 110011*.)
Теперь положим

$$
D'(\overline{\text{bin}(l(p))}01pq) = D(p)D(q).
$$

Это определение корректно: алгоритм D' сначала считает $\overline{\text{bin}(l(p))}$, пока цифры идут парами. Когда появляется группа 01, он определяет $l(p)$, затем отсчитывает $l(p)$ цифр и получает $p$. Остаток входа есть $q$, после чего уже можно вычислить $D(p)D(q)$.

Величина KS<sub>D'(xy)</sub> оценивается теперь числом 2l(bin(l(p))) + 2 + l(p) + l(q);
двоечная запись числа l(p) имеет длину не больше log l(p) + 1, поэтому D'-описа-
ние слова xy имеет длину не более 2 log l(p) + 4 + l(p) + l(q), откуда и вытекает
утверждение теоремы. ►

Альтернативный способ исправления допущенной ошибки состоит в том, чтобы
модифицировать определение сложности, потребовав, чтобы описания были само-
ограниченными (self-delimiting); мы обсуждаем его в главе 4.
Заметим также, что в теореме можно поменять местами $p$ и $q$ и доказать, что
$KS(xy) \le KS(x) + KS(y) + 2\log_2 KS(y) + c$.

Насколько неравенство теоремы 4 близко к равенству? Может ли $KS(xy)$ быть существенно меньше суммы $KS(x) + KS(y)$? В полном согласии с нашей интуицией это возможно, если $x$ и $y$ содержат много общего. Например, при $x = y$ мы имеем $KS(xy) = KS(xx) = KS(x) + O(1)$, поскольку хх алгоритмически получается из х и обратно (теорема 3).

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

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

если х и у — слова сложности не более $n$. Читается оно так: количество информации в ху равно количеству информации в у плюс количество новой (отсутствующей в у) информации в х.

Разность $KS(x) - KS(x|y)$ естественно назвать количеством информации об х в у: эта разность показывает, насколькоко знание слова у упрощает описание слова х.

Понятие условной сложности позволяет придать смысл вопросу о том, сколько новой информации в ДНК одного организма по сравнению с ДНК другого: если $d_1$ — двочное слово, кодирующее ДНК первого организма, а $d_2$ — двочное слово, кодирующее ДНК второго, то искомая величина есть $KS(d_1|d_2)$. Аналогичным образом можно спрашивать, какой процент информации был потерян при переводе романа на другой язык: в этом случае нас интересует отношение

$$KS(\text{оригинал} | \text{перевод}) / KS(\text{оригинал}).$$

Вопросы о количестве информации в различных объектах изучались и до алгоритмической теории информации, с помощью понятия шенноновской энтропии. Напомним её определение. Пусть случайная величина $\xi$ принимает $n$ значений с вероятностями $p_1, \dots, p_n$. Тогда её шенноновская энтропия определяется формулой

$$H(\xi) = \sum p_i (-\log_2 p_i).$$

Говорят, что исход, имеющий вероятность $p_i$, несёт в себе $(-\log_2 p_i) = \log_2(1/p_i)$ битов информации; тогда $H(\xi)$ можно интерпретировать как среднее количество информации в исходе случайной величины.

Чтобы применить понятие шенноновской энтропии, скажем, к оценке количества информации в данном тексте на русском языке, нужно включить этот текст в какой-то ансамбль текстов, считая его «типичным» значением некоторой случайной величины. Это имеет смысл для короткой поздравительной телеграммы, но для текста романа трудно вообразить себе подходящий ансамбль. Столь же сложно
сделать это при оценке количества информации в ДНК: если считать ансамблем
множество всех существовавших ДНК всех организмов, то число элементов это-
го ансамбля можно оценить сверху, скажем, числом $2^{1000}$, и получится абсурдно
малое число — меньше тысячи битов.

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

Сложность и случайность

Вернёмся к неравенству $KS(x) \le l(x) + O(1)$ (теорема 2). Для большинства
слов данной длины это неравенство близко к равенству. В самом деле, справедливо
такое утверждение:

**Теорема 5.** Для любого натурального числа $n$ количество слов $x$, для которых $KS(x) < n$, меньше $2^n$.

◀ Пусть $D$ — оптимальный способ описания, фиксированный при определении
колмогоровской сложности. Тогда все слова вида $D(y)$ при $l(y) < n$ (и только
они) имеют сложность менее $n$. А таких слов не больше, чем различных слов $y$,
имеющих длину меньше $n$, которых всего

$$1 + 2 + 4 + 8 + \dots + 2^{n-1} = 2^n - 1$$

штук (ведь слов длины $k$ ровно $2^k$). ►

Отсюда легко заключить, что доля слов сложности меньше $n-c$ среди всех
слов длины $n$ меньше $2^{n-c}/2^n = 2^{-c}$. Например, доля слов сложности менее 90
среди всех слов длины 100 меньше $2^{-10}$.

Таким образом, большинство слов несжимаемы или почти несжимаемы. Это
можно выразить и так: почти наверняка случайно взятое слово данной длины ока-
жется (почти) несжимаемым. Рассмотрим следующий мысленный (или даже ре-
альный) эксперимент. Бросим монету, скажем, 80000 раз и сделаем из результатов
бросаний файл длиной в 10000 байтов (8 битов образуют один байт). Можно сме-
ло держать пари, что ни один существовавший до момента бросания архиватор не
сумеет сжать этот файл более чем на 10 байтов. (В самом деле, вероятность этого
меньше $2^{-80}$ для каждого конкретного архиватора, а число различных архиваторов
не так уж велико.)

Вообще естественно считать случайными несжимаемые слова: случайность есть
отсутствие закономерностей, которые позволяют сжать слово. Конечно, чёткой гра-
ницы между случайными и неслучайными объектами провести нельзя. Глупо инте-
ресоваться, какие именно из восьми слов длины 3 (то есть из слов 000, 001, 010,
011, 100, 101, 110, 111) случайны, а какие нет. Другой пример: начав со «слу-
чайного» слова длиной 10000, будем заменять в нём по очереди единицы на нули.
В конце получится явно неслучайное слово (из одних нулей), но имеет ли смысл
спрашивать, в какой именно момент слово перестало быть случайным? Вряд ли.

Более естественно определить «дефект случайности» двоичного слова $x$ как раз-
ность $l(x) - KS(x)$. Используя эту терминологию, можно сказать так: теорема 2
утверждает, что дефект случайности почти что неотрицателен (не меньше некоторой константы), а теорема 5 гарантирует, что для случайно взятого слова данной длины *n* (мы считаем все слова длины *n* равновероятными) вероятность иметь дефект больше *d* не превосходит $1/2^d$.

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

Если мы хотим провести чёткую границу между случайными и неслучайными объектами, мы должны от конечных объектов перейти к бесконечным. Определение случайности для бесконечных последовательностей нулей и единиц, данное учеником Колмогорова шведским математиком П. Мартин-Лёфом, подробно обсуждается нами в главе 3. Впоследствии К. Шнорр и Л. А. Левин нашли критерий случайности в терминах сложности: последовательность случайна тогда и только тогда, когда дефект случайности её начальных отрезков ограничен. (Правда, нужно использовать другой вариант колмогоровской сложности, так называемую монотонную сложность.)

## Невычислимость KS и парадокс Берри

Прежде чем говорить о применениях колмогоровской сложности, скажем о пренятствии, с которым сталкивается любое такое применение. Увы, функция KS невычислима: не существует алгоритма, который по данному слову *x* определяет его колмогоровскую сложность. Более того, не существует никакой нетривиальной (неограниченной) вычислимой нижней оценки для KS, как показывает следующая теорема.

**Теорема 6.** Пусть $k$ — произвольная (не обязательно всюду определённая) вычислимая функция из $\Xi$ в $\mathbb{N}$. (Другими словами, вычисляющий её алгоритм применим к некоторым двоичным словам и даёт в качестве результатов натуральные числа.) Если $k$ является нижней оценкой для колмогоровской сложности (то есть $k(x) \le KS(x)$ для тех $x$, для которых $k(x)$ определено), то $k$ ограничена: все её значения не превосходят некоторой константы.

◄ Доказательство этой теоремы повторяет так называемый «парадокс Берри». Этот парадокс состоит в предложении рассмотреть

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

Эта фраза как раз содержит тринадцать слов и определяет то самое число, которое нельзя определить, так что получается противоречие.

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

Перейдём к формальному изложению. Пусть функция k является вычислимой нижней оценкой колмогоровской сложности. Рассмотрим функцию B(N), аргументом которой является натуральное число N, вычисляемую следующим алгоритмом: «Параллельно вычислять k(0), k(1), k(2)... до тех пор, пока не обнаружится некоторое х, для которого k(x) > N. Первое из таких х и будет результатом».

Предположим, что вопреки утверждению теоремы функция k не ограничена. Тогда функция B определена для всех N, и k(B(N)) > N по построению. По предположению k является нижней оценкой сложности, так что и KS(B(N)) > N. С другой стороны, B(N) эффективно получается по двоичной записи bin(N) числа N, поэтому

$$KS(B(N)) \le KS(\text{bin}(N)) + O(1) \le l(\text{bin}(N)) + O(1) \le \log_2 N + O(1)$$

(первое неравенство следует из теоремы 3, а второе — из теоремы 2; O(1) обозначает ограниченное слагаемое). Получается, что

$$N < KS(B(N)) \le \log_2 N + O(1),$$

что при больших N приводит к противоречию. ►

## Применения колмогоровской сложности

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

**Бритва Оккама.** Начнём с такого философского вопроса: что значит, что теория хорошо объясняет результаты эксперимента? Пусть имеется какой-то набор экспериментальных данных и разные теории, его объясняющие. Например, экспериментальными данными могут быть положения планет на небесной сфере. Их можно объяснять в духе Птолемея, рассматривая эпициклы и дифференты (и внося дополнительные поправки при необходимости), а можно ссылаться на законы современной механики. Как объяснить, чем современная теория лучше? Можно сказать так: современная теория позволяет вычислять положения планет с той же (и даже лучшей) точностью, имея меньше параметров. Условно говоря, достижение Кеплер а состоит в том, что он нашёл более короткое описание для экспериментальных данных. Совсем грубо можно сказать, что экспериментаторы получают двоичные слова, после чего теоретики ищут для этих слов короткие описания (и тем самым верхние оценки на сложность), и лучше тот теоретик, у которого описание короче (оценка меньше).
Этот подход называют иногда «бритвой Оккама» по имени философа, который говорил, что не следует множить сущности без необходимости. Насколько такое толкование одобрил бы сам Оккам, сказать трудно. (Иногда говорят о MDL-принципе, от слов Minimal Description Length.)

Можно использовать ту же идею в более практической ситуации. Представим себе, что мы собираемся автоматически читать надписи на конвертах и ищем правило, отделяющее изображения нулей от изображений единиц. (Будем считать, что изображение дано в виде матрицы битов, записанной как двоичное слово.) У нас есть несколько тысяч образцов — картинок, про которые мы знаем, нуль это или единица. По этим образцам мы хотим сформулировать какое-то разумное разделяющее правило. Что означает в этом контексте слово «разумное»? Если мы просто перечислим все образцы того или другого типа, получится вполне действующее правило — действующее до тех пор, пока нам не принесут новый образец, — но оно будет слишком длинным. Естественно считать, что разумное правило должно иметь короткое описание, то есть по возможности меньшую колмогоровскую сложность.

**Обоснование теории вероятностей.** Речь идёт не о самой математической теории вероятностей (которую можно рассматривать как часть теории меры и которая не требует никакого особого обоснования), а о механизме применения теории вероятностей. Представим себе, что мы бросаем монету тысячу раз (или, более realistically, проверяем качество специального электронного датчика случайных чисел, дающего последовательность нулей и единиц). Если получится последовательность из тысячи нулей (или последовательность 0101010101...), то мы сочтём, что датчик плох. Но, собственно говоря, почему?

Часто говорят, что вероятность случайного появления тысячи нулей исчезающе мала (равна $2^{-1000}$), если монета честная, и потому гипотеза честной монеты отвергается. С другой стороны, мы же не всегда бракуем датчик: возможна такая последовательность $\alpha$ из тысячи нулей и единиц, которая не вызовет у нас претензий к датчику. Заметим теперь, что вероятность появления последовательности $\alpha$ при бросании честной монеты также равна $2^{-1000}$ — так почему же мы в этом случае не возмущаемся? В чём разница между последовательностью из тысячи нулей и последовательностью $\alpha$? Естественно усмотреть эту разницу в том, что последовательность из тысячи нулей имеет меньшую сложность, чем $\alpha$.

**Доказательство теорем теории вероятностей.** Рассмотрим в качестве примера усиленный закон больших чисел. Он утверждает, что почти все бесконечные последовательности нулей и единиц (по равномерной бернуллиевой мере, соответствующей независимым бросаниям симметричной монеты) имеют предел частоты единиц, равный $1/2$.

Более подробно. Обозначим через $\Omega$ множество всех бесконечных последовательностей нулей и единиц. На этом множестве вводится равномерная бернуллиева мера. Это делается так: для каждого двоичного слова $x$ рассмотрим множество $\Omega_x$ всех бесконечных продолжений этого слова. (Например, $\Omega_\Lambda = \Omega$.) Меру множества $\Omega_x$ положим равной $2^{-l(x)}$. (Например, мера множества $\Omega_{01}$, состоящего из последовательностей, начинающихся на 01, равна $1/4$.)
Для каждой последовательности $\omega = \omega_0\omega_1\omega_2...$ рассмотрим предел частоты единиц в начальных отрезках, то есть предел

$$ \lim_{n \to \infty} \frac{\omega_0 + \omega_1 + \dots + \omega_{n-1}}{n} $$

Говорят, что последовательность удовлетворяет усиленному закону больших чисел, если этот предел существует и равен 1/2. Например, последовательность 010101... (с периодом 2) ему удовлетворяет, а последовательность 011011011... (с периодом 3) — нет.

Усиленный закон больших чисел гласит, что множество последовательностей, не удовлетворяющих этому закону, имеет меру нуль. Напомним: множество $A \subset \Omega$ имеет меру нуль, если для всякого $\varepsilon > 0$ можно указать последовательность слов $x_0, x_1, x_2, ...$, для которой

$$ A \subset \Omega_{x_0} \cup \Omega_{x_1} \cup \Omega_{x_2} \cup \dots $$

и сумма ряда

$$ 2^{-l(x_0)} + 2^{-l(x_1)} + 2^{-l(x_2)} + \dots $$

(состоящего из мер множеств $\Omega_{x_i}$) не превосходит $\varepsilon$.

Усиленный закон больших чисел можно доказать с помощью алгоритмической теории информации, используя понятие случайной по Мартин-Лёфу последовательности (о котором мы уже упоминали). Доказательство (см. раздел 8.4) состоит из двух частей. Сначала мы доказываем, что всякая случайная по Мартин-Лёфу последовательность удовлетворяет этому закону. Это можно сделать с использованием критерия случайности Левина-Шнорра (если предел частот не существует или не равен 1/2, то некоторые начальные отрезки имеют сложность меньше, чем должно быть для случайной последовательности; см. теорему 90 на с. 167) Вторая часть доказательства носит общий характер и не зависит от того, какой закон теории вероятностей рассматривается. Мы доказываем, что множество неслучайных (по Мартин-Лёфу) последовательностей имеет меру нуль. После этого мы говорим, что множество последовательностей, не удовлетворяющих закону больших чисел, содержится в множестве меры нуль и потому само имеет меру нуль.

Понятие случайной последовательности имеет и самостоятельный философский интерес. В начале ХХ века Рихард фон Мизес предложил положить это понятие (он называл его по-немецки Kollektiv) в основу теории вероятностей (в то время ещё не было идеи рассматривать теорию вероятностей в рамках теории меры). Подход Мизеса к определению случайной последовательности (он считал главным свойством так называемую «устойчивость частот») и его современные варианты мы рассматриваем в главе 9.

**Нижние оценки в теории вычислительной сложности.** Колмогоровская сложность оказалась полезным техническим средством для доказательства нижних оценок в теории сложности вычислений. Мы опишем её применение на модельном примере.

Рассмотрим следующую задачу: на ленте одноленточной машины Тьюринга написано некоторое слово $x$ длины $n$. Требуется скопировать это слово справа от
него, то есть получить на ленте слово хх. С середины 1960-х годов известно, что это требует времени, пропорционального $n^2$. Точнее говоря, можно доказать, что для любой машины Тьюринга $M$, решающей эту задачу для всех слов $x$, найдётся такое число $\varepsilon > 0$, что для любого $n$ существует слово $x$ длины $n$, копирование которого (с помощью $M$) длится дольше $\varepsilon n^2$.

Имеется следующее интуитивное объяснение этого факта. Машина Тьюринга имеет ограниченное число внутренних состояний, то есть может запомнить (помимо ленты) ограниченное число битов. Кроме того, скорость передвижения её по ленте ограничена: за один шаг она может сместиться не более чем на одну клетку. Следовательно, скорость переноса информации с помощью машины Тьюринга (единица измерения: бит · клетка/шаг) ограничена константой, зависящей от числа состояний машины (пропорциональной логарифму числа состояний). Копирование слова $x$ длины $n$ требует переноса $n$ битов информации, содержащихся в слове $x$, на расстояние в $n$ клеток, и потому число шагов пропорционально $n^2$.

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

Мы рассмотрим этот пример подробнее в разделе 8.2 (с. 262).

**Комбинаторный смысл утверждений о сложности.** Мы приведём один пример такого рода (подробнее см. главу 10, с. 349). Существует неравенство для сложностей трёх слов и их комбинаций:

$$2 \text{KS}(xyz) \le \text{KS}(xy) + \text{KS}(xz) + \text{KS}(yz) + O(\log n)$$

для любых трёх слов $x, y, z$ длины не больше $n$.

Оказывается, что это неравенство имеет естественные интерпретации, в которых о сложности уже ничего не говорится. В частности, из него можно вывести такой геометрический факт [52].

Пусть имеется тело в трёхмерном пространстве с перпендикулярными осями $OX, OY$ и $OZ$, имеющее объём $V$. Рассмотрим три его ортогональные проекции на плоскости $OXY, OXZ$ и $OYZ$. Пусть $S_{xy}, S_{xz}$ и $S_{yz}$ — площади этих проекций. Тогда имеет место такое неравенство:

$$V^2 \le S_{xy} \cdot S_{xz} \cdot S_{yz}.$$

А вот алгебраическое следствие того же неравенства: для произвольной группы $G$ и её подгруппы $X, Y$ и $Z$ справедливо неравенство

$$|X \cap Y \cap Z|^2 \ge \frac{|X \cap Y| \cdot |X \cap Z| \cdot |Y \cap Z|}{|G|}$$

(где $|H|$ обозначает число элементов в группе $H$).

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

Будем считать, что в нашей теории можно записать утверждение $KS(x) > n$ для любого двоичного слова $x$ и любого натурального числа $n$. (Утверждение $KS(x) > n$, построенное для данного слова $x$ и для данного числа $n$, гласит, что выбранный декомпрессор $D$ не даёт $x$ ни на каком входе длины не более $n$; его легко записать в формальной арифметике и тем более в теории множеств.)

Будем перебирать все формальные выводы и искать среди них доказательства утверждений вида $KS(x) > n$ (для всевозможных слов $x$ и чисел $n$). Найдя такое утверждение, мы смотрим, каково в нём значение $n$ (чем оно больше, тем лучше). Если $n$ превосходит прежний рекорд, то мы запоминаем в таблице рекордов это $n$ и соответствующее ему значение $x_n$. Теперь есть две возможности. Либо таблица рекордов будет расти неограниченно, либо начиная с некоторого времени новых рекордов не будет и какое-то утверждение $KS(X) > N$ так и останется непревзойдённым. Во втором случае целый класс истинных утверждений, а именно, все истинные утверждения вида $KS(x) > n$ при $n > N$, являются недоказуемыми. (Напомним, что по теореме 5 такие истинные утверждения существуют, и их бесконечно много.)

В первом случае мы получим вычислимую последовательность слов $x_0, x_1, x_2, ...$ и чисел $n_0 < n_1 < n_2 < ...$, для которых доказуемы утверждения $KS(x_i) > n_i$. Мы предполагаем, что в теории доказуемы лишь истинные утверждения, так что и вправду $KS(x_i) > n_i$. Выбросив из этой последовательности повторения слов, можно считать, что все $x_i$ различны (каждое слово может встречаться лишь конечное число раз, так как $n_i \to \infty$ при $i \to \infty$). После этого вычислимая функция $k$, для которой $k(x_i) = n_i$, будет неограниченной нижней оценкой для колмогоровской сложности, что противоречит теореме 6.
# 1. Простая колмогоровская сложность

## 1.1. Определение и основные свойства

Напомним (данное во введении) определение колмогоровской сложности. Этот вариант определения сложности был предложен в статье Колмогорова [63]. Чтобы отличить его от других, определённую таким образом сложность называют **простой**, или **обыкновенной**, колмогоровской сложностью. Другие виды сложности (префиксная, монотонная) будут рассматриваться, начиная с главы 4, так что пока мы можем говорить о колмогоровской сложности (без уточняющего эпитета), не опасаясь путаницы.

Способом описания, или декомпрессором, мы называли произвольное вычисление частичное отображение $D$ из множества двоичных слов $\Xi$ в себя. (Вычислительность отображения $D$ означает, что есть алгоритм, который применим к словам из области определения отображения $D$ и только к ним; результат применения алгоритма к слову $x$ есть $D(x)$.) Если $D(y) = x$, говорят, что у является описанием $x$ при способе описания $D$.

Для каждого способа описания $D$ мы определяем сложность относительно этого способа описания, полагая её равной длине кратчайшего описания:

$$KS_D(x) = \min\{l(y) \mid D(y) = x\}.$$

При этом минимум пустого множества считается равным $+\infty$.

Говорят, что способ описания $D_1$ не хуже способа описания $D_2$, если найдётся такая константа $c$, что $KS_{D_1}(x) \le KS_{D_2}(x) + c$ для всех слов $x$. (Краткая запись: $KS_{D_1}(x) \le KS_{D_2}(x) + O(1)$.)

Способ описания называют **оптимальным**, если он не хуже любого другого способа описания. Теорема Колмогорова – Соломонова (с. 11) утверждает, что существуют оптимальные способы описания. Её доказательство (подробно изложенное во введении) проходит так. Выберем какой-либо универсальный язык программирования. Пусть $U$ — интерпретатор этого языка: $U(p, x)$ есть результат работы программы $p$ на входе $x$ (программа и вход — двоичные слова). Далее мы полагаем

$$D(\hat{p}x) = U(p, x),$$

где вычислимое отображение $p \mapsto \hat{p}$ выбрано так, чтобы по слову $\hat{p}$ можно было определить $p$, а также место, где $\hat{p}$ кончается. (В этом случае слово $\hat{p}$ не может быть началом слова $\hat{q}$ при $p \ne q$, и это свойство гарантирует, что $D$ корректно определено.) Тогда для любого способа описания $D'$ имеем

$$KS_{D'}(x) \le KS_D(x) + l(\hat{p}),$$
где $p$ — программа, соответствующая способу описания $D'$. (В самом деле, если у есть описание $x$ относительно $D'$, то $\hat{p}$ есть описание $x$ относительно $D$.)

Мы фиксируем некоторый оптимальный способ описания и сложность слова $x$ относительно этого способа описания обозначаем $KS(x)$ (без индекса). В первой статье Колмогорова [63] использовалось обозначение $K(x)$; во второй [64] та же величина обозначалась $H(x)$. Сейчас в англоязычной литературе наиболее часто используется обозначение $C(x)$.

Сравнение оптимального способа описания с тождественным (при котором слово является своим собственным описанием) показывает, что $KS(x) \le l(x) + O(1)$ (с. 14).

Сравнивая оптимальный способ описания $D$ со способом $y \mapsto A(D(y))$, где $A$ — произвольная вычислимая функция, находим, что $KS(A(x)) \le KS(x) + O(1)$ (не-воздрастание сложности при алгоритмических преобразованиях, с. 14).

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

Поясним сказанное на примере натуральных чисел. Натуральное число $n$ можно записать в двоичной системе — получится двоичное слово. Можно выбрать и другой способ представления натуральных чисел двоичными словами. Например, можно записать двоичные слова подряд (в порядке возрастания длин и в лексикографическом порядке для слов одной длины):

А, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, ...

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

Заметим, что колмогоровская сложность и так определена с точностью до огра- ниченного слагаемого, так что дополнительный произвол такого рода нам не стра- шен.

Отметим ещё, что двоичная запись натурального числа $n$ имеет длину $\log n + O(1)$, и потому его сложность также не превосходит $\log n + O(1)$. (Здесь, напо- мним, $\log$ обозначает двоичный логарифм.)

Другое простое применение свойства невозрастания сложности при алгоритми- ческих преобразованиях: покажем, что добавление или удаление нуля или едини- цы в конце слова меняет его сложность не более чем на константу. В самом деле,
функции $x \mapsto x0$, $x \mapsto x1$, а также функция, удаляющая последний бит слова, вычислимы.

Разумеется, то же самое верно для добавления бита в начале слова. Но изменение бита в произвольном месте слова может изменить его сложность более чем на константу. Например, если слово состоит из $2^n$ нулей, то его сложность не больше $KS(n) + O(1) \le \log n + O(1)$. Заменив $k$-й нуль на единицу (при $k = 1, 2, \dots, 2^n$), мы получим $2^n$ различных слов, поэтому сложность хотя бы одного из них не меньше $n$. (Как мы видели на с. 17, число слов сложности меньше $n$ не превосходит числа всех описаний длины меньше $n$ и потому меньше $2^n$.)

Прибавление единицы к натуральному числу $n$ меняет $KS(n)$ не более чем на константу, так что сложность, рассматриваемая как функция натурального аргумента, обладает «свойством Липшица» (это значит, что $|KS(m) - KS(n)| \le c|m - n|$ для некоторого $c$ и любых натуральных чисел $m$ и $n$).

1. Докажите более сильное неравенство: $|KS(m) - KS(n)| \le |m - n| + c$ (для некоторого $c$ и для всех $m, n \in \mathbb{N}$) и даже $|KS(m) - KS(n)| \le 2\log|m - n| + c$ (при $m \ne n$).

Вернёмся к утверждению о том, что число слов $x$ с $KS(x) < n$ меньше $2^n$. Заметим, что в этом утверждении нет никаких констант (что несколько необычно). Но всё равно зависимость от выбора оптимального способа описания в нём неявно присутствует: если мы заменим один способ описания на другой, то количество слов сложности меньше $n$ по-прежнему будет меньше $2^n$, но это будут другие слова!

2. Покажите, что число слов сложности меньше $n$ заключено между $2^{n-c}$ и $2^n$ (при некотором $c$ и всех $n$). [Указание: о верхней оценке $2^n$ мы уже говорили, а нижняя вытекает из того, что $KS(x) \le l(x) + c$ при некотором $c$ и потому все слова длины меньше $n-c$ имеют сложность меньше $n$.]

Покажите, что число слов сложности ровно $n$ не превосходит $2^n$, но для некоторых способов описания может быть сильно меньше (например, таких слов может не быть вовсе для бесконечно многих $n$). [Указание: модифицируем оптимальный способ описания, добавив 0 или 11 ко всем описаниям и сделав их длину чётной.]

3. Покажите, что среднее арифметическое сложностей всех слов длины $n$ равно $n + O(1)$. [Указание: ряд $\sum k/2^k$ сходится, а доля слов длины $n$, сложность которых равна $n-k$, равна примерно $2^{-k}$.]

Продолжая эту тему (связь оценок сложности с оценками количества), докажем такое важное утверждение:

**Теорема 7.** (а) Множества $S_n = \{x | KS(x) < n\}$ образуют перечислимое семейство, причём $|S_n| < 2^n$ при всех $n$. (Здесь $|S_n|$ — число элементов в множестве $S_n$.)

(б) Если $V_n$ ($n = 0, 1, 2, \dots$) — перечислимое семейство множеств, причём $|V_n| < 2^n$ при всех $n$, то найдётся такое $c$, что $KS(x) < n + c$ для любого $n$ и для любого $x \in V_n$.

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

Например, множество всех $n$, при которых в десятичном разложении $\sqrt{2}$ встречается ровно $n$ девяток подряд, перечислимо. Перечисляющий его алгоритм таков: вычисляем последовательные цифры числа $\sqrt{2}$; как только встретилась группа из $n$ девяток подряд, окружённая не-девятками, печатаем $n$ и продолжаем работу.

Перечислимость семейства множеств $V_n$ означает (по определению), что множество пар $\{\langle n, x \rangle | x \in V_n\}$ перечислимо. Это, вообще говоря, более сильное свойство, чем перечислимость каждого из множеств $V_n$. Если семейство перечислимо, то каждое из множеств перечислимо (отбираем пары с данным первым членом), но обратное, вообще говоря, неверно. Например, если все множества $V_n$ конечны (как у нас), то все они перечислимы, но это не гарантирует перечислимости семейства. (Можно проверить, что перечислимость семейства равносильна возможности по $n$ алгоритмически получать алгоритм, перечисляющий $V_n$..) О понятии перечислимого множества можно прочесть в любом учебнике по теории вычислимости, например, в [175].

Покажем, что множество пар

$$ \{\langle n, x \rangle | x \in S_n\} = \{\langle n, x \rangle | KS(x) < n\} $$

(первыми компонентами пар являются натуральные числа, вторыми — двоичные слова) перечислимо. В самом деле, пусть $D$ — оптимальный способ описания, использованный при определении $KS$. Будем параллельно запускать $D$ на всех двоичных словах, делая всё больше шагов на каждом слове и вовлекая всё новые и новые слова. (Напимер, на $k$-м этапе мы проводим по $k$ шагов вычисления для первых $k$ двоичных слов.) Как только одно из проводимых вычислений заканчивается и обнаруживается, что $D(y) = x$, перечисляющий алгоритм выдаёт на выход пару $\langle l(y) + 1, x \rangle$ (в самом деле, мы установили, что сложность слова $x$ меньше $l(y) + 1$, поскольку это слово имеет описание $y$). После этого он выдаёт пары $\langle l(y) + 2, x \rangle$, $\langle l(y) + 3, x \rangle$... (чередуя их с другими парами, которые нужно выдать).

Для знакомых с теорией алгоритмов всё это объяснение можно заменить одной строчкой

$$ KS(x) < n \Leftrightarrow \exists y (l(y) < n \land D(y) = x) $$

(множество в правой части перечислимо, так как график вычислимой функции $D$ перечислим, а пересечение и проекция сохраняют перечислимость).

Более содержательно обратное утверждение. Пусть имеется перечислимое семейство конечных перечислимых множеств $V_n$, причём $|V_n| < 2^n$. Построим способ описания $D_V$ следующим образом. Зарезервируем слова длины $n$ для описания элементов множества $V_n$. Именно, будем считать $k$-е в лексикографическом порядке
слово длины $n$ описанием $k$-го элемента множества $V_n$ (в порядке появления элементов множества $V_n$ при перечислении). Поскольку $|V_n| < 2^n$, слов длины $n$ хватит (естественно, при повторном появлении слова в перечислении мы не выделяем нового описания). Построенный таким образом способ описания $D_V$ будет вычитимым. В самом деле, чтобы вычислить $D_V(y)$, мы находим порядковый номер слова $y$ среди всех слов длины $l(y)$. Пусть он равен $k$. После этого мы запускаем алгоритм, перечисляющий множество пар $(n, x)$, у которых $x \in V_n$, и ожидаем появления $k$ различных пар, первая компонента которых равна $l(y)$. Вторая компонента последней из них и будет $D_V(y)$.

По определению $KS_{D_V}(x) \le n$ для любого $x \in V_n$. Сравнивая способ описания $D_V$ с оптимальным, находим, что $KS(x) < n + c$ для любого $x \in V_n$. Теорема 7 доказана. ►

Интуитивный смысл доказанной только что теоремы можно объяснить так: она говорит, что утверждения «объектов определённого вида мало» (меньше $2^i$) и «объекты этого вида просты» (имеют сложность меньше $i$) равносильны, если мы рассматриваем перечислимые семейства и измеряем сложность с точностью до аддитивной константы (а число элементов — с точностью до мультипликативной).

Эту же теорему можно сформулировать в других терминах. Пусть функция $f(x)$ определена на всех двоичных словах и принимает в качестве значений натуральные числа, а также специальный символ $+\infty$. Функция $f$ называется перечислимой сверху, если существуют вычислимая функция $(x, k) \mapsto F(x, k)$, определённая для всех слов $x$ и всех натуральных чисел $k$, для которой

$$F(x, 0) \geq F(x, 1) \geq F(x, 2) \geq \dots$$

и

$$f(x) = \lim_{k \to \infty} F(x, k).$$

при всех $x$. Значениями функции $F$ также могут быть натуральные числа и $+\infty$. Наши требования гарантируют, что при любом $k$ значение $F(x, k)$ является верхней оценкой для $f(x)$. Эта оценка уточняется с ростом $k$. При каждом $x$ эта оценка в какой-то момент становится точной, но когда именно, мы можем не знать (если есть алгоритм, указывающий этот момент, то функция $f$ вычислима).

Всякая вычислимая функция перечислима сверху.

Несложно проверить, что функция $f$ перечислима сверху тогда и только тогда, когда множество

$$G_f = \{ (x, n) \mid f(x) < n \},$$

называемое иногда «надграфиком» функции $f$, перечислимо. (Это объясняет несколько странное название «перечислимая сверху».)

Убедимся в этом. Если функция $f$ перечислима сверху и $F$ — соответствующая функция двух аргументов, то

$$f(x) < n \Leftrightarrow \exists k F(x, k) < n.$$

Поэтому, вычисляя $F(x, k)$ параллельно для всех $x$ и $k$, мы можем перечислять множество $G_f$. Обратно, если мы можем перечислять множество $G_f$, то $F(x, k)$
можно определить как наилучшую верхнюю оценку для $f$, которую мы можем дать после $k$ шагов перечисления множества $G_f$. (В ходе этого перечисления мы устанавливаем, что $f(x) < n$ для некоторых $x$ и $n$, тем самым получая верхние оценки для значения $f(x)$ при некоторых $x$; для остальных $x$ мы полагаем $F(x, k) = +\infty$.)

Теперь мы можем переформулировать только что доказанную теорему 7 следующим образом:

**Теорема 8.** (а) Функция $KS$ перечислила сверху, причём $|\{x | KS(x) < n\}| < 2^n$ при всех $n$.

(б) Если функция $K$ перечислила сверху $|\{x | K(x) < n\}| < 2^n$ при всех $n$, то найдётся такое $c$, что $KS(x) < K(x) + c$ для всех $x$.

Отметим, что в пункте (б) этой теоремы можно ослабить оценку и написать, что $|\{x | K(x) < n\}| = O(2^n)$.

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

Можно сделать ещё один шаг и избавиться от требованиям минимальности, получив следующее «аксиоматическое» определение колмогоровской сложности [150].

**Теорема 9.** Пусть $K$ — функция с натуральными значениями, определённая на всех двоичных словах. Пусть при этом:

(а) $K$ перечислила сверху; [аксиома перечислимости]

(б) для любой вычислимой функции $A$, аргументами и значениями которой являются двоичные слова, выполнено неравенство $K(A(x)) \le K(x) + c$ при котором $c$ и всех $x$, для которых $A(x)$ определено; [аксиома невозрастания сложности]

(в) количество слов $x$, для которых $K(x) < n$, заключено между $2^{n-c_1}$ и $2^{n+c_2}$ при некоторых $c_1, c_2$ и при всех $n$. [аксиома калибровки]

Тогда $K(x) = KS(x) + O(1)$ (другими словами, разность $K(x) - KS(x)$ огражена с обеих сторон константами, не зависящими от $x$).

▲ Предыдущая теорема показывает, что $KS(x) \le K(x) + O(1)$. Остаётся доказать, что $K(x) \le KS(x) + O(1)$.

**Лемма 1.** Существует константа $c$ и вычислимая последовательность коечных множеств двоичных слов

$$M_0 \subset M_1 \subset M_2 \subset \dots$$

(говоря о вычислимости, мы имеем в виду, что множество задаётся списком своих элементов), в которой $M_i$ содержит ровно $2^i$ слов и $K(x) \le i + c$ для всех элементов $x \in M_i$ (при любом $i$).

**Доказательство.** Свойство (в) функции $K$ гарантирует, что множество $A_i = \{x | K(x) < i + c\}$ содержит не менее $2^i$ элементов (при некотором $c$, например $c = c_1$, и при всех $i$). Свойство (а) гарантирует, что семейство множеств $A_i$ перечислимо. Если оставить от множества $A_i$ только $2^i$ элементов, которые появляются при перечислении первыми, то получится множество $B_i$, которое содержит ровно $2^i$ элементов. При этом список элементов множества $B_i$ можно получить алгоритмически по $i$ (дождавшись появления $2^i$ элементов при перечислении множества $A_i$ —
наши предположения гарантируют, что это обязательно произойдёт). Правда, множества $B_i$ не обязаны возрастать с ростом $i$, но это можно исправить, определив $M_i$ индуктивно. Именно, $M_0$ полагаем равным $B_0$, а $M_{i+1}$ есть объединение $M_i$ с $2^i$ элементами $B_{i+1}$, не входящими в $M_i$. Лемма 1 доказана.

**Лемма 2.** Существует константа $c$, при которой $K(x) \le l(x) + c$ для любого слова $x$ (напомним, $l(x)$ — длина слова $x$).

**Доказательство.** Рассмотрим множества $M_i$ из предыдущей леммы. Рассмотрим вычислимую функцию $A$, которая определена на объединении всех множеств $M_i$ и отображает $M_{i+1} \setminus M_i$ на множество всех слов длины $i$. (В множестве $M_{i+1} \setminus M_i$ как раз $2^i$ слов, так что его можно взаимно однозначно отобразить на слова длины $i$.) По условию (б) мы знаем, что $K(A(y)) \le K(y) + c'$ при некотором $c'$ и всех $x$. Применяя это свойство для $y \in M_{i+1} \setminus M_i$, находим, что $K(x) < i + c$ для любого слова $x$ длины $i$ (при всех $i$ и при некотором $c$, не зависящем от $i$). Лемма 2 доказана.

Теперь уже легко завершить доказательство теоремы. Пусть $D$ — оптимальный способ описания. Если $p$ — кратчайшее описание для слова $x$, то $K(x) = K(D(p)) \le K(p) + O(1) \le l(p) + O(1) = KS(x) + O(1)$. (Таким образом, мы дважды использовали свойство (б): один раз при доказательстве леммы 2 и второй раз только что, применяя его к вычислимой функции $D$.) ►

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

**5.** (Продолжение) Сформулируйте и докажите аналогичное утверждение для $n$-буквенного алфавита.

**6.** Пусть $f: N \to N$ — всюду определённая вычислимая возрастающая функция, причём $\liminf f(n+1)/f(n) > 1$. Докажите, что если $A_n$ — перечислимое семейство конечных множеств, причём число элементов в $A_n$ не превосходит $f(n)$ при всех $n$, то найдётся такая константа $c$, что $KS(x) \le \log f(n) + c$ для любого $n$ и для любого $x \in A_n$.

**7.** Покажите, что при некотором $c$ для всякого слова $x$ любой длины $n$ существует слово у той же длины, отличающееся от $x$ не более чем в одной позиции, для которого $KS(y) \le n - \log n + c$. [Указание. При $n = 2^k - 1$ можно взять в качестве у кодовое слово кода Хемминга (см, например, [133]). Если число $n$ не имеет вида $2^k - 1$, применяем те же рассуждения к части $x'$ слова $x$, имеющей удобную (и достаточно большую) длину.]

## 1.2. Алгоритмические свойства

Как мы видели, функция $KS$ является перечислимой сверху, но не является вычислимой и даже не имеет вычислимых неограниченных нижних оценок (теорема 6, с. 18).
Заметим, что из этого вытекает, что никакой оптимальный способ описания не является всюду определённым (имеются слова, не являющиеся описаниями). В самом деле, если бы оптимальный способ описания $D$ был всюду определён, то мы могли бы вычислить $KS_D(x)$, просто перепробав все описания в порядке возрастания длин (до нахождения кратчайшего).

При этом возникает следующий любопытный парадокс. С точки зрения оптимальности наличие слов, не являющихся описаниями, явно невыгодно. В самом деле, если $D(y)$ не определено, можно рассмотреть другой способ описания $D'$, для которого $D'(y)$ равно некоторому слову $z$, а в остальном $D'$ совпадает с $D$. При замене $D$ на $D'$ сложность слова $z$ может уменьшиться, а сложность остальных слов не изменится. Тем не менее для оптимального способа описания всегда есть слова, на которых он не определён!

Формального противоречия тут нет (такое доопределение сохраняет вычислительность, лишь если его сделать в одной точке или в конечном числе точек), но наблюдение это любопытно (его сделал Ю. И. Манин в своей книжке «Вычислимое и невычислимое» [96] — той самой, в которой он обсуждал возможности квантовых компьютеров задолго до того, как их начали изучать).

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

Тем самым мы построили алгоритм с неразрешимой областью определения (это — центральный факт теории алгоритмов, см., например, [175]).

Вообще понятие колмогоровской сложности представляет интерес с точки зрения общей теории алгоритмов. В последние годы изучение этих связей дало множество интересных (и трудных) результатов, о которых можно прочесть в [127, 37]. Мы же рассмотрим только два вопроса такого рода — о простоте множества простых слов и о сложности больших чисел.

### 1.2.1. Простые слова и простые множества

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

**Определение.** Перечислимое множество $A$ является простым (в смысле Поста), если его дополнение бесконечно, но не содержит бесконечного перечислимого подмножества.

Будем называть слово $x$ «простым», если $KS(x) < l(x)/2$.
**Теорема 10.** Множество всех «простых» слов является простым в смысле Поста.

◀ Множество $S$ всех «простых» слов перечислимо, поскольку функция $KS$ вычислима сверху (используя всё более и более точные верхние оценки, мы рано или поздно сможем обнаружить и перечислить любое «простое» слово).

Как мы знаем, число слов сложности менее $n/2$ не превосходит $2^{n/2}$. Поэтому среди слов длины $n$ «простые» слова составляют (ничтожное) меньшинство, так что дополнение к множеству $S$ бесконечно.

Может ли дополнение к множеству $S$ иметь бесконечное перечислимое подмножество? Нет. Предположим, что такое подмножество $C$ существует, и покажем, что функция $KS$ имеет неограниченную вычислимую нижнюю оценку. В самом деле, чтобы найти слово сложности больше $t$, достаточно перечислять множество $C$, пока не обнаружится слово $c_t$ длины больше $2t$. Такое слово найдётся, поскольку $C$ бесконечно; это слово должно иметь сложность больше $t$, иначе оно было бы «простым». Можно считать, что все $c_t$ различны (отбраковывая уже использованные слова). Тогда функция, равная $t$ на слове $c_t$, будет вычислимой неограниченной нижней оценкой для $KS$, а такое невозможно по теореме 6 (с. 18). ▶

Заметим, что в этой теорема граница $l(x)/2$ выбрана произвольно: с тем же успехом можно было бы называть слово «простым», если $KS(x) < l(x) - 1$ (или, скажем, $KS(x) < \log \log l(x)$).

## 1.2.2. Сложность больших чисел

Будем рассматривать сложность $KS(m)$ как функцию натурального числа $m$, отождествляя каждое двоичное слово с его порядковым номером. Легко понять, что предел $KS(m)$ при $m \to \infty$ равен бесконечности, так как для любого $c$ лишь конечное число объектов могут иметь сложность меньше $c$. Но это стремление к бесконечности не является эффективно вычислимым: нет алгоритма, который по данному числу $n$ указывал бы то $N$, начиная с которого колмогоровская сложность становится больше $n$. (Мы убедились в этом, когда говорили о вычислимых нижних оценках для $KS$, см. с. 18.)

В этом разделе мы изучим вопрос о скорости стремления $KS$ к бесконечности более подробно. Для этого, следуя Чейтину [22], рассмотрим функцию

$$B(n) = \max\{m \in \mathbb{N} \mid KS(m) \le n\}$$

(наибольшее число, сложность которого не превосходит $n$). Эту функцию можно назвать «регулятором содумистости» $KS(m) \to \infty$ при $m \to \infty$, поскольку $K(x) > n$ при $x > B(n)$. (Формально говоря, для малых значений $n$ может оказаться, что $KS(m) > n$ при любом натуральном $m$. В этом случае можно считать, например, что $B(n) = -1$.)

Функцию $B$ можно назвать в каком-то смысле обратной к функции $KS_{\ge}(N) = \min\{KS(m) \mid m \ge N\}$. Значение $KS_{\ge}(N)$ можно интерпретировать как сложность задачи «указать какое-либо число, не меньше $N$». Функция $KS_{\ge}$ медленно растёт, принимая значение $n$ на участке $(B(n-1), B(n)]$.
<figure><img src="image_3.png" /></figure>

Рис. 1.1. К определению функции $B$: в точке $m = B(n-1)$ значение функции $KS$ не превосходит $n-1$ (на рисунке показан случай равенства), а всюду правее оно больше $n-1$. В точке $m = B(n)$ значение функции $KS$ не превосходит $n$ (показан случай равенства), а правее оно больше $n$ (на рисунке показан случай, когда оно даже больше $n+1$, и поэтому $B(n+1) = B(n)$). При $m \in (B(n-1), B(n)]$ значение $KS_{\ge}(m)$ равно $n$.

Медленный рост $KS_{\ge}$ соответствует быстрому росту функции $B$. О быстроте роста $B$ говорит такой простой факт.

**Теорема 11.** Пусть $f$ — произвольная вычислимая функция с натуральными аргументами и значениями. Тогда $B(n) \ge f(n)$ для всех $n$, кроме конечного числа.

(Заметим, что мы не требуем, чтобы $f(n)$ было определено при всех $n$. Говорится лишь, что для тех достаточно больших $n$, при которых $f(n)$ определено, выполнено неравенство $B(n) \ge f(n)$.)

### Алгоритмическое преобразование не увеличивает сложности, поэтому

$$KS(f(n)) \le KS(n) + O(1) \le \log n + c$$

для некоторого $c$ и для всех $n$, при которых $f(n)$ определено. С другой стороны, $f(n) > B(n)$ влечёт $KS(f(n)) > n$ (по определению функции $B$). Получается, что для таких значений $n$ выполняются неравенства

$$n < KS(f(n)) \le \log n + c,$$

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

Определение $B(n)$ можно переформулировать так: пусть $D$ — оптимальный способ описания, использованный при определении сложности; тогда $B(n)$ есть максимальное значение $D$ на всех словах длины не больше $n$:

$$B(n) = \max\{D(x) \mid l(x) \le n\}.$$

Напомним, что мы отождествляем слова с натуральными числами и считаем, что значениями $D$ являются натуральные числа. При этом максимум пустого множества следует считать равным $-1$.
Можно вместо $D$ рассмотреть любую вычислимую функцию $d$, аргументами которой являются слова, а значениями — натуральные числа, и рассмотреть функцию

$$B_d(n) = \max\{d(x) \mid l(x) \le n \text{ и } d(x) \text{ определено}\}.$$

Рассматриваемая нами функция $B$ является наибольшей среди них в следующем смысле:

**Теорема 12.** Для всякой функции $d$ найдётся такая константа $c$, что

$$B_d(n) \le B(n+c)$$

при всех $n$.

◀ В самом деле, значение $d(x)$ на слове $x$ длины не более $n$ имеет сложность не более $n+c$ для некоторой константы $c$, поскольку применение вычислимой функции $d$ увеличивает сложность не более чем на константу, а $KS(x) \le n+O(1)$. Другими словами, $d(x)$ — одно из чисел, сложность которых не больше $n+c$, и не превосходит наибольшего такого числа. ▶

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

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

Нас сейчас будет интересовать эта проблема для слов ограниченной длины. Итак, пусть фиксирован алгоритм $M$. Рассмотрим функцию $t(x)$, которая есть время работы алгоритма $M$ на слове $x$. (Если алгоритм $M$ не останавливается на данном $x$, то $t(x)$ не определено, так что область определения $t$ совпадает с областью определения алгоритма $M$.) Тогда $B_t(n)$ есть наибольшее время работы алгоритма $M$ на словах длины не более $n$. Зная число $B_t(n)$ или любое большее его число, мы можем решать проблему остановки для машины $M$ и любого входа $x$ длины не более $n$: надо подождать указанное время; если алгоритм не остановился за это время, то он не остановится никогда.

Как мы видели, $B_t(n) \le B(n+c)$ для некоторого $c$ (зависящего от $M$), и зная $B(n+c)$ или любое большее число, мы можем решать проблему остановки для машины $M$ и входов длины не более $n$. Сформулируем это замечание в виде теоремы:

**Теорема 13.** Для всякого алгоритма $M$ найдётся константа $c$ и алгоритм $A$, который по любому $n$ и по любому числу $t > B(n+c)$ выдаёт список всех слов длины не более $n$, на которых алгоритм $M$ останавливается.

Используя градиционную для теории алгоритмов терминологию, можно сказать, что согласно этой теореме проблема остановки для слов длины не более $n$ сводится к задаче отыскания числа, большего $B(n+c)$.
Если в качестве *M* взять оптимальный декомпрессор *D*, то верно и обратное утверждение: зная *n* и умея решать проблему остановки *D* для слов длины не более *n*, мы можем составить список всех слов сложности не более *n* и тем самым определить *B(n)*. Заметим, что для решения проблемы остановки для слов длины не более *n* достаточно указать (помимо *n*) число слов такой длины, на которых *D* останавливается.

Это рассуждение можно продолжить, доказав такое утверждение:

**Теорема 14.** Пусть $ВВ(n)$ — максимальное время работы оптимального декомпрессора на словах длины не более $n$. Тогда

$$ВВ(n) \le B(n+c) \quad \text{и} \quad B(n) \le ВВ(n+c)$$

для некоторого *с* и всех *n*.

Число $ВВ(n)$ имеет сложность не более $n + O(1)$, поскольку может быть получено по $n$ и самому долго обрабатываемому описанию $x$ длины не более $n$. Эта информация может быть записана в одном слове длины $n+1$, а именно, слове $0...01x$ (в начале стоят $n-1(x)$ нулей). Поэтому $ВВ(n) \le B(n+c)$ для некоторого $c$ и всех $n$.

С другой стороны, покажем, что для любого $t > ВВ(n)$ его сложность $k = KS(t)$ не меньше $n - O(1)$. В самом деле, возьмём описание $u$ числа $t$, имеющее длину $k$. Зная $u$ и $n$, можно алгоритмически получить слово сложности больше $n$. Для этого мы восстанавливаем $t$ и ждём $t$ шагов для каждого описания длины не более $n$. Так мы обнаружим все слова сложности не более $n$, а затем возьмём первое слово, не попавшее в их число. Следовательно, для задания $u$ и $n$ нужно не меньше $n - O(1)$ битов. А между тем их можно задать $k + O(\log(n-k))$ битами, если к самоограниченному описанию числа $n-k$ приписать $u$. Отсюда получаем, что $k + O(\log(n-k)) \ge n - O(1)$, так что $(n-k) - O(\log(n-k)) \le O(1)$ и $n-k \le O(1)$. ►

Эта теорема показывает, что функцию $В$ можно примерно (с точностью до $O(1)$-Добавки в аргументе) охарактеризовать как «время обработки самого трудного входа» ограниченной длины. Родственная конструкция появлялась в теории сложности вычислений под именем *busy beaver function* (в честь «трудолюбивых бобров»). Точнее, там для данного *n* рассматривалась машина Тьюринга с *n* состояниями и двухбуквенным алфавитом (единица и пробел), которая останавливается на пустом входе, напечатав максимально возможное число единиц (не обязательно подряд).

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

(а) список всех слов сложности не более $n$ с указанием их сложностей;

(б) число таких слов;

(в) значение $B(n)$;

(г) значение $ВВ(n)$;
(д) список всех слов длины не более $n$, на которых определён оптимальный декомпрессор («проблема остановки» оптимального декомпрессора на словах длины не более $n$);

(е) число таких слов;

(ë) самый долго обрабатываемый оптимальным декомпрессором вход длины не более $n$;

(ж) таблица $T_n$, в которой указаны значения сложности $KS(x)$ для всех слов х длины $n$;

(з) первое в словарном порядке слово $\gamma_n$ длины $n$, имеющее сложность не менее $n$ (напомним, что такое существует, так как число слов $x$ с $KS(x) < n$ меньше $2^n$).

Более точно, имеет место следующая теорема:

**Теорема 15.** Все перечисленные объекты имеют сложность $n + O(1)$ и эквивалентны друг другу в следующем точном смысле: пусть $X_n$ и $Y_n$ — объекты, указанные в каких-либо двух пунктах из числа (а) – (3). Тогда найдётся константа $c$ и алгоритм, позволяющий по $X_n$ и $n$ найти $Y_{n-c}$.

◀ Проще всего доказать эквивалентность объектов (г), (д), (е) и (ë). Зная любой из них и число $n$, можно выяснить поведение оптимального декомпрессора на всех описаниях длины не более $n$, то есть выписать все его оставляющиеся вычисления на входах длины не более $n$. В самом деле, зная список (д), мы просто применяем оптимальный декомпрессор ко всем входам из этого списка (зная заранее, что вычисления остановятся). Зная (г), мы применяем оптимальный декомпрессор ко всем входам длины не более $n$, но даём ему проработать не более $BB(n)$ шагов (будучи уверенными, что не остановившиеся за это время вычисления никогда не остановятся). Зная самый долго обрабатываемый вход длины не более $n$, мы применяем к нему оптимальный декомпрессор и находим $BB(n)$, а дальше действуем, как в предыдущем случае. Наконец, зная число слов длины не более $n$, на которых оптимальный декомпрессор оставливается, мы применяем оптимальный декомпрессор параллельно ко всем словам длины не более $n$, пока не наберём нужное количество результатов (оставшиеся вычисления не закончатся никогда).

Обратно, зная $n$ и поведение оптимального декомпрессора на всех описаниях длины не более $n$, легко найти любой из объектов (г), (д), (е) и (ë), а также объекты (а) – (в). По транзитивности (почти очевидной) мы заключаем, что (г) – (ë) все эквивалентны.

Теперь докажем, что (а) – (в) эквивалентны друг другу, а также (г) – (ë). Зная список всех слов сложности не больше $n$, можно найти их число (переход от (а) к (б)). Перейти от (б) к (а) не так просто: зная число слов сложности не больше $n$ (и зная само $n$), можно дождаться появления всех таких слов, и получить их список (в котором можно найти наибольшее число, получив (в)), но этот список будет без указания сложностей. Поскольку мы уже знаем, как от (г) перейти к (а), нам достаточно перейти от (в) к (г), то есть от $B(n)$ к $BB(n)$ (с изменением аргумента на $O(1)$). По существу этот переход уже обсуждался. Зная $B(n)$, мы знаем верхнюю оценку для $BB(n-c)$, и остаётся лишь подождать указанное время для всех входов
длины не более $n-c$, чтобы узнать точное значение $ВВ(n-c)$. Итак, мы доказали эквивалентность всех объектов (а) – (ё).

Зная (а) – (ё), можно найти (ж) для чуть меньшего значения $n$ — уменьшенного на константу $c$, для которой $KS(x) \le l(x) + c$ при всех $x$. Ясно также, как от (ж) можно перейти к (з). Осталось показать, как от (з) перейти к (г). Как, зная первое в алфавитном порядке слово $\gamma_n$ сложности не менее $n$ среди слов длины $n$, найти $ВВ(n-O(1))$ или хотя бы получить верхнюю оценку для $ВВ(n-O(1))$? Это делается следующим образом.

Зная $\gamma_n$ (и тем самым зная $n$), будем искать для всех предшествующих ему слов длины $n$ их описания длины меньше $n$; раз такие описания существуют, то рано или поздно мы их найдём (пусть даже и не кратчайшие). Найдя их, рассмотрим максимальное время работы оптимального декомпрессора на этих (найденных нами) описаниях; пусть это время будет $T$. Мы хотим доказать, что $T > ВВ(n-c)$ для некоторой константы $c$, не зависящей от $n$. Допустим, что для данного $c$ это неравенство не выполнено, то есть $T \le ВВ(n-c)$. Это значит, что одно из слов длины не более $n-c$ обрабатывается больше времени, чем нужно для обнаружения описаний длины не более $n$ у всех предшественников $\gamma_n$. Пусть это слово $u$, а длина его $n-d$. Зная $u$ и $d$, мы можем восстановить $n$, а затем найти $\gamma_n$ (за время обработки $u$ найдутся все предшественники $\gamma_n$, так что $\gamma_n$ будет первым отсутствующим). Чтобы задать $u$ и $d$, достаточно $(n-d) + 2 \log d + O(1)$ битов, откуда $n-d+2 \log d \ge KS(\gamma_n) - O(1) \ge n - O(1)$, так что $d = O(1)$.

Тем самым завершено доказательство эквивалентности объектов (а) – (ж) (в указанном выше смысле). Докажем теперь, что сложность любого из них равна $n + O(1)$. Пусть $X_n$ — любой из этих объектов. Как мы доказали, $X_n$ можно получить по $\gamma_{n+c}$ и $n$ (число $n$ равно $l(\gamma_{n+c}) - c$ и потому может быть опущено), следовательно, $KS(X_n) \le KS(\gamma_{n+c}) + O(1) \le n + O(1)$.

С другой стороны, пусть сложность $X_n$ равна $n-d$. Слово $\gamma_{n-c}$ по определению имеет сложность не меньше $n-c$ и может быть получено по кратчайшему описанию $X_n$ длины $n-d$ и по $d$ (заметим, что по этим данным можно восстановить $n$, сложив длину кратчайшего описания с $d$). Следовательно, $n-c \le KS(\gamma_{n-c}) \le (n-d) + 2 \log d + O(1)$, то есть $d \le 2 \log d + c + O(1)$ и $d = O(1)$. ►

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

**8** Докажите, что утверждение теоремы 15 остаётся верным, если разрешить в разных пунктах (а) – (ж) использовать разные оптимальные декомпрессоры.

**9** Покажите, что все объекты теоремы 15 вычислимо находятся по $n$, если разрешить использовать оракул $0'$, то есть разрешить алгоритмам спрашивать у оракула, остановится ли данная программа (эта программа уже не обращается сама к оракулу). Поэтому сложность с оракулом $0'$ для всех этих объектов есть $O(\log n)$.

Утверждение этой задачи можно обратить, и использовать сведения о сложных объектах для решения проблемы остановки. Мы установили, что существу-
ет константа $c$ и алгоритм $A$, который по слову $\gamma_n$ решает проблему остановки оптимального декомпрессора для всех слов длины не больше $n-c$. (Аналогичное рассуждение годится и для любого алгоритма, а не только для оптимального декомпрессора.) Это означает, что если у нас есть «оракул», который для каждого $n$ указывает слово $\gamma_n$, то с его помощью можно решать проблему остановки. Вместо этого можно также использовать оракул для множества «сжимаемых» слов (тех слов $x$, для которых $KS(x) < I(x)$): умея проверять сжимаемость слова, мы можем найти $\gamma_n$ перебором.

Как говорят, проблема остановки сводится по Тьюрингу к множеству сжимаемых слов. Отсюда очевидно следует, что она сводится по Тьюрингу к «надграфику» функции $KS$, то есть множеству $\{(x, k) | KS(x) < k\}$. Как говорят, множество сжимаемых слов и надграфик $KS$ являются полными по Тьюрингу перечислимыми множествами (это означает, что к любому из них сводится по Тьюрингу проблема остановки).

**10** Оцените сверху (хоть как-нибудь) число вопросов, которые придётся задать оракулу для множества $\{(x, k) | KS(x) < k\}$, чтобы решить проблему остановки оптимального декомпрессора для всех слов длины не более $n$.

Следующая задача показывает, что функция $B$ растёт так быстро, что её нельзя существенно увеличить, применив какую-то вычислимую функцию (увеличение открывается изменением аргумента на константу).

**11** Докажите, что если $f$ — вычислимая функция с натуральными аргументами и значениями, то найдётся такая константа $c$, что для всех $n$, для которых $f(B(n))$ определено, выполнено неравенство $B(n+c) \ge f(B(n))$. [Указание: число $f(B(n))$ имеет сложность не больше $n+O(1)$.]

**12** Говорят, что множество $U$ является $r$-отделимым [118], если всякое перечислимое множество $V$, не пересекающееся с $U$, можно отделить от $U$ разрешимым множеством, то есть найдётся разрешимое множество $R$, содержащее $V$ и не пересекающееся с $U$.

(а) Докажите, что множество пар $\{(x, k) | KS(x) < k\}$ (которое можно назвать «надграфиком» функции $KS$) является $r$-отделилимым множеством. Множество сжимаемых слов тоже является $r$-отделилимым. [Указание: если этот надграфик не пересекается с некоторым перечислимым множеством $V$, то вторые компоненты пар из $V$ ограничены, иначе мы получили бы неограниченную нижнюю оценку для $KS$. Значит, $V$ целиком содержится в некоторой полосе, а пересечение надграфика с этой полосой конечно.]

(б) Докажите, что если множество $U_1, m$-сводится к множеству $U_2$ (существует всюду определённая вычислимая функция $f$, для которой $U_1 = f^{-1}(U_2)$) и $U_2$ является $r$-отделилимым, то $U_1$ также $r$-отделимо. [Указание: Если перечислимое $V$ не пересекается с $U_1$, то $f(V)$ является перечислимым множеством, не пересекающимся с $U_2$. Если $R$ отделяет $f(V)$ от $U_2$, то $f^{-1}(R)$ будет разрешимым множеством, отделяющимся $V$ от $U_1$.]

(в) Выведите из этого, что существуют перечислимые множества, не обладающие свойством $r$-отделимости и потому не $m$-сводящиеся к надграфику функции $KS$. [Указание: существуют перечислимые неотделимые множества.]
13 Покажите, следуя [59], что задачи «по любому натуральному n указать слово сложности не меньше n» и «по любому алгоритму без входа указать слово, отличающееся от его выхода (если таковой существует)» эквиваленты: имея оракул, выполняющий требуемое для одной из задач, можно алгоритмически решать другую. [Указание: видя алгоритм, можно оценить сверху сложность его возможного выхода, она не сильно превосходит сложность самого алгоритма. Напротив, указать слово большой сложности означает указать слово, отличное от выходов алгоритмов из списка; считая, что эти алгоритмы выдают кортежи, мы с помощью оракула построить кортеж, который в i-й позиции отличается от выхода i-го алгоритма списка.]

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

15 (Продолжение) Покажите, что перечислимый оракул позволяет решать эти задачи в том и только том случае, когда с его помощью можно решать проблему остановки (теорема Арсланова, доказанная им без использования колмогоровской сложности). [Указание: пусть оракул для перечислимого множество А позволяет получать слова сколь угодно большой сложности. Посмотрим, сколько шагов нужно, чтобы в перечислении А появились все элементы, используемые при получении слова сложности более n. Любое T, большее этого числа, имеет сложность порядка n, так как T-приближение А можно использовать вместо А. С другой стороны, имея оракул для А, можно найти T для данного n.]

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

Теорема 15 указывает среди всех объектов сложности *n* некоторый выделенный (с точностью до описанной эквивалентности). Это отчасти парадоксально: хотелось бы думать, что все «случайные» слова длины *n* (слова длины *n* и сложности примерно *n*) более или менее одинаковы (если бы какое-то из них выделялось чем-то особенным, то эту особенность можно было бы использовать, чтобы задать его короче, и тем самым слово было бы не случайным). Тем не менее мы указали некоторое специальное случайное слово $\gamma_n$, как же так? Разрешение этого парадокса состоит в том, что индивидуальные особенности этого слова могут быть использованы для его простого задания, но лишь с оракулом $\Omega'$.⁰

Мы веримся ещё к этому вопросу, когда будем говорить о числе $\Omega$ в разделе 5.7, а также в разделе 14.3, говоря о двухчастных описаниях.

Отметим ещё, что хотя все объекты из теоремы 15 эквиваленты в указанном в ней смысле (просто получаются друг из друга), но по длине они отличаются радikalально: от длины *n* в пунктах (б), (е), (ё) и (з) до длины $\log B(n) \approx B(n - O(1))$ в пункте (в).
## 2. Сложность пары и условная сложность

### 2.1. Сложность пары

Мы уже говорили, что вычислимое кодирование позволяет говорить не только о сложности слов, но и о сложности других конструктивных объектов. Сейчас нас интересуют (упорядоченные) пары слов. Пару слов х, у можно кодировать, например, словом $[x, y] = \bar{x}01y$, где $\bar{x}$ означает слово х с удвоенными битами. Можно использовать и любое другое кодирование, важно только, чтобы оно было вычисляемым и чтобы $[x, y] \neq [x', y']$, если $x \neq x'$ или $y \neq y'$. От одного такого кодирования можно алгоритмически переходить к другому, поэтому теорема 3 (с. 14) о невозрастании сложности при алгоритмическом преобразовании показывает, что смена кодирования изменяет сложность не более чем на константу.

Фиксируем какое-либо кодирование пар $([x, y] \text{ обозначает слово, кодирующее пару слов } x, y)$ и назовём сложностью пары слов $x, y$ число $KS([x, y])$. Обозначение: $KS(x, y)$. Вот несколько очевидных свойств:

$$ \bullet KS(x, x) = KS(x) + O(1); $$

$$ \bullet KS(x, y) = KS(y, x) + O(1); $$

$$ \bullet KS(x) \le KS(x, y) + O(1); \quad KS(y) \le KS(x, y) + O(1). $$

Следующая теорема оценивает сложность пары, если известны сложности её компонент:

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

$$ KS(x, y) \le KS(x) + 2 \log KS(x) + KS(y) + O(1); $$

$$ KS(x, y) \le KS(x) + \log KS(x) + 2 \log \log KS(x) + KS(y) + O(1); $$

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

◀ Это рассуждение (для первого из неравенств) по существу проводилось во введении (теорема 4 на с. 15); правда, там мы говорили о сложности конкатенации слов ху, а не о сложности пары. Повторим его для пар.

Назовём вычислимое отображение $x \mapsto \hat{x}$ множества двоичных слов в себя беспрефиксным кодированием, если ни для каких двух различных слов х и у слово $\hat{x}$ не является началом слова $\hat{y}$. (Отсюда, в частности, следует, что $\hat{x} \neq \hat{y}$ при $x \neq y$.) Смысл этого определения таков: любое слово вида $\hat{x}z$ можно однозначно разрезать на части и найти слова х и z.
Пример беспрефиксного кодирования: $x \mapsto \bar{x}01$, где $\bar{x}$ означает строку x с удвоенными битами. Здесь признаком окончания слова являются биты 01. Это кодирование не очень экономно (увеличивает длину вдвое). Более экономно такое кодирование:

$$x \mapsto \hat{x} = \overline{\text{bin}(l(x))01x}$$

(здесь $\text{bin}(l(x))$ — двоичная запись длины слова $x$). Для него

$$l(\hat{x}) = l(x) + 2 \log l(x) + O(1).$$

Этот приём можно «итерировать»: начав с произвольного беспрефиксного кодирования $x \mapsto \hat{x}$, можно построить новое (также беспрефиксное) кодирование

$$x \mapsto \widehat{\text{bin}(l(x))x}.$$

В самом деле, если слово $\widehat{\text{bin}(l(x))x}$ является началом слова $\widehat{\text{bin}(l(y))y}$, то одно из слов $\widehat{\text{bin}(l(x))}$ и $\widehat{\text{bin}(l(y))}$ является началом другого, поэтому $\text{bin}(l(x)) = \text{bin}(l(y))$. Отсюда мы заключаем, что $x$ есть начало $y$, а потом — что $x = y$. (Другими словами, сначала мы однозначно декодируем длину слова, пользуясь тем, что она записана в беспрефиксном коде, а потом уже однозначно определяем само слово.)

Такая итерация даёт беспрефиксное кодирование, при котором

$$l(\hat{x}) = l(x) + \log l(x) + 2 \log \log l(x) + O(1),$$

затем

$$l(\hat{x}) = l(x) + \log l(x) + \log \log l(x) + 2 \log \log \log l(x) + O(1),$$

и так далее.

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

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

где $\hat{p}$ — беспрефиксный код слова $p$, а квадратные скобки означают кодирование пар, использованное при определении сложности пары. Беспрефиксность кодирования $p \mapsto \hat{p}$ гарантирует корректность этого определения ($\hat{p}$ однозначно вычленяется из $\hat{p}q$).

Если $p$ и $q$ — кратчайшие описания слов $x$ и $y$, то слово $\hat{p}q$ будет описанием слова $[x, y]$, и его длина как раз даёт оценку, указанную в теореме. (Чем более экономно беспрефиксное кодирование, тем лучше получается оценка; описанный выше итеративный метод построения беспрефиксных кодов даёт необходимые оценки.) ►

Из теоремы 16 следует, что

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

для слов $x$ и $y$ длины не более $n$. Как говорят, сложность пары не превосходит суммы сложностей её членов с точностью до логарифма (длин).
**16** Дайте естественное определение сложности тройки слов. Покажите, что $KS(x, y, z) \le KS(x) + KS(y) + KS(z) + O(\log n)$, если слова x, y, z имеют длину не больше $n$.

Возникает естественный вопрос: нельзя ли усилить оценку теоремы 16 и доказать, что $KS(x, y) \le KS(x) + KS(y) + O(1)$?

Следующее простое рассуждение показывает, что это невозможно. В самом деле, из этой оценки вытекало бы, что $KS(x, y) \le l(x) + l(y) + O(1)$. Рассмотрим какое-то $N$ и всевозможные $n = 0, 1, 2, \dots, N$. Для каждого такого $n$ имеется $2^n$ слов х длины $n$, а также $2^{N-n}$ слов у длины $N-n$. Комбинируя такие х и у, мы для данного $n$ получаем $2^N$ пар $\langle x, y \rangle$, а всего (для всех $n$ от 0 до $N$) получаем $(N+1)2^N$ пар. Если бы сложность всех этих пар $\langle x, y \rangle$ не превосходила $l(x) + l(y) + O(1) = N + O(1)$, то получилось бы $(N+1)2^N$ различных слов $[x, y]$, имеющих сложность не более $N + O(1)$, а таких слов, как мы знаем (теорема 7, с. 26), лишь $O(2^N)$.

**17** Докажите, что не найдётся такого $c$, что

$$KS(x, y) \le KS(x) + \log KS(x) + KS(y) + c$$

при всех $x$ и $y$. [Указание. Замените в правой части неравенства сложности на длины и подсчитайте количество пар.]

**18** (а) Покажите, что если $x \mapsto \hat{x}$ — беспрефиксное кодирование, то

$$\sum_{x \in \Xi} 2^{-l(\hat{x})} \le 1$$

(здесь $\Xi$ — множество всех двоичных слов).

(б) Покажите, что если беспрефиксное кодирование увеличивает длину слова не более чем на $f(n)$ (где $n$ — исходная длина), то есть $l(\hat{x}) \le l(x) + f(l(x))$, то ряд $\sum_n 2^{-f(n)}$ сходится.

Эта задача объясняет, почему понадобился коэффициент 2 при логарифме в доказательстве теоремы 16 (с. 40): ряды

$$\sum \frac{1}{n^2}, \quad \sum \frac{1}{n(\log n)^2}, \quad \sum \frac{1}{n \log n (\log \log n)^2}, \quad \dots$$

сходятся, в то время как ряды

$$\sum \frac{1}{n}, \quad \sum \frac{1}{n \log n}, \quad \sum \frac{1}{n \log n \log \log n}, \quad \dots$$

расходятся.

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

**19** Пусть $f: \mathbb{N} \to \mathbb{N}$ — неубывающая вычислимая функция. Тогда следующие три свойства равносильны:

(а) $KS(x, y) \le KS(x) + KS(y) + f(KS(x)) + O(1)$;
(б) $KS(x, y) \le l(x) + l(y) + f(l(x)) + O(1);$

(в) $\sum_n 2^{-f(n)} < \infty.$

[Указание. Из (а) очевидно следует (б); обратная импликация получается периодом к кратчайшим описаниям. Чтобы вывести (а) из (в), можно подсчитать число пар с $l(x) + f(l(x)) + l(y) < n$; можно воспользоваться также свойствами префиксной сложности из главы 4, см. задачу 107. Наконец, чтобы вывести (в) из (б), заметим, что правая часть в (б) будет меньше $n + O(1)$, если $l(x) = k$, а $l(y) = n - k - f(k)$ (при $k + f(k) \le n$). Поэтому число таких пар не меньше $\sum 2^k 2^{n-k} f(k) = 2^n \sum_k 2^{-f(k)}$, где сумма берётся по всем $k$, для которых $k + f(k) \le n$.]

**20** Докажите, что все неравенства в теореме 16 перестанут быть верными, если заменить в них коэффициент 2 на 1 (но можно заменить его на $1 + \varepsilon$ при любом $\varepsilon > 0$). [Указание. См. предыдущую задачу.]

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

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

**22** (Продолжение) Докажите, что верно даже более сильное неравенство:

$$KS(x, y) \le KS(x) + KS(y) + \log(\mathrm{KS}(x) + \mathrm{KS}(y)) + O(1)$$

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

**23** Докажите, что $KS(x, KS(x)) = KS(x) + O(1)$. [Указание. Очевидно, что $KS(x, KS(x)) \ge KS(x) + O(1)$. С другой стороны, кратчайшее описание р слова х задаёт одновременно и х, и $KS(x)$, так что $KS(x, KS(x)) \le l(p) + O(1) = KS(x) + O(1)$.]

**24** Покажите, что если $KS(x) \le n$ и $KS(y) \le n$, то $KS(x, y) \le 2n$.

### 2.2. Условная сложность

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

Назовём способом условного описания произвольную вычислимую функцию $D$ двух аргументов (аргументы и значения функции $D$ являются двоичными словами). Первый аргумент мы будем называть описанием, второй — условием. Если $D(y, z) = x$, мы говорим, что слово у является описанием слова х при известном $z$ (ешё говорят «при условии $z$», «относительно $z$»). Сложность $KS_D(x|z)$ определяется как длина кратчайшего описания слова х при известном слове $z$:

$$KS_D(x|z) = \min\{l(y) \mid D(y, z) = x\}.$$
Говорят, что способ (условного) описания $D_1$ не хуже способа $D_2$, если найдётся такая константа $c$, что

$$KS_{D_1}(x|z) \le KS_{D_2}(x|z) + c$$

для любых слов $x$ и $z$. Способ (условного) описания $D$ называется оптимальным, если он не хуже любого другого способа (условного) описания.

**Теорема 17.** Существует оптимальный способ условного описания.

◀ Этот вариант теоремы Колмогорова – Соломонова доказывается точно так же, как и безусловный (см. теорему 1, с. 11).

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

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

где $p(y, z)$ обозначает результат применения программы $p$ ко входам $y$ и $z$, а $\hat{p}$ есть беспрефиксный код слова $p$. Теперь легко проверить, что если $D' —$ произвольный способ условного описания, а $p$ — соответствующая ему программа, то

$$KS_D(x|z) \le KS_{D'}(x|z) + l(\hat{p}). \quad \blacktriangle$$

Как и прежде, мы фиксируем некоторый оптимальный способ $D$ условного описания и опускаем индекс $D$ в $KS_D$. Соответствующую функцию мы называем условной колмогоровской сложностью; как и безусловная, она определена с точностью до ограниченного слагаемого.

Вот несколько простых свойств условной колмогоровской сложности:

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

$$ 
\begin{align*}
KS(x|y) &\le KS(x) + O(1); \\
KS(x|x) &= O(1); \\
KS(f(x,y)|y) &\le KS(x|y) + O(1); \\
KS(x|y) &\le KS(x|g(y)) + O(1).
\end{align*} $$

Здесь $g$ и $f$ — произвольные вычислимые функции (одного и двух аргументов); имеется в виду, что указанные в теореме неравенства выполнены, если $f(x,y)$ (соответственно $g(y)$) определено.

◀ Безусловный способ описания можно рассматривать и как условный (не зависящий от второго аргумента), отсюда получаем первое неравенство. Второе утверждение получается, если рассмотреть способ описания $D(p, z) = z$. Третье неравенство доказывается так: пусть $D$ — оптимальный способ условного описания; рассмотрим другой способ

$$D'(p, y) = f(D(p, y), y)$$

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

$$D'(p, y) = D(p, g(y)). \quad \blacktriangle$$
**25** Покажите, что условная сложность «непрерывна по второму аргументу»:
$$KS(x|y_0) = KS(x|y) + O(1); KS(x|y_1) = KS(x|y) + O(1).$$

Используя эту «непрерывность», покажите, что для любого слова х и для любого неотрицательного $l \le KS(x)$ найдётся условие у, при котором $KS(x|y) = l + O(1)$.

**26** Покажите, что при фиксированном у функция $x \mapsto KS(x|y)$ отличается от $KS$ не более чем на константу, зависящую от у (и не превосходящую $2KS(y) + O(1)$).

**27** Докажите, что $KS([x, z] | [y, z]) \le KS(x|y) + O(1)$ для любых $x, y, z$ (квалидатные скобки означают вычислимое кодирование пар).

**28** Пусть фиксирован некоторый разумный язык программирования. (Формально говоря, надо, чтобы соответствующая ему нумерация была главной, то есть чтобы была возможна эффективная трансляция программ с других языков [175].) Покажите, что условная сложность $KS(x|y)$ равна (с точностью до $O(1)$) минимальной сложности программы, которая даёт $x$ на входе у. [Указание. Если $D$ — оптимальный способ условного описания, то сложность программы, которая получается из $D$ фиксацией первого аргумента $p$, не превосходит $l(p) + O(1)$. С другой стороны, если программа $p$ переводит у в х, то $KS(x|y) = KS(p(y)|y) \le KS(p) + O(1)$.]

К этой интерпретации условной сложности (как минимальной сложности объекта с определённым свойством) мы вернёмся в главе 13.

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

**29** Покажите, что определение тотальной условной сложности $KT(x|y)$ как минимальной сложности программы, переводящей у в х и останавливаяющейся на любом входе, корректно (не зависит с точностью до $O(1)$ от выбора разумного способа программирования). Докажите, что $KS(x|y) \le KT(x|y) \le KS(x)$ с точностью до $O(1)$.

**30** Докажите, что тотальная сложность может быть сильно больше условной:
для любого $n$ найдутся два слова $x$ и $y$ длины $n$, для которых $KS(x|y) = O(1)$,
но $KT(x|y) \ge n$. [Указание. Будем перечислять все программы сложности меньше
$n$, определённые на всех словах длины $n$, храня два слова $x$ и $y$ длины $n$ и под-
держивая такое свойство: ни одна из перечисленных программ не переводит у в х.
Когда обнаруживается новая программа, нарушающая это условие, мы выбираем
новое значение у и подбираем подходящее значение х. Этот процесс вычислим по $n$
(длине у) и задаёт частичную функцию на словах длины $n$, так что $KS(x|y) = O(1)$
для каждой выбранной пары значений.]

**31** Покажите, что если $KT(x|y) \le n$ и $KT(y|x) \le n$, то существует программа вычислимой перестановки множества двоичных слов, переводящая $x$ в $y$ и имеющая сложность не более $2n + O(1)$. [Указание. Можно закодировать программы всюду определённых функций $f$ и $g$, переводящих $x$ и $y$ и обратно, одним словом
длины $2n$. Без ограничения общности можно считать также, что х и у начинаются (скажем) на 0. Тогда рассмотрим отношение $R(u, v)$ между словами, начинающимися на 0, считая $R(u, v)$ истинным, если $f(u) = v$ и $g(v) = u$. Это разрешимое взаимно однозначное соответствие между разрешимыми множествами слов, которое легко продолжить до перестановки множеств всех слов, так как дополнения этих разрешимых множеств бесконечны.]

**32** Показайте, что оценку предыдущей задачи нельзя существенно улучшить: для любого $k$ найдутся два слова $x$ и $y$ длины $n = 2k + O(1)$, для которых $KS(x), KS(y) \le k + O(1)$ (и тем более $KT(x|y), KT(y|x) \le k + O(1)$), но любая перестановка множества слов длины $n$, отображающая $x$ в $y$, имеет сложность не менее $2k$. [Указание. Для начала выберем (произвольно) $2^k$ слов у длины $n$ и какое-нибудь одно слово $x$. Будем перечислять все перестановки сложности менее $2k$. Когда и если все пары выбранных слов будут связаны какой-либо из перечисленных перестановок, выбираем новое слово $x$, которое связано менее чем с половиной из уже выбранных слов у имеющимися перестановками, и добавим его. После этого понадобится $\Omega(2^k)$ новых перестановок, чтобы связать его со всеми выбранными у. Поэтому будет выбрано не более $2^{2k}/\Omega(2^k) = O(2^k)$ слов $x$, и сложность выбранных слов $x$ и $y$ будет не больше $k + O(1)$. Выбор слова $x$ с указанным свойством возможен, так как каждое из выбранных слов у связано с небольшой долей всех возможных $x$, и можно переставить порядок усреднения при подсчёте долей. Заметим ещё, что это рассуждение позволяет взять одно из слов в заданном множестве из $2^k$ элементов.]

Многие свойства безусловной сложности легко переносятся и на условную. Вот некоторые из них (доказательства повторяют соответствующие рассуждения для безусловной сложности):

* функция $KS(x|y)$ перечислила сверху (это означает, что множество троек $(x, y, n)$, для которых $KS(x|y) < n$, перечислимо);

* при данных $u$ и $n$ множество тех слов $x$, для которых $KS(x|y) < n$, содержит менее $2^n$ элементов, поэтому

* для всякого $u$ и для всякого $n$ найдётся слово $x$ длины $n$, сложность которого при известном $u$ не меньше $n$.

**33** Доказайте, что для любых слов $u$ и $z$ и для любого $n$ найдётся слово $x$ длины $n$, у которого $KS(x|y) \ge n-1$ и $KS(x|z) \ge n-1$. [Указание: плохие слова каждого типа образуют менее половины.]

**Теорема 19.** Если $\langle x, y \rangle \mapsto K(x|y)$ — перечислимая сверху функция, причём для любых $u$ и $n$ множество

$$ \{x \mid K(x|y) < n\} $$

содержит менее $2^n$ элементов, то $KS(x|y) \le K(x|y) + c$ при некотором $c$ и при любых $x$ и $y$.

Эта теорема доказывается аналогично теореме 8.
В теореме о сложности пары (теорема 16, с. 40) также можно заменить сложность на условную:

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

$$KS(x, y) \leq KS(x) + 2 \log KS(x) + KS(y|x) + O(1).$$

Пусть $D_1$ — оптимальный способ безусловного описания, а $D_2$ — оптимальный способ условного описания. Построим способ описания $D'$, положив

$$D'(\hat{p}q) = [D_1(p), D_2(q, D_1(p))].$$

Здесь $\hat{p}$ — беспрефиксный код слова $p$, а квадратные скобки обозначают вычисливаемое кодирование пар, используемое при определении сложности пары. Если $p$ — кратчайшее описание слова $x$, а $q$ — кратчайшее описание слова $y$ при известном $x$, то слово $\hat{p}q$ будет описанием слова $[x, y]$ относительно $D'$, откуда

$$KS(x, y) \leq KS_{D'}(x, y) + O(1) \leq l(\hat{p}) + l(q) + O(1).$$

Осталось заметить, что можно выбрать беспрефиксное кодирование так, чтобы $l(\hat{p})$ не превосходило $l(p) + 2 \log l(p) + O(1)$ (см. доказательство теоремы 16 о сложности пары, с. 40). ►

Как и раньше, можно заменить $2 \log KS(x)$ на $\log KS(x) + 2 \log \log KS(x)$ и так далее. Можно также добавочный член перенести на условную сложность, написав

$$KS(x, y) \leq KS(x) + KS(y|x) + 2 \log KS(y|x) + O(1).$$

В доказательстве при этом следует заменить $D'(\hat{p}q)$ на $D'(\hat{q}p)$.

**34** Докажите «неравенство треугольника»:

$$KS(x|z) \leq KS(x|y) + 2 \log KS(x|y) + KS(y|z) + O(1)$$

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

Если не вдаваться в тонкости различных вариантов оценки добавочного члена с логарифмом, результат теоремы 20 можно сформулировать так: для слов $x$ и $y$ длины не более $n$ имеет место неравенство

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

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

**Теорема 21** (Колмогорова – Левина).

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

для слов $x, y$ длины не больше $n$.
Пусть $A$ — произвольные слова длины не более $n$. Обозначим сложность $KS(x,y)$ пары $(x,y)$ через $a$. Пусть $A$ — множество всех пар слов, у которых сложность не больше $a$. Число элементов в множестве $A$ не больше $O(2^a)$ (точнее, меньше $2^{a+1}$), и пара $(x,y)$ — один из этих элементов.

Для каждого слова $t$ рассмотрим сечение $A_t$ множества $A$:

$$A_t = \{u \mid \langle t, u \rangle \in A\}$$

(рис. 2.1). Сумма мощностей всех множеств $A_t$ при всех $t$ равна мощности множества $A$, то есть не превосходит $O(2^a)$. Поэтому больших сечений у множества $A$ немного, что мы сейчас и используем.

<figure><img src="image_4.png" /><figcaption>Рис. 2.1. Сечение $A_t$ множества $A$ простых пар.</figcaption></figure>

Пусть $m = \lfloor \log_2 |A_x| \rfloor$, где $x$ — первая компонента исходной пары. Другими словами, пусть число элементов в $A_x$ заключено между $2^m$ и $2^{m+1}$. Докажем, что $KS(y|x)$ не сильно превосходит $m$, а $KS(x)$ не сильно превосходит $a - m$. Начнём с первого.

Зная $a$, можно перечислять множество $A$. Если мы к тому же знаем $x$, то можно оставлять от $A$ только пары, у которых первая координата равна $x$, и получить перечисление множества $A_x$. Чтобы задать $y$, помимо $a$ и условия $x$, достаточно указать порядковый номер элемента $y$ в этом перечислении. Для этого достаточно $m + O(1)$ битов, и вместе с $a$ получается $m + O(\log n)$ битов: заметим, что $a = KS(x,y)$ не превосходит $O(n)$, если $x$ и $y$ — слова длины не более $n$, а потому для задания $a$ достаточно $O(\log n)$ битов. Итак,

$$KS(y|x) \le m + O(\log n).$$

Перейдём ко второй оценке. Множество $B$ всех $t$, для которых $|A_t| \ge 2^m$, сохранит не более $2^{a+1}/2^m$ элементов (иначе сумма $|A| = \sum |A_t|$ была бы больше $2^{a+1}$). Множество $B$ можно перечислять, зная $a$ и $m$. (В самом деле, надо перечислять пары в множестве $A$; как только найдётся $2^m$ пар с одинаковой первой координатой, эта координата помещается в перечисление множества $B$.) Тем самым
исходное слово х (как и любой другой элемент множества B) можно задать, указав $(a-m) + O(\log n)$ битов $(a-m)$ битов уходят на порядковый номер слова х в B, а $O(\log n)$ битов позволяют дополнительно указать $a$ и $m$). Отсюда

$$KS(x) \le (a - m) + O(\log n),$$

и остаётся сложить два полученных неравенства. ►

Доказанную только что теорему можно рассматривать как перевод на язык колмогоровской сложности такого комбинаторного факта. Пусть дано множество А пар слов. Его мощность не превосходит произведения мощности проекции на первую координату и мощности наибольшего сечения $A_t$ (первая координата равна $t$, вторая произвольна). Это соответствует неравенству $KS(x, y) \le KS(x) + KS(y|x) + O(\log n)$. Обратное неравенство интерпретируется сложнее. Пусть дано множество А пар слов, а также числа $p$ и $q$, для которых $|A| \le pq$. Тогда можно разбить А на две части $P$ и $Q$ с такими свойствами: проекция $P$ на первую координату содержит не более $p$ элементов, а все сечения $Q_x$ множества $Q$ (первая координата равна $x$, вторая произвольна) содержат не более $q$ элементов. (В самом деле, если отнести к $P$ те сечения, которые содержат больше $q$ элементов, то их число не превосходит $p$.) Подробнее об этом см. в главе 10.

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

**Теорема 22** (Колмогорова – Левина, вариант со сложностью).

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

для любых слов х, у.

[35] Оцените более точно константы в проведённом доказательстве и покажите, что

$$KS(x) + KS(y|x) \le KS(x, y) + 3 \log KS(x, y) + O(\log \log KS(x, y)).$$

[36] Докажите, что если $KS(x, y|k, l) < k + l$, то $KS(x|k, l) < k + O(1)$ или $KS(y|x, k, l) < l + O(1)$. [Указание: это в точности соответствует рассуждению в доказательстве теоремы 22.]

[37] Показите, что в теореме Колмогорова – Левина члены порядка $O(\log n)$ неизбежны (причём в обе стороны): при любом $n$ найдутся слова х и у длины не более $n$, для которых

$$KS(x, y) \ge KS(x) + KS(y|x) + \log n - O(1),$$

а также слова х и у длины не более $n$, для которых

$$KS(x, y) \le KS(x) + KS(y|x) - \log n + O(1).$$

[Указание. В первом случае можно воспользоваться замечанием после теоремы 16 (с. 42). Во втором случае заметим, что сложность пары $KS(x, l(x)) = KS(x) + O(1)$
при любом х, а $KS(x|l(x))$ может быть равно $l(x) + O(1)$ и $KS(x) + O(1)$. Остаётся выбрать случайную длину между $n/2$ и $n$, а потом случайное слово этой длины.

**38** Покажите, что изменение одного бита в слове длины $n$ меняет его сложность не более чем на $\log n + O(\log \log n)$. Докажите то же самое для условной сложности $KS(x|n)$.

Как мы видели в задаче 7 (с. 30), для любого слова $x$ длины $n$ найдётся слово $x'$ той же длины, отличающееся от $x$ только в одной позиции, для которого $KS(x') < n - \log n + O(1)$ (и потому $KS(x'|n) < n - \log n + O(1)$). В частности, если $x$ несжимаемо при известном $n$, то при достаточно больших $n$ сложность $KS(x'|n)$ строго меньше сложности $KS(x|n)$. И наоборот, если сложность $KS(x|n)$ достаточно маленькая, точнее $KS(x|n) \le \alpha n$ для некоторой положительной константы $\alpha$, то её можно увеличить путём изменения некоторого бита $x$: для всякого достаточно большого $n$ для всех $x$ длины $n$ с $KS(x|n) \le \alpha n$ существует $x'$ длины $n$, отличающееся от $x$ только в одной позиции, для которого $KS(x'|n) > KS(x|n)$. Но доказательство этого факта требует более сложного комбинаторного рассуждения (см. [15]), чем уменьшение сложности.

**39** Фиксируем некоторый (безусловный) способ описания $D$. Докажите, что для некоторой константы $c$ и для всех $n$ и $k$ выполнено такое свойство: если какое-то слово $x$ имеет $2^k$ описаний длины не более $n$, то $KS(x|k) \le n - k + c$. [Указание. Пусть $k$ фиксировано. Для каждого $n$ рассмотрим слова $x$, имеющие не менее $2^k$ описаний длины не более $n$. Число таких слов (при данном $k$) не превосходит $2^{n-k}$, и можно воспользоваться теоремой 19, с. 46.]

С помощью этой задачи можно доказать такое утверждение о безусловной сложности:

**40** Пусть $D$ — фиксированный (безусловный) способ описания. Тогда найдётся такое число $c$, что для любого слова $x$ число кратчайших $D$-описаний слова $x$ не превосходит $c$. [Указание. В условиях предыдущей задачи $KS(x) \le n - k + 2 \log k + O(1)$, поэтому при $KS(x) = n$ значение $k$ ограничено.]

**41** Докажите, что найдётся константа $c$ с таким свойством: если для данных $x$ и $n$ вероятность события $KS(x|y) \le k$ (для случайно взятого слова у длины $n$; все такие слова считаем равновероятными) не меньше $2^{-l}$, то $KS(x|n, l) \le k + l + c$. [Указание. Соединим каждое слово у длины $n$ со всеми словами $x$, сложность которых относительно у не превосходит $k$, получим двудольный граф с $O(2^{n+k})$ рёбрами, и в нём число вершин $x$, из которых выходит не менее $2^{n-l}$ рёбер, есть $O(2^{k+l})$. Обратите внимание, что в $KS(x|n, l)$ в условие не входит $k$ — это не опечатка!]

Эта задача позволяет ответить на такой вопрос: чему в среднем равна сложность $KS(x|y)$ для данного $x$ и случайно выбранного слова у данной длины $n$? Ясно, что $KS(x|y) \le KS(x|n) + O(1)$ (поскольку $n = l(y)$ восстанавливается по $y$). Оказывается, что для большинства слов у данной длины эта оценка точная:

**42** Докажите, что найдётся такая константа $c$, что для любого слова $x$ и для любых натуральных чисел $n$ и $d$ доля тех слов у длины $n$, у которых $KS(x|y) < c$.
$< KS(x|n) - d $ (среди всех слов длины $n$), не превосходит $cd^2/2^d$. Выведите отсюда, что среднее арифметическое $KS(x|y)$ по всем словам у данной длины $n$ равно $KS(x|n) + O(1)$ (константа в $O(1)$ не зависит от $x$ и $n$).

43 Докажите, что если $KS(x|k) \le k$, то $KS(x) \le k + O(1)$. [Указание. См. теорему 7. Можно заметить также, что если описание $x$ при известном $k$ имеет длину $k$, то можно считать $k$ известным, а если оно короче, то разницу можно задать дополнительно, так как есть запас.]

Близкое (но не тождественное!) утверждение:

44 Докажите, что $KS(x) = KS(x|KS(x)) + O(1)$. [Указание. Пусть $x$ имеет короткое описание $q$ при известном $KS(x)$. Тогда для восстановления $x$ достаточно задать $q$ и разницу длин $KS(x) - l(q)$, и получается более короткое описание слова $x$, чем это возможно.]

45 Докажите, что при любом $n$ среди слов длины $n$ найдётся слово $x$, для которого $KS(KS(x)|x) = \log n - O(1)$. (Заметим, что это максимальное значение, так как $KS(x) \le n$ для слов $x$ длины $n$.)

Это утверждение (в несколько другом варианте) доказал П. Гач [43]. Наглядное доказательство в игровых терминах недавно предложили Е. Калинина и Б. Бауэнс, идея его такова. Рассмотрим прямоугольную доску ширины $2^n$ и высоты $n$, на которые два игрока (Белые и Чёрные) по очереди ставят пешки своего цвета. В отличие от шахмат, в одной и той же клетке могут помещаться и белая, и чёрная пешки (хватит места для одной пешки каждого цвета). На каждом ходу можно поставить несколько пешек в разные клетки (а можно и ни одной не ставить); поставленные пешки сдвигать и убирать нельзя. Ещё Чёрным разрешается закрашивать клетки. Ограничения:

(а) каждый из игроков может поставить не более $2^i$ пешек на горизонтали $i$ (горизонтали нумеруются снизу вверх от 0 до $n-1$);

(б) Чёрные могут в каждой вертикали закрасить не более половины клеток.

Белая пешка считается убитой, если её клетка закрашена или если ниже в той же вертикали есть чёрная пешка. Игра не имеет официального конца (хотя по существу конечна), Белые выигрывают, если в пределе у них есть неубитая пешка. В этой игре Белые могут выиграть так: поставив пешку в верхней горизонтали, они ждут, пока Чёрные её не убьют. Если это произошло из-за того, что Чёрные поставили пешку ниже, Белые переходят к следующей вертикали (скажем, начав слева и идя направо). Если же Чёрные закрасили клетку, то Белые ставят пешку на клетку ниже и снова ждут, пока она не будет убита, и так далее. (Без ограничения общности можно считать, что ответные ходы Чёрных убивают пешку Белых; поскольку выигрыш определяется предельной позицией, другие ходы можно мысленно отложить.) Поскольку закрасить можно лишь половину клеток вертикали, Чёрным придётся рано или поздно поставить пешку. Во все вертикали они поставить пешки не могут, так как сумма $2^i$ по всем горизонталям на 1 меньше числа вертикалей. Ограничение на число пешек в горизонтали Белые не нарушат, так как во всех уже отыгранных вертикалях под их пешкой в горизонтали $i$ есть чёрная
пешка в горизонтали $j < i$, а сумма $2^j$ по всем $j < i$ меньше $2^i$, и есть место ещё для одной пешки Белых.

Теперь пусть Чёрные играют так: клетка $(x, i)$ закрашивается, если обнаружилось, что $KS(i|x) < \log n - 1$; чёрная пешка ставится в клетку $(x, i)$, если обнаружилось, что у $x$ есть условное описание (при известном $n$) длины $i$. Легко понять, что при этом Чёрные не нарушают ограничений. Неубитая белая пешка в клетке $(x, i)$ будет означать, что $KS(x|n) \ge i$ и что $KS(i|x) \ge \log n - 1$; поскольку действия Белых тоже вычислимы, то при этом $KS(x|n) \ge i + O(1)$, поскольку множество белых пешек в горизонтали $i$ можно перечислять и оно содержит не более $2^i$ элементов.

Это рассуждение доказывает не совсем то, что требовалось: мы доказали, что $KS(KS(x|n)|x) \ge \log n - 1$; чтобы получить требуемое, достаточно немного изменить рассуждение и играть параллельно на досках для всех значений $n$.

**46** Докажите, что (для некоторой константы $c$) для любого слова $x$ и любого числа $n$ найдётся такое слово у длины $n$, что

$$KS(xy) \ge KS(x|n) + n - c.$$

[Указание. Для данного $n$ количество слов $x$, при которых $KS(xy) < k$ при всех у длины $n$, не превосходит $2^k/2^n$, и это свойство перечислимо, так что можно применить теорему 19 (с. 46).]

**47** Пусть $f$ — функция с натуральными аргументами и значениями, причём $f(n) + \varepsilon h \le f(n+h) \le f(n) + (1-\varepsilon)h$ для некоторого $\varepsilon > 0$ и для любых натуральных $n$ и $h$. Показите, что существует бесконечная последовательность $\omega$, у которой сложность начального отрезка длины $n$ равна $f(n) + O(1)$ при любом $n$.

[Указание. Будем строить такую последовательность добавлением блоков длины $h$: очередной блок, добавляемый к началу длины $n$. увеличивает сложность либо больше чем на $f(n+h) - f(h)$, либо меньше; выбор будет зависеть от того, ниже или выше границы мы находимся сейчас. Для поиска усложняющего блока можно применить предыдущую задачу, второй блок можно взять, скажем, из одних нулей. Заметим, что $h$ будет одно и то же для всей последовательности, и поэтому достаточно контролировать сложность начальных отрезков из целого числа блоков.]

**48** Докажите, что бесконечная последовательность $x_0 x_1 x_2 \dots$ нулей и единиц вычислима тогда и только тогда, когда величина $KS(x_0 \dots x_{n-1} | n)$ (условная сложность её начальных отрезков при известной длине) ограничена сверху.

[Указание. Отметим в бесконечном двоичном дереве всех слов перечислимое множество $S$ вершин (слов), у которых условная сложность при известной длине ограничена некоторой фиксированной константой. Все «горизонтальные» сечения множества $S$ ограничены по мощности. Нам нужно вывести из этого, что любая бесконечная ветвь, целиком проходящая по $S$, вычислима. Будем предполагать, что $S$ образует поддерево (оставив от него только те вершины, для которых путь из корня также лежит в $S$.) Фиксируем некоторую бесконечную ветвь $\omega$ в поддереве $S$ и на каждом уровне $n$ подсчитаем числа $l_n$ и $r_n$ вершин из $S$ слева и справа от $\omega$. Пусть $L$ и $R$ — верхние пределы чисел $l_n$ и $r_n$, и пусть $N$ — номер уровня,
начиная с которого эти верхние пределы не превышаются. Зная L, R и N, можно вычислять сколь угодно большие начальные отрезки ветви $ω$: надо искать ветви, слева от которых есть не менее L элементов из S на некотором уровне (большем N) и справа есть не менее R элементов из S на некотором (возможно, другом, также большем N) уровне; как только такая ветвь нашлась, её начальный отрезок до нижнего из этих двух уровней совпадает с $ω$.

**49** Докажите, что в предыдущей задаче ограниченность $KS(x_0...x_{n-1}|n)$ можно заменить более слабым условием: $KS(x_0...x_{n-1}) \le \log n + c$ для некоторого $c$ и для всех $n$. [Указание: возникает перечислимое множество $S$ слов (вершин бесконечного двоичного дерева), в котором число вершин на уровнях ниже $N$ есть $O(N)$. Если бы числа вершин на всех уровнях были бы ограничены, то задача свелась бы к предыдущей. Этого можно добиться, оставив от множества только те вершины $x$, для которых существует продолжение длины $2l(x)$, все начала которого принадлежат $S$.]

Задача 48 подсказывает разные возможности определения сложности вычислимых последовательностей $x = (x_0x_1x_2...)$ нулей и единиц:

* наименьшая сложность программы вычисления $x_0...x_{n-1}$ по данному $n$ (с точностью до константы это то же самое, что наименьшая сложность программы вычисления $x_n$ по данному $n$), эту сложность мы будем обозначать через $KS(x)$,

* наименьшая сложность программы, которая для всех достаточно больших $n$ вычисляет $x_0...x_{n-1}$ по данному $n$, обозначаемая через $KS_∞(x)$ (для конечного количества $n$ программа может на входе $n$ зависеть или давать неверный ответ),

* $\max\{KS(x_0...x_{n-1}|n) | n = 0, 1, ...\}$, обозначаемая через $M(x)$, и

* $\limsup_{n→∞} KS(x_0...x_{n-1}|n)$, обозначаемая через $M_∞(x)$.

Между этими величинами имеются очевидные неравенства:

$$M_∞(x) \le M(x) \le KS(x)$$

(с точностью до постоянного слагаемого) и

$$M_∞(x) \le KS_∞(x) \le KS(x)$$

(с той же точностью).

**50** Покажите, что существуют вычислимые последовательности, для которых $KS_∞(x)$ значительно меньше $M(x)$ (а значит и $KS(x)$). Точнее, можно указать последовательность $x^m$ вычислимых последовательностей, для которой $KS_∞(x^m)$ есть $O(\log m)$, а $M(x^m)$ не меньше $m$. [Указание. Рассмотрите последовательность $x^m = y_m 000...$, где $y_m$ обозначает лексикографически первое слово длины $m$ и сложности не менее $m$ при известном $m$.]

**51** Покажите, что также бывают вычислимые последовательности для которых $M(x)$ значительно меньше $KS(x)$. А именно, можно указать последовательность $x^m$
вычислимых последовательностей, для которой $M(x^m)$ есть $O(\log m)$, а $KS(x^m)$ не меньше $m$. [Указание. Рассмотрите последовательность $x^m = (1^{BB(m)}000...)$; число единиц перед нулями равно $BB(m)$, определение этой функции см. на с. 35.]

52. Покажите, что $KS_{\infty}(x) \le 2M_{\infty}(x) + O(1)$. [Указание. Годится рассуждение из задачи 48.]

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

53. Рассмотрим слова длины $n$, у которых сложность не меньше $n$. (Такие слова естественно назвать несжимаемыми.) (а) Покажите, что количество таких слов не меньше $2^{n-c}$ и не больше $2^n - 2^{n-c}$ (для некоторого $c$). (б) Покажите, что сложность количества несжимаемых слов длины $n$ равна $O(1)$ (отсюда следуют утверждения предыдущего пункта!). (в) Покажите, что если слово $x$ длины $2n$ является несжимаемым, то его половины $x_1$ и $x_2$ (длины $n$) имеют сложность $n - O(1)$. (г) Покажите, что если слово $x$ длины $n$ является несжимаемым, то любое его подслово длины $k$ имеет сложность не меньше $k - O(\log n)$. (д) Покажите, что для любой константы $c < 1$ любое несжимаемое слово достаточно большой длины $n$ содержит подслово из $\lfloor c \log_2 n \rfloor$ нулей. [Указание. (а) Всего описаний длины меньше $n$ будет $2^n - 1$, но часть их уходит на более короткие слова: любое слово длины $n-d$ при некотором $d$ имеет сложность меньше $n$, что доказывает первое утверждение. Чтобы доказать второе, заметим, что слова длины $n$, начинающиеся с $k$ нулей, можно задать $2 \log k + (n-k)$ битами. (б) Если число несжимаемых слов длины $n$ можно описать двоичным словом $t$ длины $n-k$, то по $t$ и $\log k$ битов можно восстановить $n$ и, список всех несжимаемых слов длины $n$, поэтому первое из несжимаемых слов будет иметь сложность меньше, чем следует. (в) Если одну из половин можно описать короче, то и всё слово можно задать короче, начав с (беспрефиксного кода) разности между длиной и сложностью сжимаемой половины. (г) Если подслово имеет меньшую сложность, то и всё слово можно описать короче (задав подслово, его положение и остальные биты). (д) Подсчитаем число слов длины $n$, не содержащих подряд $k$ нулей; рекуррентное соотношение показывает, что это число растёт с увеличением $n$ примерно как геометрическая прогрессии, знаменатель которой есть наибольший действительный корень уравнения $x = 2 - (1/x^k)$, и можно оценить сложность таких слов.]

54. Покажите, что (при некотором значении $c$) для любой бесконечной последовательности $x_0x_1x_2...$ нулей и единиц найдётся бесконечно много значений $n$, для которых $KS(x_0x_1...x_{n-1}) \le n - \log n + c$.

Покажите, что найдётся последовательность $x_0x_1x_2...$ и константа $c$, для которых $KS(x_0x_1...x_{n-1}) \ge n - 2\log n - c$ при всех $n$.

[Указание. Ряд $\sum 1/n$ расходится, а ряд $\sum 1/n^2$ сходится. Подробнее см. теоремы 95 и 99.]

55. Для данного слова $x$ длины $n$ определим величины $d(x) = n - KS(x)$ и $d_c(x) = n - KS(x|n)$. Покажите, что они связаны неравенством

$$d_c(x) - 2 \log d_c(x) - O(1) \le d(x) \le d_c(x) + O(1).$$
[Указание. Надо доказать, что если $KS(x|n) = n-d$, то $KS(x) \le n-d+2\log d + O(1)$. В самом деле, взяв условное описание р длины $n-d$ и добавив в его начало самоограниченную запись $d$, мы получим слово, по которому можно восстановить сначала $d$, потом $n$, и наконец $x$.]

**56** Докажите, что $d(xy) = d(x) + d(y|x) + O(\log d(xy))$ для любых двух слов $x, y$ длины $n$, где $d(u) = l(u) - KS(u)$. [Указание: можно воспользоваться задачей 36.]

(Интуитивный смысл разности между длиной слова и его сложностью как дефекта случайности обсуждается для разных видов сложности в главе 5 и в главе 14.)

**57** Показайте, что для достаточно большого значения константы $c$ перечислимое множество пар слов $(x, y)$, для которых $KS(x|y) < c$, является полным по Тьюрингу (с помощью оракула для этого множества можно алгоритмически решать проблему остановки). [Указание: воспользуйтесь задачей 15.]

### 2.3. Количество информации

Мы знаем (теорема 18), что условная сложность $KS(y|x)$ не превосходит безусловной сложности $KS(y)$ (с точностью до константы). Разность $KS(y) - KS(y|x)$ показывает, насколько знание слова $x$ упрощает описание слова $y$. Поэтому её называют количеством информации в слове $x$ о слове $y$. Обозначение: $I(x:y)$.

Теорема 18 показывает, что информация $I(x:y)$ неотрицательна (с точностью до константы): существует такое $c$, что $I(x:y) \ge c$ при всех $x$ и $y$.

**58** Пусть дана произвольная вычислимая функция $f$. Тогда для некоторой константы $c$ выполнено неравенство $I(f(x):y) \le I(x:y) + c$.

**59** Докажите обобщение этого свойства на вероятностные алгоритмы. А именно, пусть дана произвольная вычислимая функция $f(x, r)$. Пусть $r$ выбирается с равномерным распределением среди строк некоторой длины $n$. Тогда для всех $l$ вероятность события $I(f(x, r):y) > I(x:y) + l$ не превосходит $2^{-l+O(KS(n)+KS(l))}$. Это свойство информации называют «невозрастанием информации при алгоритмических преобразованиях». Пользуясь метафорой Левина, смысл этого неравенства можно выразить словами «пытка неинформированного свидетеля не даст информации о преступлении» [82]. [Указание. Используйте условный вариант задачи 41.]

Вспомнив, что

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

(теорема 22, с. 49), можно выразить условную сложность через безусловные:

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

Тогда для информации получается выражение:

$$I(x:y) = KS(y) - KS(y|x) = KS(x) + KS(y) - KS(x, y) + O(\log KS(x, y)).$$
Отсюда сразу вытекает

**Теорема 23** (симметрия информации).

$$I(x:y) = I(y:x) + O(\log KS(x,y)).$$

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

**60** Покажите, что если $x$ — слово длины $n$, для которого $KS(x|n) \ge n$, то $I(x:n) = KS(n) + O(1)$, в то время как $I(n:x) = O(1)$.

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

<figure><img src="image_5.png" /><figcaption>Рис. 2.2. Взаимная информация и условная сложность.</figcaption></figure>

На ней показано, что слова $x$ и $y$ имеют $I(x:y) \approx I(y:x)$ битов общей информации. Добавив $KS(x|y)$ битов (информация, которая есть в $x$, но не в $y$, левая область), мы получаем

$$I(y:x) + KS(x|y) \approx (KS(x) - KS(x|y)) + KS(x|y) \approx KS(x)$$

битов (как и должно быть в слове $x$). Аналогичным образом центральная часть вместе с $KS(y|x)$ справа дают $KS(y)$. Наконец, все три области вместе складываются в

$$KS(x|y) + I(x:y) + KS(y|x) = KS(x) + KS(y|x) = KS(x|y) + KS(y) = KS(x,y)$$

(все равенства верны с точностью $O(\log n)$, если слова $x$ и $y$ имеют длину не больше $n$).

В некоторых случаях эту картинку можно понимать буквально. Возьмём, например, «несжимаемое» слово $r = r_1...r_n$ длины $n$, для которого $KS(r_1...r_n) \ge n$. Тогда сложность любого его подслова $u$ равна $l(u)$ с точностью до $O(\log n)$. В самом деле, поскольку $u$ является подсловом $r$, то $r = tuv$ для некоторых слов $t$ и $v$. Тогда $l(r) \le KS(r) \le KS(t) + KS(u) + KS(v) \le l(t) + l(u) + l(v) = l(r)$ (с логарифмической точностью) и потому все неравенства обращаются в равенства (с той же точностью).
Если теперь взять два перекрывающихся подслова х и у (рис. 2.3), то $KS(x)$ будет равно длине х, $KS(y)$ будет равно длине у (с точностью до $O(\log n)$).

<figure><img src="image_6.png" /><figcaption>Рис. 2.3. Общая информация в перекрывающихся подсловах.</figcaption></figure>

Сложность пары $KS(x, y)$ будет равна длине объединения отрезков (поскольку пара х, у отличается от этого объединения лишь информацией о длинах, которая требует $O(\log n)$ битов).

Следовательно, и условные сложности $KS(x|y)$, $KS(y|x)$, и общая информация $I(x:y)$ равны (с логарифмической точностью) длинам соответствующих отрезков.

Однако такая ситуация имеет место далеко не всегда. Как мы впоследствии убедимся (см. главу 11), далеко не для всяких двух слов х и у, имеющих большую взаимную информацию $I(x:y)$, эту взаимную информацию можно «материализовать» в виде слова z, для которого $KS(z|x) \approx 0$, $KS(z|y) \approx 0$ и $KS(z) \approx I(x:y)$. (В нашем последнем примере таким z было пересечение подслов х и у.)

**61** Докажите, что для любого слова х длины не больше n математическое ожидание количества общей информации в х и случайном слове длины n есть $O(\log n)$.

Рассмотрим теперь сложностные характеристики трёх слов. Здесь важным приёмом является релятивизация — перенесение свойств безусловной сложности на условную. Поясним это на примере.

Теорема о сложности пары (с. 40) утверждает, что

$$KS(x, y) \le KS(x) + 2 \log KS(x) + KS(y) + O(1).$$

Если все сложности заменить на условные (при известном z), получится неравенство

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

где под условной сложностью пары х, у при известном z понимается сложность её кода: $KS(x, y|z) = KS([x, y]|z)$. Как и для безусловной сложности пары, выбор кодирования несуществен (меняет сложность на $O(1)$).

Это неравенство доказывается точно так же, как и неравенство без z: мы соединяем описание p для х (при известном z) и q для у (при известном z) в единое описание $\hat{pq}$ относительно нового способа (условного) описания.

Поучительно исключить из этого неравенства условные сложности, заменив их на безусловные: $KS(x, y|z) = KS(x, y, z) - KS(z)$, а также $KS(x|z) = KS(x, z) - KS(z)$ и $KS(y|z) = KS(y, z) - KS(z)$ (с логарифмической точностью). При
этом мы приходим к такой теореме:

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

$$KS(x, y, z) + KS(z) \le KS(x, z) + KS(y, z) + O(\log n)$$

для слов х, у, z сложности не более n.

Это неравенство иногда называют базисным.

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

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

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

если слова х, у, z имеют сложность не больше n.

Здесь $KS(x|y, z)$ понимается как сложность х относительно кода пары $(y, z)$, то есть как $KS(x|[y, z])$. Как и раньше, вычислимое кодирование пар может быть любым (сложность изменится не более чем на константу).

◀ Можно воспроизвести доказательство теоремы 21, заменив везде описания без условий на описания при известном $z$. При этом $KS(y|x)$ превратится в $KS(y|x, z)$. Можно сказать, что мы теперь имеем трёхмерное пространство с координатами х, у, z и проводим все прежние рассуждения одновременно во всех плоскостях, параллельных плоскости ху.

Если это кажется слишком сложным, можно просто выразить все условные сложности через безусловные: в левой части получим

$$KS(x, y | z) = KS(x, y, z) - KS(z),$$

а в правой

$$KS(x|z) + KS(y|x, z) = KS(x, z) - KS(z) + KS(y, x, z) - KS(x, z),$$

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

**62** Проверьте, что в теореме 25 достаточно потребовать, чтобы условные сложности $KS(x|z)$ и $KS(y|x, z)$ не превосходили $n$.

Можно «релятивизовать» определение информации, определив $I(x:y|z)$ как разность $KS(y|z) - KS(y|x, z)$. Как и для случая безусловной информации, эта величина неотрицательна (с точностью до $O(1)$). Выразив условную сложность через безусловную (с логарифмической точностью), можно записать неотрицательность $I(x:y|z)$ как

$$KS(y|z) - KS(y|x, z) = KS(y, z) - KS(z) - KS(y, x, z) + KS(x, z) \ge 0,$$

приходя к неравенству теоремы 24.
Вообще большинство известных равенств и неравенств, касающихся безусловных сложностей, условных сложностей и информации (с логарифмической точностью), являются прямыми следствиями «базисных неравенств» — теорем 21 и 24. Первые примеры неравенств, которые не выводятся из базисных, были найдены сравнительно недавно [193, 194], и они довольно сложные. Мы обсудим их в разделе 10.13, а пока рассмотрим несколько простых следствий базисных неравенств.

**Независимые слова.** Будем называть слова х и у «независимыми», если $I(x:y) \approx 0$. (Степень точности должна ещё уточняться, но мы предполагаем, что членами порядка $O(\log n)$ мы пренебрегаем, если $n$ — максимальная из длин (или сложности) используемых слов.)

Независимые слова можно рассматривать как аналог независимых случайных величин в теории вероятностей. Есть такая теорема: если случайная величина $\xi$ независима с парой величин $\langle \alpha, \beta \rangle$, то она независима и с величинами $\alpha$ и $\beta$ по отдельности.

Для колмогоровской сложности аналогичное утверждение (если слово х независимо с парой $\langle y, z \rangle$, то оно независимо и с её отдельными компонентами) естественно выражается неравенством

$$I(x: \langle y, z \rangle) \ge I(x:y)$$

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

$$KS(x) + KS(y, z) - KS(x, y, z) \ge KS(x) + KS(y) - KS(x, y),$$

что после приведения подобных членов даёт базисное неравенство теоремы 24.

**Сложность пар и троек.** Напротив, для доказательства следующей теоремы (упоминавшейся на с. 22) полезно заменить безусловные сложности на условные:

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

$$2 KS(x, y, z) \le KS(x, y) + KS(x, z) + KS(y, z) + O(\log n),$$

если $x, y, z$ — слова сложности не более $n$.

◀ Перенося $KS(x, y)$ и $KS(x, z)$ в левую часть, и заменяя разности $KS(x, y, z) - KS(x, y)$ и $KS(x, y, z) - KS(x, z)$ на условные сложности $KS(z|x, y)$ и $KS(y|x, z)$, мы получаем такое неравенство:

$$KS(z|x, y) + KS(y|x, z) \le KS(y, z) + O(\log n).$$

Остаётся переписать правую часть неравенства как $KS(y) + KS(z|y)$ и заметить, что $KS(z|x, y) \le KS(z|y)$ и $KS(y|x, z) \le KS(y)$ (с логарифмической точностью). ▶

А можно вместо этого формально сложить два неравенства (базисное и для сложности пары):

$$KS(x, y, z) + KS(y) \le KS(x, y) + KS(y, z) + O(\log n),$$

$$KS(x, y, z) \le KS(y) + KS(x, z) + O(\log n),$$
после чего сократить $KS(y)$ в обеих частях и получить требуемое. (К сожалению, это доказательство, как и предыдущее, несимметрично.) Мы вернёмся к этому равенству и его геометрическим следствиям в главе 10.

Различные сложностные характеристики трёх слов можно систематизировать следующим образом. Имеются семь основных таких характеристик (три сложности одиночных слов, три сложности пар и сложность всей тройки). Другие характеристики (условная сложность, информация) выражаются через них. Чтобы лучше представить себе, какие ограничения накладываются на эти семь сложностей, удобно перейти к новым координатам. Введём переменные $a_1, a_2, \dots, a_7$, соответствующие семи областям на рис. 2.4.

<figure><img src="image_7.png" /><figcaption>Рис. 2.4. Новые координаты $a_1, a_2, \dots, a_7$.</figcaption></figure>

Будем считать, что

$$KS(x) = a_1 + a_2 + a_4 + a_5,$$

$$KS(y) = a_2 + a_3 + a_5 + a_6,$$

$$KS(z) = a_4 + a_5 + a_6 + a_7,$$

$$KS(x, y) = a_1 + a_2 + a_3 + a_4 + a_5 + a_6,$$

$$KS(x, z) = a_1 + a_2 + a_4 + a_5 + a_6 + a_7,$$

$$KS(y, z) = a_2 + a_3 + a_4 + a_5 + a_6 + a_7,$$

$$KS(x, y, z) = a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7.$$

Легко проверить, что эти равенства задают обратимое линейное преобразование семимерного пространства (каждому набору из семи сложностей соответствует единственное значение переменных $a_1, \dots, a_7$).

Различные условные сложности и взаимные информации (с логарифмической точностью) выражаются через безусловные, поэтому можно их выразить и в новых координатах. Например, $I(x:y) = KS(x) + KS(y) - KS(x,y) = a_2 + a_5$, а $KS(x|y) = KS(x,y) - KS(y) = a_1 + a_4$.

Каков смысл наших новых координат? Легко проверить, что $a_1 = KS(x|y,z)$ (с логарифмической точностью). Аналогичный смысл имеют $a_3$ и $a_7$. Координата $a_2$ равна (с той же точностью) $I(x:y|z)$; аналогичный смысл имеют $a_4$ и $a_6$ (см. рис. 2.5). Отсюда, в частности, вытекает, что для любых слов $x, y, z$ соответствующие значения координат $a_1, a_2, a_3, a_4, a_6, a_7$ неотрицательны (с точностью до $O(\log n)$, если слова $x, y, z$ имеют сложность не больше $n$).
<figure><img src="image_8.png" /><figcaption>Рис. 2.5. Сложностной смысл новых координат.</figcaption></figure>

Ситуация с координатой $a_5$ сложнее. Её хотелось бы интерпретировать как «об-
щую информацию, содержащуюся в трёх словах х, у, z». Иногда для неё использу-
ется обозначение $I(x:y:z)$. Однако смысл такого выражения далеко не очевиден,
особенно если иметь в виду, что $a_5$ может быть отрицательным. Рассмотрим та-
кой пример. Пусть х и у — две половины несжимаемого слова длины $2n$. Тогда
$KS(x) = n$, $KS(y) = n$, $KS(x,y) = 2n$ и $I(x:y) = 0$ (с логарифмической точно-
стью). Рассмотрим слово z длины $n$, которое является побитовой суммой х и у
по модулю 2. Тогда любое из трёх слов х, у, z может быть восстановлено по двум
другим, следовательно, сложности $KS(x,y)$, $KS(y,z)$ и $KS(x,z)$ одинаковы и рав-
ны $2n$ (с логарифмической точностью), и сложность $KS(x,y,z)$ также равна $2n$.
Сложность слова z равна $n$ (она не больше $n$, так как его длина равна $n$, но и не
меньше, так как иначе вместе с у не получилось бы пары сложности $2n$).

После этого можно вычислить значения $a_1, \dots, a_7$ для этого примера (рис. 2.6).

<figure><img src="image_9.png" /><figcaption>Рис. 2.6. Два независимых несжимаемых слова длины $n$ и их сумма $mod 2$.</figcaption></figure>

Таким образом координата $a_5$ может быть отрицательной, однако суммы $a_5 + a_2$, $a_5 + a_4$ и $a_5 + a_6$, будучи взаимными информациями пар слов, должны быть нео-
трицательны. (В нашем примере эти суммы равны нулю.)
Этот пример соответствует простейшему способу «разделения секрета» z между двумя лицами: если одному человеку сообщить х, а другому у, то ни один из них по отдельности не будет ничего знать о z (поскольку $I(x:z) \approx 0$ и $I(y:z) \approx 0$), но вместе они могут восстановить z, побитово сложив х и у.

Можно проверить, что указанными неравенствами (неотрицательность всех $a_i$, кроме $a_5$, и неотрицательность трёх названных сумм) исчерпываются все линейные неравенства, имеющиеся для сложностных характеристик трёх слов. Мы вернёмся к этому вопросу в главе 10.

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

$$2 \text{KS}(x, y, z) \le \text{KS}(x, y) + \text{KS}(x, z) + \text{KS}(y, z).$$

В наших новых переменных оно записывается как $a_2 + a_4 + a_5 + a_6 \ge 0$ (это легко проверить в уме, подсчитав, сколько раз входит каждое из $a_i$ в левую и правую часть неравенства). Теперь остаётся заметить, что $a_2 + a_5 \ge 0$, $a_4 \ge 0$ и $a_6 \ge 0$.

**[63]** Докажите, что $I(xy:z) = I(x:z) + I(y:z|x) + O(\log n)$ для слов x, y, z сложности не более $n$. [Указание: это легко объяснить на диаграмме.]

Эта задача показывает, что информация в ху о z складывается из двух частей: информации в х о z и информации в у о z (при известном х). Можно рассматривать её как аналог равенства $\text{KS}(x, y) = \text{KS}(x) + \text{KS}(y|x)$, только теперь вместо сложности стоит информация о слове z. В качестве следствия получаем, что если ху независимо с z, то х независимо с z, а также у независимо с z при известном х. (Под независимостью понимается малость взаимной информации.) Симметричное рассуждение показывает, что у независимо с z, а также х независимо с z при известном у.

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

**[65]** Будем говорить, что слова x, y, z, t образуют марковскую цепь (по аналогии с соответствующим понятием теории вероятностей), если $I(x:z|y)$ и $I(\langle x, y \rangle: t|z)$ малы (разумеется, точный смысл определения зависит от выбора границы малости). Покажите, что в этом случае эти же слова в обратном порядке образуют марковскую цепь, то есть что $I(t:y|z)$ и $I(\langle t, z \rangle:x|y)$ малы. [Указание. $I(\langle x, y \rangle:t|z) = I(y:t|z) + I(x:t|y, z)$, и равенство нулю левой части означает обращение в нуль обоих слагаемых справа; второе слагаемое симметрично относительно обращения порядка.]
### 3. Случайность по Мартин-Лёфу

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

Мы начём с напоминания основных фактов о мерах на последовательностях нулей и единиц.

#### 3.1. Пространство Ω и меры

Рассмотрим пространство $\Omega = \mathbb{B}^N$, элементами которого являются бесконечные последовательности нулей и единиц. Его называют **канторовским пространством**. Для каждого двоичного слова $x$ мы рассмотрим множество $\Omega_x$ всех продолжений этого слова. Например, $\Omega_{00}$ есть множество всех последовательностей, начинающихся с двух нулей, а $\Omega_\Lambda = \Omega$ (здесь $\Lambda$ обозначает пустое слово).

Множества вида $\Omega_x$ мы будем называть **интервалами**. Интервалы и всевозможные их объединения называют **открытыми** подмножествами пространства $\Omega$. Эта топология соответствует стандартной метрике, в которой расстояние между двумя последовательностями тем меньше, чем больше у них совпадающее начало:

$$d(\omega, \omega') = 2^{-n},$$

где $n$ — наименьшее число, для которого $\omega_n \neq \omega'_n$. (Через $\omega_n$ мы обозначаем член с номером $n$, начиная нумерацию с нуля: $\omega = \omega_0\omega_1\omega_2\dots$)

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

Нас, однако, будет интересовать не столько топология, сколько мера. Семейство подмножеств пространства $\Omega$ называют **$\sigma$-алгеброй**, если оно замкнуто относительно конечных и счётных пересечений и объединений, а также перехода к дополнению.

Минимальную $\sigma$-алгебру, содержащую все множества $\Omega_x$ (и тем самым все открытые множества), называют алгеброй **борелевских множеств**.

Рассмотрим произвольную $\sigma$-алгебру, содержащую все интервалы. Пусть на ней задана функция $\mu$, которая ставит в соответствие каждому множеству из $\sigma$-алгебры
неотрицательное число, причём выполнено свойство σ-аддитивности:

если множество A есть объединение конечного или счётного числа не-
пересекающихся множеств $A_0, A_1, A_2, \dots$, и все эти множества принад-
лежат σ-алгебре, на которой определена функция μ, то

$$
\mu(A) = \mu(A_0) + \mu(A_1) + \mu(A_2) + \dots
$$

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

Такие функции называют мерами на пространстве Ω; множества, на которых
мера определена, называют измеримыми (по этой мере), и μ(А) называют мерой
множества А.

Если мера всего пространства Ω равна 1, то меру называют распределением вероятностей, элементы σ-алгебры называют событиями, а число μ(А) называют вероятностью события А.

Любая мера монотонна (если $A \subset B$, то $\mu(A) \le \mu(B)$). В самом деле, $\mu(B) - \mu(A) = \mu(B \setminus A) \ge 0$.

Другое важное свойство мер — непрерывность: если множество В есть объединение возрастающей последовательности множеств

$B_0 \subset B_1 \subset B_2 \subset \dots,$

то μ(В) равно пределу μ(Bᵢ) при i → ∞. (В самом деле, применяем счётную и
конечную аддитивность к множествам Aᵢ = Bᵢ \ Bᵢ₋₁.) Аналогичное свойство не-
прерывности верно и для убывающих последовательностей множеств.

Для каждой меры μ на Ω можно рассмотреть функцию p на двоичных словах, определённую равенством p(x) = μ(Ωx). Эта функция принимает неотрицательные значения, при этом выполнено свойство аддитивности:

$p(x) = p(x0) + p(x1)$

для любого слова x. (В самом деле, интервал Ωx есть дизъюнктное объединение двух его половин Ωx0 и Ωx1.)

Теория меры (теорема о продолжении меры по Лебегу) позволяет выполнить и обратный переход. Именно, для каждой функции p на двоичных словах, принимающей неотрицательные действительные значения и обладающей свойством аддитивности, можно построить меру μ, для которой μ(Ωx) = p(x) при всех х. Эта мера обладает дополнительным свойством (которое мы будет предполагать в дальнейшем: если μ(A) = 0 и B ⊂ A, то B измеримо (отсюда уже следует, что μ(B) = 0.

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

Напомним, что у нас фиксирована неотрицательная функция p на словах, обладающая свойством аддитивности. Будем называть число p(x) мерой интервала Ωх. Говорят, что множество A ⊂ Ω является нулевым, если для всякого ε > 0 можно
найти конечное или счётное покрытие множества А интервалами с суммой мер не больше ε.

Другими словами, множество А нулевое, если существует функция $\langle \varepsilon, i \rangle \mapsto x(\varepsilon, i)$ (первый аргумент — положительное действительное число, второй — натуральное число, значениями являются двоичные слова), для которой

* $A \subset \Omega_{x(\varepsilon, 0)} \cup \Omega_{x(\varepsilon, 1)} \cup \Omega_{x(\varepsilon, 2)} \dots$ и

* $p(x(\varepsilon, 0)) + p(x(\varepsilon, 1)) + p(x(\varepsilon, 2)) + \dots \le \varepsilon$

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

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

Несколько простых наблюдений, которые нам пригодятся в дальнейшем:

* В определении нулевого множества можно было бы ограничиться рациональными значениями ε (или только значениями вида $2^{-k}$).

* Всякое подмножество нулевого множества является нулевым.

* Конечное или счётное объединение нулевых множеств является нулевым. (В самом деле, чтобы найти покрытие объединённого множества с суммой мер меньше ε, достаточно соединить покрытия его частей с суммой мер меньше ε/2, ε/4, ε/8, ...)

* Пусть функция p такова, что каждая точка имеет меру нуль (это будет так, если для любой бесконечной последовательности $\omega = \omega_0\omega_1\omega_2\dots$ предел мер $p(\omega_0\dots\omega_n)$ при $n \to \infty$ равен нулю). Тогда любое конечное или счётное множество является нулевым.

Равномерная мера на пространстве Ω получится, если положить меру интервалами $\Omega_x$ равной $2^{-l(x)}$:

$$p(x) = 2^{-n} \text{ для всех слов x длины } n.$$

Возникающая при этом мера тесно связана с обычной мерой на действительной прямой (точнее, на отрезке $[0, 1]$): мера множества $A \subset \Omega$ равна мере множества действительных чисел, которое получится, если каждую последовательность из А считать бесконечной двоичной дробью. (Замечание в скобках: соответствие между двоичными дробями и числами не совсем взаимно однозначно, так как двоично-рациональные числа имеют два представления: например, $0,01111\dots = 0,10000\dots$. Но это затрагивает лишь счётное множество чисел, которое пренебрежимо с точки зрения теории меры.) В самом деле, числа, двоичные записи которых начинаются на данную строку x длины n, заполняют промежуток длины $2^{-n}$. Отсюда легко заключить, что для любого отрезка $I \subset [0, 1]$ равномерная мера множества последовательностей, являющихся двоичными разложениями чисел из I, равна длине отрезка I.
С точки зрения теории вероятностей равномерная мера соответствует независимым бросаниям честной монеты. В самом деле, при независимых бросаниях честной монеты все возможные последовательности длины $n$ равновероятны и имеют вероятность $2^{-n}$. Множество $\Omega_x$ есть событие «полученная в результате бросаний последовательность начинается на $x$» и имеет меру $2^{-l(x)}$.

Можно рассматривать и несимметричную монету, по-прежнему предполагая бросания независимыми. Соответствующая мера (распределение вероятностей) называется бернуллиевой с параметрами $q, p$ (вероятности выпадения нуля и единицы; предполагается, что $p, q \ge 0$ и $p+q=1$).

При этом вероятность появления последовательности, начинающейся на слово $x$, равна $q^u p^v$, где $u$ и $v$ — число нулей и единиц в этом слове. Другими словами, мы рассматриваем функцию

$$x \mapsto q^{u(x)} p^{v(x)},$$

где через $u(x)$ и $v(x)$ обозначено число нулей и единиц в слове $x$. Легко проверить, что эта функция аддитивна.

## 3.2. Усиленный закон больших чисел

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

Пусть $p+q=1$, $p, q \ge 0$. Рассмотрим множество $A_p$ всех бесконечных последовательностей $\omega_0\omega_1\omega_2\dots$ нулей и единиц, в которых предел частоты единиц существует и равен $p$, то есть

$$\lim_{n \to \infty} \frac{\omega_0 + \omega_1 + \dots + \omega_{n-1}}{n} = p.$$

**Теорема 27.** Множество $A_p$ имеет меру 1 относительно бернуллиева распределения вероятностей (с параметрами $p$ и $q$).

Другими словами, дополнение множества $A_p$, то есть множество тех последовательностей, в которых частота единиц не стремится ни к какому пределу или имеет предел, отличный от $p$, является нулевым.

◄ Мы докажем эту теорему для равномерной меры (то есть при $p=q=1/2$) с помощью явного подсчёта. Для произвольного $p$ доказательство будет кратко намечено в одном из упражнений (см. также раздел 9.6).

Сначала рассмотрим «допредельную» ситуацию, зафиксировав некоторое число $n$. Все последовательности из $n$ нулей и единиц равновероятны, и нам нужно доказать, что большинство из них содержит примерно $n/2$ единиц. Пусть выбрана некоторая граница $\varepsilon > 0$. Посмотрим, сколько последовательностей имеет более $(1/2 + \varepsilon)n$ единиц. Другими словами, мы должны просуммировать в треугольнике Паскаля часть $n-й$ строки, которая начинается несколько правее середины. Всего в этой части не более $n$ слагаемых и они убывают, поэтому сумму можно оценить как первое слагаемое, умноженное на $n$. (На самом деле нам не нужна большая точность, и полиномиальные от $n$ множители нам не повредят, так что ими мы сразу пренебрегаем. В частности, мы опускаем множитель $n$.)
Первое слагаемое равно

$$ \frac{n!}{k!(n-k)!}, $$

где $k$ — ближайшее справа $k(1/2 + \epsilon)n$ целое число. Воспользуемся формулой Стирлинга:

$$ m! = \sqrt{(2\pi + o(1))m} \left(\frac{m}{e}\right)^m, $$

где $e$ — основание натуральных логарифмов. Отбрасывая полиномиальные множители и используя обозначения $u = k/n$, $v = (n-k)/n$, получаем

$$ \begin{aligned} \frac{n!}{k!(n-k)!} &\approx \frac{(n/e)^n}{(k/e)^k ((n-k)/e)^{n-k}} = \frac{n^n}{k^k (n-k)^{n-k}} \\ &\approx \frac{n^n}{(un)^{un} (vn)^{vn}} = \frac{1}{u^{un} v^{vn}} = 2^{H(u,v)n}, \end{aligned} $$

где

$$ H(u, v) = -u \log u - v \log v. $$

Число $H(u, v)$ называется шенноновской энтропией случайной величины с двумя значениями, принимаемыми с вероятностями $u$ и $v$. (подробно шенноновская энтропия обсуждается в главе 7.) На рисунке 3.1 показан соответствующий график

<figure><img src="image_10.png" /><figcaption>Рис. 3.1. Шенноновская энтропия как функция $u$.</figcaption></figure>

(напомним, что $v = 1 - u$). легко проверить, что величина $H(u, 1 - u)$ достигает максимума (равного 1) в единственной точке $u = 1/2$.

Вернёмся к нашей задаче: число последовательностей длины $n$, у которыхча-
стота единиц больше $(1/2 + \epsilon)$, не превосходит poly$(n)2^{H(1/2+\epsilon, 1/2-\epsilon)n}$, то есть не
превосходит $2^{cn+o(n)}$, где $c$ — некоторая константа, меньшая единицы (зависящая
от $\epsilon$). Тем самым доля таких последовательностей экспоненциально убывает с ро-
стом $n$. Точно такую же долю составляют последовательности, у которых доля
единиц меньше $(1/2 - \epsilon)$.
Подведём промежуточный итог. Для любого фиксированного $\varepsilon > 0$ мы доказали такое утверждение:

**Лемма.** Для последовательностей длины $n$, у которых частота единиц отклоняется от $1/2$ более чем на $\varepsilon$, среди всех последовательностей длины $n$ не превосходит $\delta_n$, где $\delta_n$ экспоненциально убывает с ростом $n$.

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

Мы хотим доказать, что множество $A_{1/2}$ тех последовательностей, у которых предел частоты единиц в начальных отрезках равен $1/2$, имеет меру 1. Другими словами, мы хотим показать, что его дополнение (обозначим его $B$) является нулевым множеством.

По определению предела $B$ есть объединение по всем $\varepsilon > 0$ множеств $B_\varepsilon$, где $B_\varepsilon$ есть множество тех последовательностей, у которых частота единиц бесконечное число раз бывает больше $1/2 + \varepsilon$ или меньше $1/2 - \varepsilon$.

Очевидно, достаточно рассматривать счётное число различных значений $\varepsilon$ (скажем, только рациональные), а счётное объединение нулевых множеств есть нулевое множество. Осталось доказать, таким образом, что множество $B_\varepsilon$ является нулевым при любом фиксированном $\varepsilon$.

Множество $B_\varepsilon$ состоит из тех последовательностей, у которых есть сколь угодно длинные плохие начальные отрезки (если считать плохим двоичное слово, в котором частота единиц отличается от $1/2$ более чем на $\varepsilon$). Поэтому при любом $N$ множество $B_\varepsilon$ покрывается интервалами вида $\Omega_x$, если взять все плохие $x$ длины $N$ и более. Но суммарная (равномерная) мера всех этих интервалов не превосходит

$$ \delta_N + \delta_{N+1} + \delta_{N+2} + \dots, $$

и эта сумма может быть сделана сколь угодно малой, так как ряд $\Sigma_i \delta_i$ сходится.

(Это рассуждение называется в теории вероятностей леммой Бореля – Кантелли. В общем виде эта лемма гласит, что если сумма мер множеств $A_0, A_1, \dots$ конечна, то множество тех точек, которые принадлежат бесконечно многим множествам $A_i$, является нулевым.) ►

Оценить число плохих слов длины $n$ можно и не используя формулы Стирлинга. Будем рассматривать плохие слова, у которых частоты слишком велики (больше $1/2 + \varepsilon$). Рассмотрим на множестве всех слов данной длины $n$ два распределения вероятностей. Первое из них (назовём его $L$) — равномерное: все слова имеют вероятность $2^{-n}$. Второе (назовём его $S$) отдаёт предпочтение единицам и соответствует $n$ независимым бросаниям монеты, у которой вероятность единицы есть $p = 1/2 + \varepsilon$. При этом вероятность слова из $i$ нулей и $v$ единиц равна $q^i p^v$ (где $q = 1/2 - \varepsilon$ — вероятность нуля). Чем больше в слове $x$ единиц, тем больше отношение вероятностей $S(x)/L(x)$. Легко подсчитать, что для всех плохих слов это отношение не меньше $2^n/2^H(p,q)^n$, и потому суммарная $L$-мера всех
### 3.3. Эффективно нулевые множества

Пусть фиксирована некоторая мера на пространстве Ω; меру интервала Ω_х мы обозначаем $p(x)$.

Говорят, что множество $A \subset \Omega$ является эффективно нулевым (по данной мере), если по любому $\varepsilon > 0$ можно эффективно указать покрытие множества A последовательностью интервалов, суммарная мера которых не превосходит $\varepsilon$.

Это определение требует некоторых уточнений. Во-первых, мы будем рассматривать не все действительные $\varepsilon$, а только рациональные (иначе непонятно, в какой форме алгоритму можно подать на вход число $\varepsilon$). С другой стороны, надо уточнить, в какой форме алгоритм выдаёт последовательность интервалов. Вот одно из возможных уточнений:

**Определение.** Множество $A \subset \Omega$ называется эффективно нулевым (по данной мере), если существует вычислимая функция х двух аргументов (первый — положительное рациональное число, второй — натуральное число), значениями которой являются двоичные слова, причём

1) $A \subset \Omega_{x(\varepsilon,0)} \cup \Omega_{x(\varepsilon,1)} \cup \Omega_{x(\varepsilon,2)} \dots$;

2) $p(x(\varepsilon, 0)) + p(x(\varepsilon, 1)) + p(x(\varepsilon, 2)) + \dots \le \varepsilon$

при любом рациональном $\varepsilon > 0$. При этом мы не требуем, чтобы функция х была всюду определена; если $x(\varepsilon, i)$ не определено, то соответствующий член (в обоих условиях) пропускается.

**68** Покажите, что определение не изменится, если предполагать, что алгоритм получает на вход рациональное $\varepsilon > 0$, а на выходе перечисляет некоторое множество двоичных слов (печатая их одно за другим с произвольными перерывами), которые образуют покрытие интервалами с суммарной мерой (мерой объединения) не больше $\varepsilon$. (Обратите внимание, что суммарная мера может быть меньше суммы мер интервалов, если они пересекаются.)

**69** Покажите, что определение не изменится, если мы будем рассматривать не все рациональные $\varepsilon$, а только числа вида $2^{-k}$ при натуральных k. Покажите, что определение не изменится, если заменить знак $\le$ во втором условии на строгое неравенство.

**70** Покажите, что определение не изменится, если требовать, чтобы для какого $\varepsilon$ функция $i \mapsto x(\varepsilon, i)$ была бы определена на некотором начальном отрезке натурального ряда (возможно, бесконечном).

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

Приведём несколько примеров эффективно нулевых множеств относительно равномерной меры на Ω.

Рассмотрим одноэлементное множество, единственным элементом которого является последовательность из одних нулей. Оно является эффективно нулевым:
чтобы найти покрытие из интервалов суммарной меры меньше данного $\varepsilon > 0$, возьмём натуральное $k$, для которого $2^{-k} < \varepsilon$, и покрытие из единственного интервала $\Omega_{00...0}$ (в индексе стоит слово из $k$ нулей).

Формально говоря, $x(\varepsilon, 0) = 0^k$, где $0^k$ обозначает последовательность из $k$ нулей, а $k$ — наименьшее натуральное число, для которого $2^{-k} < \varepsilon$. Значения $x(\varepsilon, i)$ при $i \neq 0$ не определены.

В этом примере последовательность из одних нулей можно заменить на любую вычислимую последовательность нулей и единиц; нужно только вместо $0^k$ рассмотреть начальный отрезок этой последовательности длины $k$.

Но вычислимость существенна, как показывает следующая задача:

**72** Показайте, что существует последовательность $\omega \in \Omega$, для которой одноэлементное множество $\{\omega\}$ не является эффективно нулевым. [Указание. Рассмотрим все вычислимые функции $x$, удовлетворяющие второму условию из определения эффективно нулевого множества. Их счётное число. Для каждой из них рассмотрим наибольшее множество $A$, удовлетворяющее первому условию этого определения (пересечение покрытий по всем $\varepsilon$). Это множество будет (эффективно) нулевым. Объединение счётного числа таких множеств будет нулевым, и потому можно взять $\omega$ вне этого объединения.

**Замечание.** Утверждение этой задачи очевидно следует из теоремы Мартин-Лёфа о наибольшем эффективно нулевом множестве (теорема 28, с. 73), которую мы доказем в этом разделе (и приведённое выше указание к задаче использует по существу тот же метод доказательства). Мы увидим, что множество $\{\omega\}$ является эффективно нулевым тогда и только тогда, когда последовательность $\omega$ «не случайна в смысле Мартин-Лёфа».

Легко построить и невычислимую последовательность $\omega$, для которой множество $\{\omega\}$ является эффективно нулевым. Возьмём любую последовательность $\omega = 0?0?0?0...$ (нули чередуются с произвольными цифрами). Покажем, что множество $\{\omega\}$ является эффективно нулевым.

В самом деле, чтобы построить покрытие с суммарной мерой $2^{-n}$, можно взять все конечные слова длины $2n$, в которых $n$ нулей чередуется с $n$ произвольными цифрами (как в $\omega$). Таких слов $2^n$, а мера каждого интервала $2^{-2n}$, поэтому суммарная мера равна $2^{-n}$.

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

Возвращаясь к определению эффективно нулевого множества, заметим, что требования в его определении можно разделить в следующем смысле. Будем называть вычислимую функцию $x$ корректной, если она удовлетворяет требованию (2) (про сумму мер). Напомним, что требование (1) определения означает, что множество $A$ при любом рациональном $\varepsilon > 0$ лежит в объединении множеств

$$ \Omega_{x(\varepsilon, 0)} \cup \Omega_{x(\varepsilon, 1)} \cup \Omega_{x(\varepsilon, 2)} \dots $$
Таким образом, корректная функция х «обслуживает» все множества, лежащие внутри

$$ \bigcap_{\varepsilon>0} (\Omega_{x(\varepsilon,0)} \cup \Omega_{x(\varepsilon,1)} \cup \Omega_{x(\varepsilon,2)} \dots) = \bigcap_{\varepsilon>0} \bigcup_{i} \Omega_{x(\varepsilon,i)}. $$

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

Прежде чем сформулировать теорему Мартин-Лёфа, дадим определение вычислимой меры на пространстве Ω.

Действительное число $\alpha$ называют вычислимым, если существует алгоритм, вычисляющий приближения к $\alpha$ с любой заданной точностью $\varepsilon > 0$. Точнее говоря, $\alpha$ вычислимо, если найдётся вычислимая функция $\varepsilon \mapsto a(\varepsilon)$, определённая на всех положительных рациональных числах и принимающая рациональные значения, для которой

$$ |\alpha - a(\varepsilon)| < \varepsilon $$

при любом рациональном $\varepsilon > 0$.

**73** Покажите, что определение не изменится, если дополнительно потребовать, чтобы выдаваемые приближения были «приближениями с недостатком», то есть чтобы $a(\varepsilon) < \alpha$ для всех $\varepsilon$. [Указание: потеряв вдвое в точности, можно любое приближение превратить в приближение с недостатком (или с избытком).]

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

**75** Покажите, что числа $e$ (основание натуральных логарифмов) и $\pi$ вычислимы.

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

Мера $\mu$ на пространстве $\Omega$ называется вычислимой, если меры всех интервалов являются вычислимыми действительными числами, и, более того, алгоритм приближения к $\mu(\Omega_x)$ можно эффективно указать по х. Более формально:

**Определение.** Мера $\mu$ на пространстве $\Omega$ называется вычислимой, если существует вычислимая функция $\langle x, \varepsilon \rangle \mapsto a(x, \varepsilon)$, определённая для всех слов х и всех положительных рациональных чисел $\varepsilon$, для которой

$$ |\mu(\Omega_x) - a(x, \varepsilon)| < \varepsilon $$

для любых х и $\varepsilon$.

Вообще говоря, это определение не предполагает, что мера всего пространства равна единице, но на практике оно нам понадобится только для таких $\mu$ (то есть для распределений вероятностей).
**Теорема 28 (Мартин-Лёфа).** Пусть $\mu$ — вычислимая мера на $\Omega$. Тогда существоует наибольшее по включению эффективно нулевое относительно меры $\mu$ множество.

Переформулировка: объединение всех эффективно нулевых (относительно данной вычислимой меры) множеств является эффективно нулевым множеством.

► Как мы говорили, каждой корректной функции $x$ соответствует эффективно нулевое множество. Таких множеств счётное число, и любое эффективно нулевое множество содержится в одном из них, поэтому мы немедленно заключаем, что объединение всех эффективно нулевых множеств является нулевым множеством.

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

По техническим причинам нам будет удобно изменить определение корректной функции. Именно, мы будем называть вычислимую функцию $x$ корректной, если всякая конечная частичная сумма ряда

$$p(x(\epsilon, 0)) + p(x(\epsilon, 1)) + p(x(\epsilon, 2)) + \dots$$

строго меньше $\epsilon$. (Напомним, что $p(x) = \mu(\Omega_x)$.) Это требование чуть более сильное (если все частичные суммы ряда строго меньше $\epsilon$, то его сумма не превосходит $\epsilon$, но не наоборот). Но легко понять, что определение эффективно нулевого множества не изменится, так как там всегда можно заменить $\epsilon$, скажем, на $\epsilon/2$.

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

Следующая лемма утверждает, что можно эффективно перечислять все корректные функции $x$.

**Лемма.** Существует вычислимая (частичная) функция трёх аргументов

$$\langle q, \epsilon, i \rangle \mapsto X(q, \epsilon, i)$$

($q$ и $i$ — натуральные числа, $\epsilon$ — положительное рациональное число), которая при любом фиксированном $q$ даёт корректную функцию $X_q$ двух аргументов и все корректные (вычислимые) функции двух аргументов могут быть получены таким образом.

**Доказательство.** Расположим все программы для функций двух аргументов (корректных и некорректных) в вычислимую последовательность, и «программой номер $q$» будем называть $q$-й член этой последовательности.

Мы определим $X(q, \epsilon, i)$ как результат применения программы номер $q$ к входам $\epsilon, i$, если выполнены некоторые условия; если нет, то $X(q, \epsilon, i)$ не определено. Условия гарантируют, что все $X_q$ корректны и что корректные функции остались нетронутыми.

Чтобы вычислить $X(q, \epsilon, i)$, мы параллельно запускаем программу номер $q$ на всех парах

$$(\epsilon, 0), (\epsilon, 1), \dots,$$
сначала делая один шаг первого вычисления, потом два шага первых двух вычислений и т. д. Как только вычисление на паре $(\epsilon, i)$ заканчивается и выдаёт некоторое слово в качестве результата, мы начинаем проверку корректности. Проверка эта состоит в том, что для всех обнаруженных слов $z$ мы начинаем всё с большей и большей точностью вычислять соответствующие значения $p(z)$, пока не убедимся, что сумма этих значений меньше $\epsilon$. Точнее говоря, проверка заканчивается успешно, когда мы обнаруживаем, что сумма текущих приближений меньше $\epsilon$ на величину, меньшую суммарной погрешности приближений к $p(z)$. Здесь важно, что мера $\mu$ вычислима, так что мы можем вычислять приближения к $p(z)$ с любой заданной точностью для любого слова $z$.

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

Теперь $X(q, \epsilon, i)$ определяется как результат применения программы номер $q$ к входу $(\epsilon, i)$, если этот результат был получен и прошёл проверку корректности в ходе описанного нами процесса.

Если программа номер $q$ на самом деле вычисляет корректную функцию, то все тесты корректности (успешно) завершатся и $X_q$ будет совпадать с этой функцией.

С другой стороны, во всех случаях функция $X_q$ окажется корректной. В самом деле, из последовательности обнаруживаемых значений $q$-й программы на парах $(\epsilon, 0), (\epsilon, 1), \dots$ будет оставлен некоторый начальный (в порядке обнаружения) отрезок, где суммы мер ещё меньше $\epsilon$; для всех следующих пар проверка никогда не кончится.

Лемма доказана.

**77** Объясните, почему нам понадобилось изменить определение корректности: где не проходит доказательство при старом определении? [Указание: если ряд содержит конечное число ненулевых членов, сумма которых в точности равна $\epsilon$, мы этого никогда не узнаем.]

Продолжаем доказательство теоремы Мартин-Лёфа. Пусть $X$ — функция из леммы. При каждом $q = 0, 1, 2, \dots$ рассмотрим эффективно нулевое множество $Z_q$, соответствующее корректной функции $X_q$. Мы уже знаем, что всякое эффективно нулевое множество содержится в одном из $Z_q$; остаётся доказать, что объединение $Z_0 \cup Z_1 \cup \dots$ является эффективно нулевым множеством.

Это делается по той же схеме, что и доказательство теоремы о счётном объединении нулевых множеств. Именно, чтобы найти покрытие суммарной меры не больше $\epsilon$ для $\cup_q Z_q$, мы объединим покрытие размера $\epsilon/2$ для $Z_0$, покрытие размера $\epsilon/4$ для $Z_1$, и так далее.

Формально говоря, мы рассматриваем функцию $x(\epsilon, i)$, определённую так:

$$x(\epsilon, [q, k]) = X(q, \epsilon/2^{q+1}, k),$$
где $[q, k]$ обозначает номер пары $q, k$ при каком-то взаимно однозначном кодировании пар натуральных чисел натуральными числами. (Это кодирование должно быть вычислимым, но в остальном может быть произвольным.) ►

Теперь мы можем дать определение случайной по Мартин-Лёфу последовательности. Пусть фиксирована некоторая вычислимая мера $\mu$ на пространстве $\Omega$.

**Определение.** Последовательность $\omega$ называется случайной по Мартин-Лёфу относительно меры $\mu$, если она не содержится в наибольшем эффективно нулевом множестве относительно этой меры.

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

Ещё одна переформулировка: последовательность $\omega$ случайна по Мартин-Лёфу, если множество $\{\omega\}$ не является эффективно нулевым.

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

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

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

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

Следующее утверждение, несмотря на всю его очевидность, полезно осознать (и прочувствовать его парадоксальность):

**Теорема 29.** Множество $A \subset \Omega$ является эффективно нулевым тогда и только тогда, когда все его элементы не случайны по Мартин-Лёфу («нетипичны»).
В частности, множество всех нетипичных последовательностей является (наи-
большим) эффективно нулевым множеством, а множество всех типических после-
довательностей имеет меру 1.

◀ В самом деле, элементы эффективно нулевого множества нетипичны по опре-
делению; с другой стороны, если все элементы множества А нетипичны, то А
содержится в наибольшем эффективно нулевом множестве и потому является эф-
фективно нулевым. ▶

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

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

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

**Теорема 30.** Множество всех вычислимых последовательностей нулей и единиц является эффективно нулевым подмножеством Ω относительно равномерной меры.

Любопытно отметить, что по существу это наблюдение было сделано ещё до
Мартин-Лёфа, при изучении конструктивного варианта математического анализа
(«пример Заславского» [192]). Там речь шла о действительных числах, а не о по-
следовательностях нулей и единиц.

В следующем разделе мы продолжим обсуждение свойств последовательностей, МЛ-случайных по равномерной мере. А сейчас мы приведём любопытный критерий МЛ-случайности последовательности, приведённый со ссылкой на Соловея в [24].

**Теорема 31.** Последовательность $\omega$ не МЛ-случайна по вычислимой мере $\mu$ тогда и только тогда, когда существует вычислимая последовательность интервалов с конечной суммой мер, покрывающая эту последовательность бесконечное число раз, то есть вычислимая последовательность слов $x_0, x_1, x_2, \dots$, для которой

$$
\sum_{i} \mu(\Omega_{x_i}) < \infty
$$

и $\omega \in \Omega_{x_i}$ при бесконечно многих $i$.

◀ Если последовательность $\omega$ не МЛ-случайна, то множество $\{\omega\}$ имеет по-
крытия с суммой мер не больше $\varepsilon$ для любого положительного рационального $\varepsilon$.
Соединим такие покрытия для $\varepsilon = 1, 1/2, 1/4, 1/8, \dots$. Соединённое покрытие име-
ет сумму мер не больше 2 и покрывает $\omega$ бесконечно много раз (на каждом уровне
хотя бы по разу).

Напротив, пусть есть некоторое покрытие точки $\omega$ интервалами, соответствую-
щими словам $x_0, x_1, x_2, \dots$, и сумма мер этих интервалов не превосходит какой-то
границы $c$, которую удобно считать рациональным числом. Чтобы найти покрытие точки $\omega$ с суммой не больше $\varepsilon$, рассмотрим множество тех точек из $\Omega$, которые покрыты не менее $N$ раз, где целое положительное $N$ выбрано так, чтобы $c/N$ было меньше $\varepsilon$. Легко понять, что это множество ($N$-кратно покрытые точки) представимо в виде объединения непересекающихся интервалов, и эти интервалы можно перечислять алгоритмически, глядя на последовательность $x_0, x_1, x_2, ...$ и зная $N$. Тем самым множество $\{\omega\}$ является эффективно нулевым, а последовательность $\omega$ — неслучайной по Мартин-Лёфу. ►

**Замечание.** Эта теорема является «конструктивизацией» леммы Бореля – Кантелли (если сумма мер множеств $A_0, A_1, ...$ конечна, то множество точек, принадлежащих бесконечно многим из $A_i$, является нулевым), и приведённое нами рассуждение является конструктивизацией доказательства леммы Бореля – Кантелли. Однако тут нужна осторожность: для конструктивизации годится не всякое доказательство. Обычное доказательство этой леммы (ряд сходится, значит, хвосты его стремятся к нулю и покрывают интересующее нас множество) не годится, так как мы не умеем по $\varepsilon$ эффективно находить хвост, меньший $\varepsilon$.

При определении случайности по мере мы предполагали её вычислимость, по скольку эта вычислимость использовалась в доказательстве существования максимального эффективно нулевого множества. В принципе можно обойтись и без максимального множества, сказав, что случайными (по произвольной мере $\mu$ на $\Omega$) будут те последовательности, которые не лежат ни в каком нулевом множестве. Для этого понятия случайности Б. Кьёс-Хансен предложил термин *Hippocratic randomness* [58] (а П. Гач — более нейтральный термин «слепая (безоракульная) случайность», *blind randomness*). Это не единственный возможный вариант определения случайности относительно невычислимых мер: отметим (без подробностей), что можно использовать также *равномерные тесты случайности* (uniform randomness tests, подход Левина – Гача, см. обзор [8]).

**78** Докажите, что для перечислимой сверху меры существует максимальное эффективно нулевое множество. (При этом мы не предполагаем, что мера всего пространства равна 1; в последнем случае из перечислимости сверху следует вычислимость.)

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

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

**80** Приведите пример невычислимой меры, для которой существует наибольшее эффективно нулевое множество. [Указание: можно рассмотреть невычислимую
меру, настолько близкую к равномерной, чтобы меры всех множеств отличались не больше чем в константу раз.]

### 3.4. Свойства случайных по Мартин-Лёфу последовательностей

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

**Теорема 32.** Множество последовательностей нулей и единиц, для которых $1/2$ не является пределом последовательности частот, является эффективно нулевым по равномерной мере.

◀ Достаточно показать, что при любом рациональном $ε > 0$ множество тех последовательностей, у которых частота бесконечное число раз становится больше $1/2 + ε$ (или меньше $1/2 - ε$), является эффективно нулевым. Для этого заметим, что оценка меры, приведённая при доказательстве закона больших чисел в предыдущем разделе (теорема 27, с. 66), была эффективной: покрытие состояло из продолжений всех достаточно длинных слов с большим отклонением частоты, а его мера эффективно оценивалась сверху остаточным членом в сумме бесконечно убывающей геометрической прогрессии. ▶

Переформулируем доказанное утверждение в терминах МЛ-случайных последовательностей:

**Теорема 33.** Пусть $ω = ω_0ω_1...$ — случайная в смысле Мартин-Лёфа последовательность относительно равномерной меры. Тогда

$$ \lim_{n \to \infty} \frac{\omega_0 + \omega_1 + \dots + \omega_{n-1}}{n} = \frac{1}{2}. $$

Аналогичное утверждение справедливо и для неравномерных бернуллиевых мер. Пусть даны положительные числа $p, q$, для которых $p + q = 1$, причём $p$ и $q$ вычислимы. Рассмотрим бернуллиеву меру с параметрами $q, p$ (соответствующую последовательности независимых испытаний с вероятностью успеха $p$, см. с. 66). Легко проверить, что эта мера вычислима (поскольку вычислимы $p$ и $q$).

**Теорема 34.** Любая МЛ-случайная относительно бернуллиевой меры с вычислимыми параметрами $q, p$ последовательность имеет предел частот, равный $p$.

◀ В самом деле, оценка вероятностей последовательностей с большими уклонениями частот от $p$ (производимая с помощью сравнения меры с другой мерой, в которой $p$ сдвинуто, см. задачу 67, с. 69), даёт явную оценку и покрытие, поэтому получается эффективно нулевое множество. ▶

Ещё несколько свойств типичности (МЛ-случайности) по равномерной мере:

**Теорема 35.** Пусть $ω$ — типическая по равномерной мере последовательность. Тогда последовательность полученная из $ω$ удалением, добавлением или изменением конечного числа членов, также является типической.
Достаточно доказать, что дописывание в начало последовательности нуля или единицы, а также удаление первого её члена не сказывается на типичности.

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

С другой стороны, если у всех слов, задающих интервалы покрытия, удалить первый бит, то получится семейство интервалов вдвое большей меры, покрывающее последовательность $\omega'$, получающуюся удалением из $\omega$ первого бита. Значит, $\omega'$ не типична. ►

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

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

**82** Пусть $n_0, n_1, n_2, \dots$ — вычислимая последовательность различных нату-ральных чисел ($n_i \neq n_j$ при $i \neq j$). Покажите, что если последовательность $\omega = \omega_0\omega_1\omega_2\dots$ типична, то и её подпоследовательность

$$ \omega|n = \omega_{n_0} \omega_{n_1} \omega_{n_2} \dots $$

типична. [Указание. Из каждого интервала $\Omega_x$ в покрытии для $\omega|n$ получается конечное семейство интервалов, у которых члены с номерами $n_0, n_1, \dots, n_{i-1}$ сов-впадают с битами слова $x$ (здесь $i$ — длина слова $x$), а остальные биты любые. Общая мера этих интервалов равна мере интервала $\Omega_x$.]

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

**83** Пусть последовательность $\omega$ типична (МЛ-случайна) по равномерной мере. Разделим её на блоки по две цифры и заменим блоки 00 на нули, а блоки 01, 10 и 11 — на единицы. Докажите, что полученная последовательность типична по бернулиевой мере с параметрами $1/4, 3/4$. [Указание. Описанное преобразование задаёт отображение $F: \Omega \to \Omega$. Прообраз любого открытого множества $U$ при этом открыт, и равномерная мера этого прообраза равна $(1/4, 3/4)$-мере множества $U$.]

**84** (Продолжение) Докажите, что любая типическая по $(1/4, 3/4)$-мере последовательность может быть получена описанным способом из последовательности, типической по равномерной мере.

[Указание. Для любого открытого множества $B \subset \Omega$ рассмотрим множество $B'$ всех тех последовательностей $\omega$, у которых $F^{-1}(\{\omega\}) \subset B$ (те последовательности, которые не имеют прообраза вне $B$, или дополнение к образу дополнения $B$). Образ компактного множества компактен, поэтому $B'$ открыто. Проверьте, что