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

## Простые или заранее указанные?

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

Один из возможных путей таков: можно сказать, что мы отбрасываем гипотезу, если мы наблюдаем весьма маловероятное событие, указанное заранее (до начала эксперимента). Но тогда возникает такой вопрос. Представим себе, что мы бросали монету и получили последовательность, которая на первый взгляд показалась нам случайной. Пришедший коллега, однако, обратил наше внимание на то, что если смотреть на биты через два на третий, то нули и единицы чередуются (??0??1??0??1...). Будем ли мы после этого по-прежнему считать последовательность случайной? Видимо нет: хотя до эксперимента такая закономерность нам в голову не приходила, но она настолько проста, что она могла бы прийти. Можно даже так сказать: рассмотрим объединение всех простых событий ничтожной вероятности (выбрав границу между простым и сложным так, чтобы это объединение оставалось очень маловероятным). Теперь мы можем утверждать, что это событие рассматривалось заранее (по крайней мере теми, кто прочёл этот раздел книги).

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

Короче говоря, мы можем заменить одно расплывчатое требование («быть простым») на другое («быть известным заранее»). Вот как описывает ситуацию Борель ([12], с. 77–78):

> «Скажем несколько слов о мысли Бертрана по поводу равностороннего треугольника, который могли бы образовать три звезды; она связана с вопросом о круглом числе. Если рассматривать число, взятое нaudачу между 1 000 000 и 2 000 000, то вероятность, что оно равняется 1342517, равна одной миллионной; вероятность, что оно равняется
тие «число орлов при 1 000 000 бросаний отличается от 500 000 больше чем на 100 000» имеет простое описание и ничтожно малую вероятность. Поэтому мы отвергаем гипотезу честной монеты, наблюдая такое явление (а также не опасаемся такого события всерьёз, если верим в честность монеты).

## Динамические и статистические закономерности

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

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

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

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

## Будут ли сложными встречающиеся в природе последовательности?

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

Более наглядная формулировка того же самого вопроса такова. Давайте бро- сим (самую что ни на есть честную) монету миллион раз. Полученную последова- тельность нулей и единиц попробуем сжать с помощью какого-то из практически используемых компрессоров, скажем, с помощью программы gzip. (Для этого её надо вначале разбить на восьмибитовые байты.) Можно быть уверенным, что мы не получим сжатия больше чем на 1%, сколько раз ни повторяй этот опыт. В самом деле, такая степень сжатия возможна лишь для $2^{-10000}$-доли всех последователь- ностей.

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

Чтобы осознать ситуацию, полезно её юпростить. Представим себе, что время у нас дискретно, фазовое пространство представляет собой отрезок $[0, 1]$, а динами- ческий закон (преобразование фазового пространства) задаётся формулой

$$x \mapsto T(x) = \text{if } 2x < 1 \text{ then } 2x \text{ else } 2x - 1.$$

Мы получаем последовательность состояний $x_0$ (начальное условие), $x_1 = T(x_0)$, $x_2 = T(x_1)$ и так далее. На каждом шаге мы замечаем, в какую половину отрезка попали и пишем 0, если точка будет в левой половине, и 1, если в правой.

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

Что же получается? Должны ли мы к динамическим законам добавить ещё один закон природы, говорящий о случайности ($= несжимаемости$) начальных условий? («Мир был создан в алгоритмически случайном состоянии», если говорить фило- софски торжественно.) Ведь алгоритмические преобразования (соответствующие динамическим законам) не могут увеличивать сложность, поэтому если объекты большой сложности существуют в детерминированном (как мы временно предло- гаем в этом обсуждении) мире, то они должны быть там с самого начала. (От- метим, что не удастся объяснить случайность тем, что мы наблюдаем состояние
мира в случайной точке в случайное время: количество битов, нужных для описания времени и места со всей мыслимой точностью, недостаточно для того, чтобы объяснить появление несжимаемых слов длиной $10^6$.)

«Бог не играет в кости», говорил Эйнштейн? Что же, вместо этого мы должны предположить, что он заранее снабдил мир запасом концентрированной случайности при создании?

## Случайность как незнание: генераторы псевдослучайных битов

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

Мы имеем в виду понятие генератора псевдослучайных битов (в смысле Блома, Микэли и Яо; об этом центральном понятии современной сложной криптографии можно прочесть, например, в книге Голдрайха [48]). Существование таких генераторов не доказано, но следует из некоторых сложных предположений (существование односторонних функций), которые многие считают правдоподобными.

Объясним неформально, о чём идёт речь. Представим себе простую и быструю (полиномиальную) процедуру, которая берёт «зародыш» случайности (seed в англоязычной литературе), двоичное слово сравнительно небольшой длины, скажем, из тысячи битов. Эта процедура преобразует его в гораздо более длинное слово, скажем, в последовательность из $10^{10}$ битов. Естественно, что получившееся слово имеет малую сложность, поскольку оно может быть задано указанием самой процедуры (которая проста по нашему предположению) и зародыша. Более того, даже и сложность с ограничением на время мала, поскольку преобразование предполагается легко вычислимым.

Тем не менее, если нам покажут такое слово из $10^{10}$ битов, то мы можем и не отличить его от по-настоящему случайной последовательности. Это звучит падоксально: мы только что сказали, что колмогоровская сложность такого слова мала, а для случайных слов она близка к длине, в каком же смысле мы говорим о неотличимости?

Смысл этот вполне практический — мы бы сразу согласились с тем, что это слово имеет малую сложность и потому нетипично, если бы нам показали зародыш. Но если нам дали это слово длины $10^{10}$ просто так, то перебрать все $2^{1000}$ возможных зародышей выше человеческих сил (даже если иметь в виду всё человечество со всеми его компьютерами), и никто так никогда и не узнает, что оно на самом деле было малой сложности.
Это соображение показывает, что в принципе мир может управляться простыми динамическими законами с достаточно простыми начальными условиями (описываемыми, скажем, тысячами битов). В таком мире «истинной» случайности не существует, и любая последовательность из $10^6$ бросаний монеты (уже случившаяся, или которая случится в будущем) будет сильно сжимаемой. Тем не менее, вычислительно ограниченный наблюдатель (вроде нас самих) может никогда этого и не обнаружить.

## Отступление: термодинамика

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

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

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

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

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

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

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

## Ещё одно отступление: квантовая механика

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

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

Интерпретация квадрата модуля амплитуды как вероятности (ожидаемой ча-
стоты) может быть тогда получена тем же способом, как и раньше. Представим
себе систему, состоящую из N идентичных независимых систем, каждая из кото-
рых может находиться в двух состояниях, причём амплитуда состояния 1 равна
z (в каждой из систем). Точнее говоря, состояние всей большой системы равно
тензорному произведению описанных состояний отдельных систем. В этом случае
амплитуда события «число единиц среди состояний сильно отличается от N|z|²»
(квадрат модуля проекции указанного состояния на описанное подпространство)
мала — это по существу тот же самый закон больших чисел.

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

# Четыре алгоритмических лица случайности

В. А. Успенский<fnref n="1" />

## Введение

Если кто-либо скажет нам, что он подбросил «честную» монету двадцать раз и, обозначив герб единицей, а решётку — нулём, получил такой результат:

10001011101111010000 (I)

или такой:

01111011001101110001, (II)

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

00000000000000000000 (III)

или таким:

01010101010101010101, (IV)

мы будем поражены и вообще не поверим или же усомнимся в корректности эксперимента. Возникает вопрос: почему?

По-видимому, цепочки (I) и (II) воспринимаются как случайные, а цепочки (III) и (IV) — как неслучайные.

Но что означают слова «воспринимается как случайная»? Классическая теория вероятностей не даёт ответа на этот важный вопрос. Не столь редко можно услышать следующее объяснение: вероятность каждой из цепочек (III) и (IV) слишком мала, она равна $2^{-20}$, что меньше одной миллионной. Но ведь ровно такую же вероятность имеют цепочки (I) и (II)!

<footnote n="1">¹Это приложение воспроизводит (с некоторыми изменениями) текст брошоры «Четыре алгоритмических лица случайности» (2-е изд., испр. — М.: МЦНМО, 2009; первое издание вышло в 2006 г.), написанной по материалам лекции, прочитанной автором брошоры, В. А. Успенским, 23 июля 2005 года в летней школе «Современная математика» в Дубне. Терминология и обозначения, использованные в брошюре, несколько отличаются от использованных в остальной части книги; эти различия отмечены в подстрочных примечаниях.</footnote>
Сделаем три важных замечания.

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

* Во-вторых, говорить о случайности имеет смысл лишь в применении к очень длинным цепочкам. Бессмысленно спрашивать, которая из цепочек 00, 01, 10, 11 более случайна, чем другие.

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

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

Нам будут полезны некоторые термины и обозначения.

Всякая конечная цепочка $\langle i_1, \dots, i_n \rangle$ нулей и единиц называется также двоичным словом, а число $n$ — длиной этого слова. Длина слова $x$ обозначается так: $|x|$.<fnref n="1" /> Длина слова может быть равна нулю; слово длины нуль ничего не содержит и называется пустым. Пустое слово обозначается буквой $\Lambda$.

Множество всех двоичных слов обозначается буквой $\Xi$. Множество всех последовательностей нулей и единиц обозначается буквой $\Omega$.

Для последовательности $\langle a_1, a_2, \dots \rangle$ каждое из двоичных слов $\langle a_1, a_2, \dots, a_n \rangle$ является её началом. Пусть $x \in \Xi$ — двоичное слово. Множество всех тех последовательностей из $\Omega$, для которых $x$ служит началом, обозначим через $\Omega_x$. Каждое

<footnote n="1">¹В основном тексте книги длина слова $x$ обозначалась $l(x)$.</footnote>
множество вида $\Omega_x$, где $x \in \Xi$, принято называть шаром. Шару $\Omega_x$ приписывается его объём$^1 v(x)$, равный $2^{-|x|}$.

Содержательно, каждую последовательность из $\Omega$ мы рассматриваем как серию результатов бросаний монеты. Ещё раз подчеркнём, что для наглядности мы ограничиваемся на первых порах ситуацией, когда результаты всех бросаний равновероятны. На математическом языке это означает, что на $\Omega$ задано так называемое равномерное распределение вероятностей, а это, в свою очередь, означает следующее: для каждого шара вероятность того, что случайно выбранная последовательность из $\Omega$ попадёт в этот шар, равна объёму этого шара.

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

Чтобы найти требуемое определение, обычно поступают так: формулируют некое характеристическое свойство, которым обладают случайные (в неформальном, интуитивном смысле) последовательности, а затем последовательности, обладающие этим свойством, и объявляют — по определению — случайными.

Какими же свойствами обладает случайная последовательность нулей и единиц?

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

Во-вторых, она **хаотична**. Это означает, что она сложно устроена и не может иметь разумного описания. Психологическому эксперименту, с которого мы начали, Колмогоров дал такое объяснение. Цепочки (I) и (II) потому воспринимаются как случайные, что они сложны, их устройство нельзя коротко описать. А вот цепочки (III) и (IV) имеют простое, легко описываемое устройство.

В-третьих, она **типична**. Это означает, что она принадлежит любому разумному большинству.

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

Конечно, слово «разумный», встречающееся в объяснениях перечисленных чётырёх свойств, нуждается в уточнении. Теория алгоритмов как раз и предлагает такие уточнения, наполняя это слово точным смыслом — своим для каждого

<footnote n="1">¹В основном тексте книги мы говорили об интервалах и их длинах.</footnote>
из наших четырёх свойств. Тем самым, возникают четыре алгоритмических свойства: частотная устойчивость, хаотичность, типичность, непредсказуемость. Каждое из них представляет своё собственное алгоритмическое лицо случайности, и каждое из них, с большими или меньшими основаниями, может претендовать на роль строгого математического определения понятия случайности. Можно сказать и так: возникают четыре точно очерченных класса последовательностей, каждый из которых претендует на то, чтобы служить «истинным» классом случайных последовательностей; некоторые из этих претензий более оправданы, чем другие.

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

## Лицо первое: Частотоустойчивость и стохастичность

По-видимому, одним из первых поставил вопрос о том, что такое отдельно взятая случайная последовательность, замечательный немецкий математик Рихард фон Мизес в начале ХХ века — в 1919 г. Во всяком случае, именно он первым предложил сравнительно удачное (хотя и нестрогое) определение, послужившее отправной точкой для дальнейшего развития.

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

$$0, 1, 0, 1, 0, 1, 0, 1, \dots$$

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

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

Сам Мизес объяснял, какие последовательности следует считать допустимыми, в расплывчатых терминах. Первое уточнение предложил в 1940 г. американский
математик Алонзо Чёрч — один из создателей теории алгоритмов. Чёрч предложил, чтобы допустимые подпоследовательности строились на основе определённых алгоритмов. Последовательности, в которых устойчивость частот наблюдается во всех допустимых по Чёрчу подпоследовательностях, получили название стохастических по Чёрчу.<fnref n="1" /> Однако оказалось, что определение Чёрча слишком широко: существует, например, стохастическая по Чёрчу последовательность, перестающая быть таковой после вычислимой перестановки её членов.<fnref n="2" />

В 1963 г. Колмогоров усовершенствовал определение Чёрча, предложив более обширный класс допустимых алгоритмов отбора членов исходной последовательности в подпоследовательность и, тем самым, заведомо не меньший (а на деле более обширный) класс допустимых подпоследовательностей; в частности, колмогоровский алгоритм разрешает членам подпоследовательности иметь иной порядок следования, чем в исходной последовательности. Поэтому класс всех последовательностей, стохастических по Колмогорову (т. е. таких, у которых устойчивость частот наблюдается во всех допустимых по Колмогорову подпоследовательностях),<fnref n="3" /> является подклассом класса последовательностей, стохастических по Чёрчу, а на самом деле, даже строгим подклассом, т. е. не совпадающим с объемлющим классом. Для дальнейших ссылок класс всех последовательностей, стохастических по Колмогорову, обозначим буквой S.

Выяснилось, что класс S также слишком широк. Оказалось, например, что может быть построена такая стохастическая по Колмогорову последовательность, в каком начальном отрезке которой единиц больше, чем нулей; а это противоречит как интуиции, так и законам теории вероятностей (например, закону возвратности состояний при случайном блуждании).<fnref n="4" /> Таким образом, даже наиболее продвинутое из известных на сегодняшний день математически строгих уточнений идей Мизеса не даёт полного отражения интуитивного представления о случайности (хотя и это неполное отражение может оказаться полезным).

Для большей ясности приведём определения Чёрча и Колмогорова. Центральным для обоих определений является указание тех правил, согласно которым из членов рассматриваемой последовательности составляются допустимые подпоследовательности. Поскольку каждое такое правило производит отбор членов последовательности для включения их в допустимую подпоследовательность, сами эти правила принято называть допустимыми правилами отбора.<fnref n="5" />

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

<footnote n="1">¹В основном тексте книги они называются случайными по Мизесу – Чёрчу.</footnote>

<footnote n="2">²См. теорему 203(г) на с. 345.</footnote>

<footnote n="3">³В основном тексте они называются случайными по Мизесу – Колмогорову – Лавлэнду.</footnote>

<footnote n="4">⁴См. теорему 203(б) на с. 345.</footnote>

<footnote n="5">⁵В основном тексте они были названы допустимыми правилами выбора.</footnote>
ения подпоследовательности предписывает, во-первых, которую из карт надлежит
открыть и, во-вторых, следует или нет включать эту открываемую карту в под-
последовательность. Входом алгоритма служит информация о всех уже открытых
к этому моменту картах. Может случиться, что алгоритм отберёт лишь конечное
число членов исходной последовательности; в этом случае считается, что ника-
кой допустимой подпоследовательности не образовалось. (Напомним, что исходная
последовательность признаётся стохастической при наличии устойчивости частот
в любой её допустимой подпоследовательности.)

Переходим к более точному описанию.

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

Исследуемую на устойчивость последовательность обозначим через $a_1, a_2, \dots$, так что на $n$-й карте записана цифра $a_n$, равная 0 или 1.

Допустимое по Чёрчу правило отбора является произвольной вычислимой функцией $G$, определённой на множестве $\Xi$ всех двоичных слов и принимающей одно из двух значений: Да и Нет. Карты открываются последовательно, одна за другой, начиная с первой, и каждый раз — до открытия очередной карты — решается вопрос, включать ли эту карту в подпоследовательность. Вопрос этот решается следующим образом. Пусть уже открыты $n$ карт, на которых записаны, соответственно, цифры $a_1, \dots, a_n$. Если $G(a_1, \dots, a_n)$ есть Нет, то следующая, $(n+1)$-я, карта не включается в подпоследовательность. Если $G(a_1, \dots, a_n)$ есть Да, то следующая, $(n+1)$-я, карта включается в подпоследовательность в качестве очередного члена. Включать или не включать в подпоследовательность член $a_1$, зависит от значения $G(\Lambda)$. Таким образом, правилу $G$ отвечает бесконечная подпоследовательность (в случае, если таковая образовалась)

$$a_n(1), a_n(2), a_n(3), \dots,$$

где числа $n(1), n(2), n(3), \dots$ образуют возрастающую последовательность, состоя-
вленную из всех чисел $n$, для которых $G(a_1, \dots, a_{n-1}) = \text{Да}$.

Изложению определения Колмогорова предпошлём обобщение понятия под-
последовательности. Обобщённой подпоследовательностью последовательности
$a_1, a_2, \dots, a_n, \dots$ назовём всякую последовательность вида

$$a_{\varphi(1)}, a_{\varphi(2)}, \dots, a_{\varphi(k)}, \dots,$$

для которой выполнено условие

$$i < j \Rightarrow \varphi(i) \neq \varphi(j).$$

Для обычной подпоследовательности (которая является частным случаем обобщён-
ной) это условие заменено на более сильное — с правой частью $\varphi(i) < \varphi(j)$.

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

Само колмогоровское (т. е. допустимое по Колмогорову) правило состоит из двух вычислимых функций: $F$ и $G$. Первая служит для образования некой вспомогательной обобщённой подпоследовательности. Окончательная же обобщённая подпоследовательность исходной последовательности строится при помощи функции $G$ в качестве обычной подпоследовательности вспомогательной обобщённой подпоследовательности. Аргументами функций $F$ и $G$ служат двоичные слова, так что каждая из этих функций определена на своём подмножестве множества $\Xi$. Значениями функции $F$ служат целые положительные числа, у функции $G$ два возможных значения: Да и Нет. Сперва строится последовательность натуральных чисел $n(1), n(2), n(3), ...$:

$$n(1) = F(\Lambda), n(2) = F(a_{n(1)}), \dots, n(k+1) = F(a_{n(1)}, \dots, a_{n(k)}).$$

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

* значение $F(a_{n(1)}, \dots, a_{n(k)})$ не определено;

* значение $G(a_{n(1)}, \dots, a_{n(k)})$ не определено;

* значение $F(a_{n(1)}, \dots, a_{n(k)})$ совпадает с одним из чисел $n(1), \dots, n(k)$.

Если же остановки в построении не произошло и возникла бесконечная последовательность номеров $n(1), n(2), n(3), \dots$, то далее строится вспомогательная обобщённая подпоследовательность $a_{n(1)}, a_{n(2)}, a_{n(3)}, \dots$. Из неё, наконец, отбираются — в порядке возрастания $k$ — те её члены $a_{n(k)}$, для которых выполнено равенство $G(a_{n(1)}, \dots, a_{n(k-1)}) = \text{Да}$.

## Лицо второе: Хаотичность

Вернёмся к примерам конечных цепочек из Введения и вспомним объяснение, предложенное Колмогоровым: цепочки (I) и (II) воспринимаются как случайные, потому что они сложны; цепочки (III) и (IV) воспринимаются как неслучайные, потому что они просты. По-видимому, мы ожидаем, что результат случайного эксперимента окажется сложным, и удивляемся, когда получаем что-то простое.

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

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

Пусть $Y$ — множество всех объектов, которые мы рассматриваем, а $X$ — множество всех мыслимых описаний этих объектов. Через $|x|$ обозначим длину описания $x$. Сложность объекта $y$ обозначим $\text{Comp}(y)$. В соответствии со сказанным,

$$ \text{Comp}(y) = \min_x \{|x| : x \text{ есть описание для } y\}. $$

Если объект $y$ не описуем, т. е. для него не существует описания, то, естественно, его сложность равна бесконечности.

Разумеется, длины надо мерить единообразным способом, чтобы не получилось, что описание одного и того же объекта имеет на китайском языке длину единица (один иероглиф), а на русском — сёрок (сёрок букв). Поэтому все описания колируются в двоичном алфавите — в виде двоичных цепочек. Вот эти-то двоичные коды мы и будем отныне считать описаниями, так что отныне $X = \Xi$.

Множество всех таких пар $(x, y)$, что $x$ служит описанием для $y$, естественно называть языком описания.

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

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

В декартовом произведении $\Xi \times Y$ рассматриваем произвольное подмножество $E$, которое называем языком описания. Если $(x, y) \in E$, будем говорить, что $x$ является описанием объекта $y$. Сложность $\text{Comp}_E$ объекта $y$ относительно языка $E$ определяется так:

$$ \text{Comp}_E(y) = \min_x \{|x| : (x, y) \in E\}. $$

Напомним, что минимум по пустому множеству принято считать равным бесконечности.

Для языка $E = \Xi \times Y$, в котором каждое $x$ служит описанием для каждого $y$, сложность любого объекта $y$ равна нулю, поскольку одним из описаний этого $y$ является пустое слово; такой язык мыслим, но не будет встречаться в тех семействах языков, которые мы будем рассматривать.

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

Будем говорить, что язык $A$ не хуже языка $B$ и писать $A \le B$, если существует такая константа $c$, что для всякого $y$ справедливо неравенство $\text{Comp}_A(y) < c \text{Comp}_B(y) + c$.

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

Встаёт вопрос о выборе оптимального языка — такого, который не хуже любого другого. Пусть $\mathcal{L}$ — некоторое языковое семейство, т. е., попросту, некоторое множество языков. Язык $A$ из семейства $\mathcal{L}$ называется оптимальным (для $\mathcal{L}$), если он не хуже любого другого языка из этого семейства, т. е. если

$$ \forall B \in \mathcal{L} \text{ выполнено } A \le B. $$

Если оптимальный язык существует, то именно с его помощью следует измерять сложность. Сложность объекта относительно одного из оптимальных языков называется *алгоритмической энтропией* этого объекта.<fnref n="1" /> Энтропию и рассматривают как окончательную искомую меру сложности в рамках заданного языкового семейства.

Для некоторых важных языковых семейств имеет место теорема о существовании оптимального языка, а тем самым и энтропии. Эта теорема называется теоремой *Соломонова – Колмогорова*.

Для данного семейства может существовать много оптимальных языков и тем самым много энтропий. Однако, в силу определения оптимальности, любые две энтропии (взятые для одного и того же фиксированного языкового семейства) различаются не более чем на аддитивную константу. Иными словами, если $A$ и $B$ суть два оптимальных для $\mathcal{L}$ языка, то существует такая константа $c$, что для всех у

$$ |\text{Comp}_A(y) - \text{Comp}_B(y)| < c. $$

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

Из уважения к Колмогорову алгоритмическую энтропию обозначают обычно<fnref n="2" /> буквой $K$; иногда к этой букве $K$ добавляют ещё вторую букву, указывающую то языковое семейство, к которому относится рассматриваемая энтропия. Если $K'$ и $K''$ суть две энтропии, относящиеся к одному и тому же языковому семейству, то, как отмечалось,

$$ |K' - K''| < c. $$

<footnote n="1">¹В основном тексте мы пишем «сложность», оставляя слово «энтропия» для шенноновской энтропии.</footnote>

<footnote n="2">²В англоязычной литературе буква $K$ обычно обозначает префиксный вариант сложности; простая колмогоровская сложность обычно обозначается буквой $C$. Сам Колмогоров использовал буквы $K$ и $H$ (в разных публикациях — разные).</footnote>
Колмогоров не только сформулировал понятие алгоритмической энтропии объекта, но и применил его к исследованию случайных последовательностей. Наблюдение Колмогорова состояло в том, что в случайной последовательности энтропия начального отрезка растёт достаточно быстро при неограниченном увеличении длины этого отрезка. (Ничего не поделаешь: случайная последовательность может начинаться с миллиона нулей, но и этот миллион — ничто перед бесконечностью, и если взять все начальные отрезки в совокупности, то их энтропия неизбежно будет расти.)

Итак, в качестве описываемых объектов мы будем рассматривать двоичные цепочки, такие, как (I), (II), (III), (IV) и т. п. Поэтому отныне $Y = \Xi$.

Если язык содержит пару $\langle z, z \rangle$, то это означает попросту, что цепочка $z$ описывает самоё себя. Язык $D$, состоящий в точности из пар такого вида, называется диагональным (термин из математики), или автонимным (термин из лингвистики). Для такого языка $Comp_D(y) = |y|$. Ограничиваемся языковыми семействами, содержящими автонимный язык (таким будет, в частности, семейство монотонных языков, описанное ниже). Тогда для каждой энтропии $K$, соответствующей этому семейству, и подходящей константы $c$ будет выполнено неравенство

$$K(y) < |y| + c.$$

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

Итак, фиксируем некоторое языковое семейство и одну из соответствующих этому семейству энтропий $K$. Назовём последовательность

$$a_1, a_2, \dots, a_n, \dots$$

хаотической, если существует такая константа $c$, что

$$K(a_1, a_2, \dots, a_n) > n - c.$$

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

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

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

Для наглядности начнём с термина «счётное множество». Термин этот имеет два варианта толкования. В первом, более узком (и более распространённом), толковании счётное множество — это такое множество, которое можно поставить во взаимно однозначное соответствие с натуральным рядом. Во втором, более широком, толковании счётное множество — это такое множество, которое можно поставить во взаимно однозначное соответствие с каким-либо начальным отрезком натурального ряда. Напомним, что **начальным отрезком натурального ряда называется произвольное множество М** натуральных чисел, содержащее вместе со всемkim своим элементом и все меньше числа. Таким образом, и весь натуральный ряд, и пустое множество являются начальными отрезками. Поэтому при втором понимании счётности все конечные множества, в том числе пустое множество, оказываются счётными. Именно это второе, более широкое понимание счётности удобно для наших целей; его мы и примем. А тогда счётному множеству можно дать и такое определение: **множество называется счётным, если оно либо пусто, либо может быть расположено в последовательность (т. е. является множеством членов какой-либо последовательности).** Например, конечное множество {a, b, c} можно расположить в последовательность a, b, c, c, c, ... Заменяя в приведённом определении счётного множества термин «последовательность» на термин «вычислимая последовательность», мы получаем определение перечислимого множества. Что касается определения термина «вычислимая последовательность», то оно сейчас будет дано.

Последовательность w₁, w₂, ..., wₙ, ... называется вычислимой, если существует алгоритм, вычисляющий её п-й член wₙ по его номеру n. Поэтому понятие вычислимой последовательности называют алгоритмическим аналогом, или эффективным аналогом, понятия последовательности, а понятие перечислимого множества — алгоритмическим аналогом, или эффективным аналогом, понятия счётного множества. Перечислимые множества называются также эффективно счётными. Повторим определение: множество называется перечислимым, или эффективно счётным, если оно либо пусто, либо может быть расположено в вычислимую последовательность (т. е. является множеством членов какой-либо вычислимой последовательности).

Все рассматриваемые нами языки суть подмножества декартова произведения Ξ × Ξ и, следовательно, счётны. Идеология Колмогорова состояла в том, чтобы рассматривать только эффективно счётные (они же — перечислимые) языки.
Окончательно надлежащий выбор языкового семейства произвёл колмогоровский ученик Леонид Левин. Именно, в 1973 г. он ввёл в рассмотрение семейство монотонных языков и изучил соответствующее этому семейству понятие хаотично-сти.<fnref n="1" /> Приведём необходимые определения.

Будем говорить, что двоичные слова $u$ и $v$ согласованы, и писать $u \approx v$, если одно из этих слов есть начало другого.

Язык $E$ называется монотонным, если он перечислим и выполнено условие:

$$ (\langle x_1, y_1 \rangle \in E \& \langle x_2, y_2 \rangle \in E \& (x_1 \approx x_2)) \Rightarrow (y_1 \approx y_2). $$

Можно показать, что в семействе монотонных языков имеется оптимальный. Алгоритмическая энтропия, соответствующая семейству монотонных языков, называется монотонной энтропией<fnref n="2" /> и обозначается $KM$.

Всякую последовательность, являющуюся хаотической для семейства монотонных языков, будем называть просто хаотической.<fnref n="3" /> Условие хаотичности последовательности $\langle a_1, a_2, a_3, \dots \rangle$ можно записать так:

$$ \exists c \ \forall n \ \text{выполнено } KM(a_1, a_2, \dots, a_n) > n - c. $$

Класс всех хаотических последовательностей обозначается буквой $C$.

Считается, что строгое понятие хаотической последовательности может служить хорошим отражением интуитивного понятия случайной последовательности. К тому есть два основания.

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

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

$$ C = T. $$

Поэтому хаотические последовательности можно было бы называть типично-хаотическими или хаотично-типическими, а сам класс обозначать $TC$ или $CT$. Этот класс ўже класса $S$ всех последовательностей, стохастических по Колмогорову (последний, как ужё отмечалось, слишком широк):

$$ TC \subset S, \ TC \neq S. $$

## Лицо третье: Типичность

Сказать про какой-либо объект, что он типичен — это значит сказать, что он принадлежит к любому подавляющему большинству. Например, типичный человек,

<footnote n="1">¹Близкое понятие ввёл в 1972 г. Шнорр, см. об этом ниже.</footnote>

<footnote n="2">²В основном тексте используется термин «монотонная сложность». Приведённое только что определение монотонной сложности рассматривается в разделе 6.2.</footnote>

<footnote n="3">³Поскольку это свойство оказывается равносильным случайности по Мартин-Лёфу (типичности), отдельного названия для него в основном тексте не используется.</footnote>
встреченный на московской улице, имеет рост менее двух метров (т. е. принадлежит к подавляющему большинству людей, имеющих рост менее двух метров), возраст более трёх лет (т. е. принадлежит к подавляющему большинству людей, имеющих возраст более трёх лет) и т. д. Конечно, любое из большинств, о которых идёт речь, должно быть разумным, ведь какой объект ни возьми, он заведомо не принадлежит к подавляющему большинству, образованному всеми остальными, отличными от данного, объектами.

Мы исходим из интуитивного представления о том, что случайный объект должен обладать свойством типичности. Наша цель — дать строгое математическое определение этого свойства для последовательностей нулей и единиц при равномерном распределении вероятностей на пространстве Ω таких последовательностей. Последовательности, удовлетворяющие этому строгому определению, мы будем называть типическими, оставляя слово типичный для употребления на интуитивном уровне. В силу сказанного выше, нам надо определить сперва, что есть подавляющее большинство последовательностей, а затем — какие большинства следует считать разумными. А тогда класс типических последовательностей автоматически определится как пересечение всех разумных большинств.

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

Итак, пусть дано какое-то множество последовательностей $Q \subset \Omega$. Мы хотим определить, когда его следует считать малым. В терминах теории вероятностей мы сказали бы, что $Q$ малое, коль скоро вероятность попадания в $Q$ равна нулю. В терминах теории меры мы сказали бы, что $Q$ малое, коль скоро оно имеет меру нуль. Мы, однако, постараемся определить, что такое малое множество, в более простых терминах.

Множество $Q$ называется малым, если его можно покрыть шарами, сумма объёмов которых сколь угодно мала. Определению малого множества можно дать такую формулировку: множество $Q$ называется малым, если для каждого натурального числа $m$ найдётся такая последовательность двоичных слов

$$ \langle x(1), x(2), \dots, x(n), \dots \rangle, $$

что

$$ Q \subset \bigcup_n \Omega_{x(n)}, \\ \sum_n v(x(n)) = \sum_n 2^{-|x(n)|} < \frac{1}{m}. $$

Очевидно, каждая отдельная последовательность из $\Omega$ образует малое множество, а потому понятие большого множества не может претендовать на роль уточнения понятия разумного большинства. Пересечение всех больших множеств пусто. «Разумность» вводится путём следующей корректировки определения.
Во-первых, потребуем, чтобы упоминаемая в определении последовательность двоичных слов $\langle x(1), x(2), \dots, x(n), \dots \rangle$ была вычислимой. Другими словами, мы требуем, чтобы существовал алгоритм, вычисляющий её $n$-й член $x(n)$ по его номеру $n$.

Во-вторых, потребуем, чтобы такая вычислимая последовательность не просто существовала для каждого $m$, но строилась бы по этому $m$ эффективно. Слово «эффективно» означает с помощью алгоритма. Здесь необходимы разъяснения. Дело в том, что алгоритм, получающий на вход $m$ и выдающий на выходе требуемую последовательность, невозможен просто потому, что последовательность — это бесконечный объект, а алгоритмы оперируют лишь с конечными объектами. Однако в нашем случае, поскольку последовательность вычислима, то у неё есть алгоритм, который её вычисляет, даже очень много таких алгоритмов. Алгоритмы (в другой системе терминов — программы алгоритмов) являются конечными объектами, и потому вполне осмысленно говорить об алгоритме, который по чисту $m$, поступившему на его вход, выдаёт на выходе один из алгоритмов (в другой системе терминов — одну из программ), вычисляющих последовательность $\langle x(1), x(2), \dots, x(n), \dots \rangle$.

Внеся в определение малого множества эти два добавления, мы получаем определение эффективно малого<fnref n="1" /> множества, а тем самым, и определение эффективно большого множества. Пересечение всех эффективно больших множеств оказывается непустым. Более того, оно само является эффективно большим. Это наименьшее среди эффективно больших множеств и есть искомое множество $T$ всех типических последовательностей.

Типические последовательности называют также случайными по Мартин-Лёфу — по имени ученика Колмогорова, замечательного шведского математика Пера Мартин-Лёфа, который в 1966 г. сформулировал только что изложенное определение типичности в качестве строгого уточнения понятия случайности.

Как уже говорилось, класс $T$ всех типических последовательностей совпадает с классом $C$ всех хаотических последовательностей:

$$T = C.$$

Поэтому, как уже говорилось, типические последовательности можно именовать также хаотическо-типическими или типическо-хаотическими, а сам класс всех таких последовательностей обозначать $CT$ или $TC$.

Как мы уже знаем,

$$CT \subset S, \quad CT \neq S.$$

## Лицо четвёртое: Непредсказуемость

Вот начало «Двенадцати стульев» Ильфа и Петрова: «В уездном городе $N$ было так много парикмахерских заведений и бюро похоронных процессий, что казалось, жители города рождаются лишь затем, чтобы побриться, остричься, освежить голову вежеталем и сразу же умереть». Суждение остаётся верным, если заменить $N$ на

<footnote n="1">¹В основном тексте такие множества называются эффективно нулевыми.</footnote>
Москву, парикмахерские на залы игровых автоматов, похоронные бюро на казино, а цель рождения на «играть». Этот печальный факт, однако, позволяет наглядно объяснить то свойство случайных последовательностей, которое мы называем непредсказуемостью.

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

Непредсказуемость какой-либо последовательности, таким образом, определяется в терминах игры, которую Игрок ведёт против обладающего этой последовательностью Казино, или, для краткости, против данной последовательности.

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

Для наглядности представим себе, что члены последовательности написаны на картах, которые лежат рубашками вверх, так что Игрок не видит, что там написано. Последовательность предстаёт перед Игроком в виде бесконечного ряда таких карт. Игра состоит в том, что Игрок на каждом своём ходу указывает ту карту, которая должна быть открыта, одновременно предсказывая значение, которое обнаружится на этой карте, и объявляя размер денежной ставки. Если предсказание окажется правильным, Казино выплачивает Игроку сумму ставки, если неправильным — Игрок выплачивает эту сумму Казино. Считается, что Игрок выиграл, если он сумел разорить Казино. Разумеется, если Игроку открыт неограниченный кредит, он всегда может разорить Казино, удваивая ставки. Но игра идёт на наличные, так что величина ставки ограничена текущим капиталом Игрока.

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

На математическом языке ситуация описывается так. Рассматривается бесконечная последовательность нулей и единиц

$$ \mathbf{a} = \langle a_1, a_2, a_3, \dots \rangle. $$

При каждом ходе Игрока возникает тройка чисел

$$ \langle n, i, v \rangle, $$

где

$$ n \in \mathbb{N}, \quad i \in \{0, 1\}, \quad v \in \mathbb{Q}, \quad v \ge 0; $$
здесь, как обычно, $N$ обозначает натуральный ряд<fnref n="1" />, а $Q$ — множество всех рациональных чисел. Содержательно: натуральное число $n$ есть номер того члена последовательности, на который делается ставка; $i$ есть предсказываемое значение этого члена; неотрицательное рациональное число $v$ есть размер ставки. Ходы делаются друг за другом, начиная с первого; тройка, возникающая на $k$-м ходу, обозначается $\langle n(k), i(k), v(k) \rangle$. Более математически грамотно было бы сказать, что каждый ход есть тройка чисел и что ходы не делаются, а предъявляются.

Капитал Игрока перед $k$-м ходом обозначается $V(k-1)$. Без ограничения общности можно считать, что начальный капитал Игрока равен единице: $V(0) = 1$.

После каждого хода капитал Игрока меняется (если только ставка не была нулевой). А именно:

* если $i(k) = a_{n(k)}$ (Игрок угадал), то $V(k) = V(k-1) + v(k)$;

* если $i(k) \neq a_{n(k)}$ (Игрок не угадал), то $V(k) = V(k-1) - v(k)$.

И ещё два прибавления к сказанному.

Во-первых, ходы бывают корректные и некорректные, и чтобы игра продолжалась, необходимо, чтобы ход был корректным. А именно, $k$-й ход считается корректным, если выполнены оба нижеследующие требования:

1) номер открываемой карты корректен: это значит, что подлежащая открытию карта не была уже открыта ранее, т. е. $n(k)$ не совпадает ни с одним из чисел $n(1), \dots, n(k-1)$;

2) делаемая Игроком ставка корректна: это значит, что она меньше его текущего капитала, т. е. $v(k) < V(k-1)$.

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

**Основное правило остановки.** Если Игрок совершает некорректный ход, игра останавливается. При этом Игрок остаётся при имеющемся у него к данному моменту капитале — и, тем самым, заведомо не выигрывает.

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

<footnote n="1">¹Натуральный ряд иногда начинают с единицы, а иногда (в частности, в большинстве исследований по теории вычислимых функций) с нуля. В данном случае мы не включаем нуль в натуральный ряд.</footnote>
ибо никогда не поступает сигнала об остановке. Таким образом, у игры есть три возможных сценария развития: 1) Игрок делает бесконечное число ходов; 2) Игрок делает лишь конечное число ходов, и причиной этого служит то, что был сделан некорректный ход; 3) Игрок делает лишь конечное число ходов, и причиной этого служит то, что на каком-то этапе игры Игрок не в состоянии прийти к решению об очередном ходе. Разумеется, сказанное носит иллюстративный характер, и математическое описание не включает в себя ссылку на такие понятия, как «решать», «обдумывать» и т. п.

По определению, Игрок выигрывает (при игре против а), если

$$ \sup_k V(k) = +\infty, $$

т. е. если

$$ \forall W \exists k V(k) > W. $$

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

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

Таким образом, историю игры перед k-м ходом можно записать в виде таблицы:

```
n(1) n(2) ... n(k-1)
i(1) i(2) ... i(k-1)
v(1) v(2) ... v(k-1)
a_n(1) a_n(2) ... a_n(k-1)
```

(если $k=1$, таблица пуста).

На математическом языке стратегия есть функция, которая каждой подобной таблице (в том числе пустой) либо ничего не ставит в соответствие, либо ставит в соответствие некоторый ход, т. е. тройку $\langle n, i, v \rangle$. Под «каждой подобной таблицей» мы понимаем отнюдь не только такую таблицу, которая отражает реальное течение игры, а произвольную таблицу, в которой в первой строке стоят положительные целые числа, в третьей — неотрицательные рациональные числа, а во второй и четвёртой — нули и единицы.
Если таблица реально встретилась в процессе игры (в качестве истории игры на каком-то этапе) и если задана стратегия, то первые три строки таблицы однозначно восстанавливаются по её четвёртой строке. В самом деле, применение стратегии к пустой таблице даёт нам первый ход $\langle n(1), i(1), v(1) \rangle$. Тем самым — поскольку четвёртая строка предполагается известной — мы получаем историю игры перед вторым ходом в виде таблицы

$$ 
\begin{aligned}
n(1) \\
i(1) \\
v(1) \\
a_n(1).
\end{aligned}
$$

Теперь к этой таблице снова применяем стратегию, которая указывает второй ход $\langle n(2), i(2), v(2) \rangle$; получаем таблицу

$$ 
\begin{aligned}
n(1) & n(2) \\
i(1) & i(2) \\
v(1) & v(2) \\
a_n(1) & a_n(2),
\end{aligned}
$$

и так далее.

Сказанное даёт нам право при определении стратегии брать в качестве аргумента не всю таблицу в целом, а лишь её четвёртую строку. Заметим, что в этой четвёртой строке стоит двоичное слово, т. е. элемент множества $\Xi$. Стратегия должна, имея этот элемент, или не выдавать ничего, или выдавать ход, который есть тройка, т. е. элемент декартова произведения $N \times \{0, 1\} \times Q_+$. Здесь символом $Q_+$ обозначено множество всех неотрицательных рациональных чисел.

Мы приходим к окончательному определению понятия стратегии: стратегия есть отображение некоторого подмножества множества $\Xi$ всех двоичных слов в декартово произведение $N \times \{0, 1\} \times Q_+$:

$$ \Xi \rightarrow N \times \{0, 1\} \times Q_+. $$

Для наших целей особый интерес представляет случай, когда указанное отображение задается каким-то алгоритмом. Поясним, что это значит. Пусть $A$ — алгоритм, на вход которого могут подаваться элементы из множества $X$, а на выходе получаются элементы из множества $Y$. В множестве $X$ выделяется область результативности алгоритма $A$, состоящая из тех и только тех элементов, в применении к которым $A$ даёт результат. Алгоритм $A$ задаёт следующее отображение: область определения этого отображения совпадает с область результативности алгоритма, и для каждого элемента этой области значение отображения на этом элементе совпадает с тем результатом, который получается при применении алгоритма к этому элементу.

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

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

Последовательность называется предсказуемой, если для неё существует вы-
игрывающая вычислимая стратегия, и непредсказуемой — в противном случае.
Класс всех непредсказуемых последовательностей обозначается буквой **U**.<fnref n="1" />

Известно, что всякая непредсказуемая последовательность является стохастиче-
ской по Колмогорову (принадлежит классу S) и что всякая типическо-хаотическая
последовательность (последовательность класса CT) непредсказуема:

$$
CT \subset U \subset S.
$$

Известно также, что класс стохастических по Колмогорову последовательностей
существенно шире класса непредсказуемых:

$S \neq U.$

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

$$
\mathbf{CT} \stackrel{?}{=} \mathbf{U}.
$$

Эта важная проблема ждёт своего решения.

О безостановочных стратегиях

Если игра никогда не останавливается, она называется **безостановочной**. Стратегия называется **безостановочной**, если, какова бы ни была последовательность, применение против неё этой стратегии приводит к безостановочной игре. В определении предсказуемости можно ограничиться безостановочными стратегиями и дать такую равносильную формулировку: последовательность называется **предсказуемой**, если для неё существует выигрывающая вычислимая безостановочная стратегия. Чтобы убедиться в равносильности, достаточно объяснить, как можно алгоритм **А**, задающий выигрывающую стратегию, переделать в алгоритм **В**, задающий выигрывающую безостановочную стратегию. Такая переделка осуществляется весьма просто. Сперва по поступившему на вход алгоритма **А** двоичному слову восстанавливается история игры, что позволяет знать как номера всех открытых ранее карт, так и величину текущего капитала Игрока. Затем всякий ход, предписываемый исходным алгоритмом **А**, проверяется на корректность, и если он оказывается некорректным, то новый алгоритм **В** никакого хода не выдаёт, а объявляется не определённым на указанном двоичном слове.

<footnote n="1">¹В основном тексте такие последовательности упоминались как «случайные относительно немоно-
тонных вычислимых мартингалов», см. обсуждение на с. 347.</footnote>
Обобщение на вычислимые распределения вероятностей

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

Говорят, что на множестве *M* задана мера *μ*, коль скоро, во-первых, выделен некоторый класс подмножеств множества *M*, называемых измеримыми, и, во-вторых, каждому измеримому подмножеству *A* отнесено неотрицательное число *μ*(*A*), называемое мерой этого подмножества. При этом требуется, чтобы выполнялись некоторые аксиомы, приводить которые мы здесь не будем; отметим только, что следствием этих аксиом является такой факт: объединение непересекающихся измеримых множеств измеримо и его мера равна сумме мер этих множеств. Если *μ*(*M*) = 1, мера называется вероятностной, или распределением вероятностей. В этом случае *μ*(*A*) содержательно трактуется как вероятность того, что случайно выбранный элемент множества *M* попадает в *A*.

Каждая мера на Ω характеризуется мерами шаров. Так, для равномерного распределения (и только для него)

$$
\forall x \in \Xi \text{ выполнено } \mu(\Omega_x) = 2^{-|x|}.
$$

Равномерное распределение вероятностей на пространстве Ω отвечает тому сценарию, когда нули и единицы возникают в последовательности с равными вероятностями. Ближайшим обобщением равномерного распределения является распределение Бернулли, или бернуллиевское распределение (называемое также биномиальным), при котором нули и единицы возникают независимо с вероятностью p для единицы и вероятностью 1 - p для нуля; это число p условимся называть параметром бернуллиевского распределения. Если параметр равен одной второй, получаем равномерное распределение. Говоря формально, распределение Бернулли с параметром p задаётся формулой

$$
\mu(\Omega_x) = p^k (1-p)^{|x|-k},
$$

где k — количество единиц в слове x.

Следующим обобщением служит класс распределений, которые мы будем называть квазибернуллиевскими. На содержательном уровне квазибернуллиевость распределения вероятностей означает, что единицы и нули появляются в качестве членов последовательности по-прежнему независимо, но с переменой вероятностью, зависящей от номера члена. Вероятность того, что член с номером *k* есть единица, условимся обозначать через *p*(*k*); тогда вероятность того, что этот член есть
нуль, окажется равной $1 - p(k)$. Формальное определение квазибернуллиевского распределения таково. Пусть дана последовательность действительных чисел

$$ \mathbf{p} = \langle p(1), p(2), \dots, p(k), \dots \rangle, \quad 0 \le p(k) \le 1. $$

Про распределение $\mu$ будем говорить, что оно квазибернуллиевское с параметром $\mathbf{p}$, если для всякого двоичного слова $x = (x_1, \dots, x_n)$ имеет место равенство

$$ \mu(\Omega_x) = \prod_{i=1}^{n} r_i, $$

где $r_i = p(i)$ при $x_i = 1$ и $r_i = 1 - p(i)$ при $x_i = 0$. Для ясности: бернуллиевское распределение с параметром $\mathbf{p}$ является квазибернуллиевским с параметром $\mathbf{p} = (p, p, \dots, p, \dots)$.

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

$$ \mathbf{C}(\mu) = \mathbf{T}(\mu) \subset \mathbf{U}(\mu) \subset \mathbf{S}(\mu), \\ \mathbf{S}(\mu) \neq \mathbf{U}(\mu) $$

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

Здесь через $\mathbf{C}(\mu)$, $\mathbf{T}(\mu)$, $\mathbf{U}(\mu)$, $\mathbf{S}(\mu)$ соответственно обозначены те классы последовательностей, хаотических, типических, непредсказуемых, стохастических по Колмогорову относительно распределения $\mu$, которые будут определены ниже. (В наших прежних обозначениях $\mathbf{C} = \mathbf{C}(\eta)$, $\mathbf{T} = \mathbf{T}(\eta)$, $\mathbf{U} = \mathbf{U}(\eta)$ и $\mathbf{S} = \mathbf{S}(\eta)$, где $\eta$ есть равномерное распределение.)

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

## Вычислимые меры и вычислимые распределения

Хотелось бы называть меру $\mu$ на пространстве $\Omega$ вычислимой, если существует такой алгоритм, который по каждому двоичному слову $x$ даёт меру $\mu(\Omega_x)$ шара $\Omega_x$. Однако алгоритмы не могут иметь дело с действительными числами, а только с числами целыми, рациональными и т. п. — строго говоря, даже не с числами, а с их именами в виде слов в каком-либо фиксированном конечном алфавите (словом
в данном алфавите называется любая конечная цепочка, составленная из букв этого алфавита). Дать же имена всем действительным числам невозможно, поскольку для каждого конечного алфавита все слова в нём образуют лишь счётное множество. Поэтому можно требовать лишь наличие алгоритма, дающего не самоё меру шара, а сколь угодно точное рациональное приближение к ней.

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

Иногда в определение вычислимости включают ещё и требование о существова-
нии такого алгоритма, который для каждого двоичного слова х определяет, имеет
ли место равенство μ(Ωх) = 0. Вычислимые меры, удовлетворяющие этому дополн-
ительному требованию (которое мы не включаем в определение вычислимости),
будем называть сильно вычислимыми. Заметим, что из вычислимости меры не вы-
текает, как могло бы показаться, её сильная вычислимость.

Важным подклассом класса сильно вычислимых мер является класс вычисли-
мо-рациональных мер. Будем называть меру вычислимо-рациональной, если мера
каждого шара есть рациональное число и существует алгоритм, вычисляющий эту
меру по заданному шару, т. е., на более точном языке, алгоритм, который для
каждого двоичного слова х выдаёт дробь, выражающую меру μ(Ωх) шара Ωх. За-
метим для ясности, что если мера вычислима, а её значения на шарах рациональ-
ны, то отсюда ещё не следует, что она вычислимо-рациональна: умение находить
для данного рационального числа сколь угодно точные рациональные приближения
к нему ещё не означает умения выписать само это число в виде отношения двух
целых чисел!

Теперь нет нужды отдельно определять, что такое вычислимое распределение вероятностей: это просто-напросто вычислимая вероятностная мера. Именно на вычислимые распределения естественно обобщаются многие определения и факты, изложенные нами для равномерного распределения. В частности, для произвольного вычислимого распределения верны как теорема *Мартин-Лёфа*, утверждающая, что пересечение всех эффективно больших множеств само является эффективно большим, так и теорема *Левина*, утверждающая, что типичность равносильна heterogeneidad, определённой на основе монотонной энтропии.<fnref n="1" />

Стохастичность

Для какой-либо последовательности е её k-й член обозначаем еk или, дабы избежать многоэтажных индексов, е(к).

В случае равномерного распределения стохастичность последовательности по-
нималась как **глобальная устойчивость частот**, т. е. как устойчивость частот в ка-

<footnote n="1">¹В основном тексте книги она называется теоремой Левина – Шнорра; в работе Шнорра, появив-
шейся раньше, рассматривается некоторая особая разновидность сложности, которую автор назвал "про-
цессной". Числовые значения монотонной сложности и процессной сложности могут различаться до-
статочно сильно (уточнение дано ниже, в разделе "История и библиография"), процессную сложность
можно рассматривать как особый вариант монотонной сложности и доказательства Левина и Шнорра
сходны.</footnote>
ждой из допустимых подпоследовательностей. Допустимые же подпоследовательности возникали путём применения допустимых по Колмогорову правил отбора. В ситуации произвольной вероятностной меры общая схема сохраняется, только устойчивость частот заменяется на некоторое более общее свойство, а именно на так называемый закон больших чисел.

Определение стохастичности для бернуллиевского распределения с параметром $p$ очевидно: надо потребовать, чтобы в каждой допустимой подпоследовательности соблюдалась устойчивость частот с одной и той же предельной частотой $p$. Иными словами, доля единиц в начальном отрезке всякой допустимой подпоследовательности должна, при неограниченном удлинении отрезка, стремиться к $p$. Случаи, когда $p=0$ или $p=1$, являются вырожденными; для первого из них не считается стохастической последовательность, в которой встречается хотя бы одна единица, для второго — последовательность, в которой встречается хотя бы один ноль.

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

Ясно, что для квазибернуллиевского распределения предельной частоты в подпоследовательности может и не быть, а если она и есть, то, вообще говоря, в каждой подпоследовательности — своя. Приходится поэтому говорить о стохастичности относительно данного правила отбора. Пусть $p$ — параметр квазибернуллиевского распределения. Прежде всего, заявим, что не считается стохастической последовательность, в которой значение хотя бы одного её члена имеет нулевую вероятность. Или, говоря на формальном языке: последовательность $a$ не считается стохастической, если существует такое $k$, что либо $a(k) = 0$ и $p(k) = 1$, либо $a(k) = 1$ и $p(k) = 0$. Для остальных последовательностей определение таково: последовательность $a$ будем называть стохастической относительно правила отбора $\Theta$, коль скоро её обобщённая подпоследовательность

$$ \mathbf{b} = \langle a(m_1), a(m_2), \dots, a(m_k), \dots \rangle, $$

полученная по этому правилу, удовлетворяет требованию закона больших чисел:

$$ \frac{a(m_1) + \dots + a(m_k)}{k} - \frac{p(m_1) + \dots + p(m_k)}{k} \to 0 $$

при $k \to \infty$. Далее, последовательность $a$ называется стохастической (по Колмогорову), если для любого колмогоровского правила, приводящего к бесконечной обобщённой подпоследовательности, она является стохастической относительно этого правила.

**Замечание.** Слово «бесконечной» в предыдущей фразе избыточно, так как всякая обобщённая подпоследовательность является последовательностью, а следовательно, бесконечна по определению. Тем не менее мы будем иногда использовать это формально избыточное упоминание о бесконечности, дабы подчеркнуть, что имеется в виду именно последовательность, а не кортеж.
Чтобы объяснить, как понятие стохастичности по Колмогорову обобщается на более широкий класс вероятностных распределений, введём несколько обозначений.

Пусть $n(1), n(2), \dots, n(k)$ суть натуральные числа и пусть

$$i(1), i(2), \dots, i(k) \in \{0, 1\}.$$

Через $A_{i(1), \dots, i(k)}^{n(1), \dots, n(k)}$ обозначим множество всех таких последовательностей $\mathbf{a} \in \Omega$, у которых

$$a_{n(1)} = i(1), a_{n(2)} = i(2), \dots, a_{n(k)} = i(k). \quad (*)$$

Дробь

обозначим символом

$$\frac{\mu(A_{i(1), \dots, i(k)}^{n(1), \dots, n(k)}, m)}{\mu(A_{i(1), \dots, i(k)}^{n(1), \dots, n(k)})}$$

это есть условная вероятность того, что $m$-й член последовательности $\mathbf{a}$ будет равен 1 при условии $(*)$; эта величина не определена, коль скоро знаменатель дроби обращается в нуль.

Рассмотрим два произвольных, но фиксированных объекта: последовательность $\mathbf{a} \in \Omega$ и допустимое по Колмогорову правило отбора $\Theta$. Наша цель — придать смысл высказыванию «последовательность $\mathbf{a}$ стохастична относительно правила $\Theta$». Процесс, посредством которого правило $\Theta$ отбирает из последовательности $\mathbf{a}$ члены обобщённой подпоследовательности $\mathbf{b}$, состоит из двух этапов. На первом этапе строится вспомогательная обобщённая подпоследовательность $\mathbf{c}$, из некоторых членов которой на втором этапе и строится $\mathbf{b}$. Более подробно,

$$\mathbf{c} = \langle a_{n(1)}, a_{n(2)}, \dots, a_{n(k)}, \dots \rangle,$$

где номер $n(k)$ вычисляется алгоритмически по кортежу

$$\langle a_{n(1)}, a_{n(2)}, \dots, a_{n(k-1)} \rangle.$$

Имея на входе этот же кортеж, правило $\Theta$ решает, включать или нет член $a_{n(k)}$ в окончательную последовательность $\mathbf{b}$. Таким образом,

$$\mathbf{b} = \langle a(n(k_1)), a(n(k_2)), \dots, a(n(k_j)), \dots \rangle.$$

На каждом из обоих этапов может наступить момент, когда правило $\Theta$ не даст никакого результата, т. е. не выдаст номера на первом этапе или не примет решения на втором этапе. Если такое произойдёт, последовательность $\mathbf{b}$ окажется конечной, т. е., говоря более строго, окажется не последовательностью, а кортежем. В этом случае никакого требования к $\mathbf{b}$ не выдвигается и, говоря формально, $\mathbf{a}$ признаётся стохастической относительно $\Theta$. Если же $\mathbf{b}$ оказалось бесконечной, то для признания последовательности $\mathbf{a}$ стохастической относительно $\Theta$ требуется выполнение нижеследующего свойства последовательности $\mathbf{a}$.
Обозначим через $r_j$ величину

$$ \mu \left( \begin{array}{c|c} n(k_j) & n(1), \ n(2), \dots, \ n(k_j - 1) \\ \hline 1 & a(n(1)), a(n(2)), \dots, a(n(k_j - 1)) \end{array} \right). $$

Рассмотрим разность

$$ \delta_j = \frac{r_1 + r_2 + \dots + r_j}{j} - \frac{a(n(k_1)) + a(n(k_2)) + \dots + a(n(k_j))}{j}. $$

Величина $\delta_j$ не определена, если не определена хотя бы одна из величин $r_1, \dots, r_j$. Скажем, что **b** подчиняется закону больших чисел, если все величины $\delta_j$ определены и $\delta_j \to 0$ при $j \to \infty$. Последовательность **a** назовём стохастической относительно правила $\Theta$, если обобщённая подпоследовательность **b**, полученная из **а** согласно правилу $\Theta$, подчиняется закону больших чисел.

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

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

## Хаотичность

Определение последовательности, хаотической относительно меры $\mu$, таково: последовательность **а** = $\langle a_1, a_2, a_3, \dots \rangle$ называется хаотической относительно $\mu$, если существует такая константа $c$, что для всех $n$ выполняется неравенство

$$ KM(a_1, a_2, \dots, a_n) > - \log \mu(\Omega_{a_1, a_2, \dots, a_n}) - c, $$

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

Мотивировка этого определения, имеющего содержательный смысл для вычислимых вероятностных мер, такая же, как и в случае равномерного распределения вероятностей. Дело в том, что для всякой вычислимой вероятностной меры выполняется соотношение:

$$ \exists c \forall x \in \Xi \text{ выполнено } KM(x) < -\log \mu(\Omega_x) + c. $$

Говоря неформально, для любой вычислимой меры $\mu$ можно подобрать язык описания, приспособленный к этой мере в том смысле, что снабжает слова х с большим $\mu(\Omega_x)$ короткими описаниями (и написанное соотношение указывает длину этих коротких описаний). Определение хаотичности требует, чтобы полученные таким способом короткие описания нельзя было бы ещё укоротить (более чем на константу).
## Типичность

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

Сперва определяется понятие эффективно малого множества. Множество $Q \subset \Omega$ называется эффективно малым относительно меры $\mu$, коль скоро существует алгоритм А, удовлетворяющий нижеследующему требованию. При поступлении на вход алгоритма А натурального числа $m$ на его выходе возникает алгоритм построения такой последовательности двоичных слов $\langle x(1), x(2), \dots, x(n), \dots \rangle$ (т. е. алгоритм вычисления такой функции $n \mapsto x(n)$), что

$$Q \subset \bigcup_n \Omega_{x(n)}, \\ \sum_n \mu(\Omega_{x(n)}) < \frac{1}{m}.$$

Далее, эффективно большое относительно меры $\mu$ множество определяется как дополнение (до $\Omega$) к эффективно малому.

Для вычислимых мер имеет место теорема Мартин-Лёфа: объединение всех эффективно малых множеств является эффективно малым, а пересечение всех эффективно больших — эффективно большим. Существующее согласно этой теореме наименьшее эффективно большое множество называют конструктивным носителем меры $\mu$. В случае, если $\mu$ — вычислимое распределение вероятностей, последовательности, принадлежащие конструктивному носителю распределения $\mu$, и называют типическими относительно этого распределения. Таким образом, $\Gamma(\mu)$ есть не что иное как конструктивный носитель распределения $\mu$.

## Непредсказуемость

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

Распределение вероятностей влияет на правило изменения капитала Игрока после очередного хода. Если Игрок не угадал, его капитал уменьшается на сумму сделанной им ставки — так же, как и в случае равномерного распределения. Но если Игрок угадал, то прирост его капитала равняется ставке, умноженной на который коэффициент. Этот коэффициент сравнительно велик, если вероятность угадать была низка, и сравнительно мал, если вероятность угадать была высока. Для равномерного распределения вероятность угадать всегда равна одной второй, а коэффициент всегда равен единице. Точная формулировка правила прироста капитала будет сейчас изложена.
Для последовательности **a** её k-й член обозначаем $a_k$, для последовательности $\mathbf{a}'$ её k-й член обозначаем $a'_k$ и т. д.

Ход, делаемый на j-м ходу, есть тройка $\langle n(j), i(j), v(j) \rangle$.

Пусть последовательность, которой располагает Казино, есть **a**. Положим

$$A(k-1) = \{ \mathbf{a}' \in \Omega : a'_{n(j)} = a_{n(j)} \text{ при } j = 1, 2, \dots, k-1 \}$$

(так что $A(0) = \Omega$),

$$A_i(k) = \{ \mathbf{a}' \in A(k-1) : a'_{n(k)} = i \} \text{ для } i = 0, 1.$$

Разумеется, эти обозначения имеют смысл в предположении, что все участвующие в их определениях номера $n(l)$ определены. Полезно заметить, что

$$\Omega = A(0) \supset A(1) \supset A(2) \supset \dots, \qquad (1)$$

$$1 = \mu(A(0)) \ge \mu(A(1)) \ge \mu(A(2)) \ge \dots; \qquad (2)$$

если Игрок на k-м ходу угадал, то

$$i(k) = a_{n(k)}, \quad A_{i(k)}(k) = A(k); \qquad (3)$$

если Игрок на k-м ходу не угадал, то

$$i(k) \neq a_{n(k)}, \quad A_{1-i(k)}(k) = A(k); \qquad (4)$$

кроме того,

$$A(k-1) = A_0(k) \cup A_1(k). \qquad (5)$$

В случае, если $i(k) = a_{n(k)}$ (прогноз Игрока на его k-м ходе оправдался — он угадал), капитал Игрока увеличивается по формуле

$$V(k) = V(k-1) + v(k) \cdot \frac{\mu(A_{1-i(k)}(k))}{\mu(A_{i(k)}(k))}. \qquad (6)$$

Наша формула (6) гарантирует «честность» игры: математическое ожидание вы- игрыша, т. е. прироста капитала, за один ход равно нулю. Однако на пути примене- ния этой формулы нас подстерегает неприятность, невозможная для равномерного распределения, как и для любой позитивной меры (мера называется позитивной, если мера любого шара положительна). Неприятность заключается в том, что сто- ящая в знаменателе вероятность $\mu(A_{i(k)}(k))$ может оказаться равной нулю. Эта неприятность устраняется путём введения Дополнительного правила остановки, ко- торое мы сейчас приведём. В случае равномерного распределения это правило было излишним, поскольку предусмотренная в нём ситуация не могла встретиться.

**Дополнительное правило остановки.** Оно применяется тогда, когда в ходе игры впервые наступает такая ситуация, что $\mu(A(k)) = 0$ (просим Читателя взглянуть на формулу (2)). Пусть $\mu(A(k-1)) \ne 0$, $\mu(A(k)) = 0$. Последний ход, который был сделан, имел номер k. Делая этот ход, Игрок объявил свой прогноз $i(k)$.
Если прогноз оказался верным, т. е. оказалось, что $i(k) = a_{n(k)}$, игра останавливается, а капитал Игрока считается возросшим до бесконечности: $V(k) = +\infty$. Таким образом, в этом случае Игрок объявляется выигравшим. Если же прогноз оказался неверным, т. е. оказалось, что $i(k) \neq a_{n(k)}$ (или, что то же самое, $1 - i(k) = a_{n(k)}$), игра опять-таки останавливается, но с тем капиталом Игрока, который у него был к этому моменту, так что величина $V(k)$ оказывается равной величине $V(k-1)$. В этом случае, следовательно, Игрок не выигрывает.

Ясно, что проблема с нулевым знаменателем в формуле (6) устраняется этим правилом. Действительно, формула (6) применяется лишь в случае, когда $i(k) = a_{n(k)}$. В этом случае, согласно (3), $A_{i(k)}(k) = A(k)$. Поэтому интересующий нас знаменатель может оказаться нулевым лишь в ситуации, когда $\mu(A(k)) = 0$. Но именно эта ситуация как раз и регулируется не формулой (6), а нашим Дополнительным правилом. (Можно, впрочем, считать, что и формулой (6), если разрешить деление на нуль положительного числа $\mu(A_{1-i(k)}(k))$ и принять бесконечность в качестве результата такого деления.)

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

## История и библиография

[1] А. Н. Колмогоров, В. А. Успенский. Алгоритмы и случайность // Теория вероятностей и её применения, 1987. Т. 32, вып. 3, с. 425–455.

[2] В. А. Успенский, А. Л. Семёнов. Теория алгоритмов: основные открытия и приложения. — М.: Физматлит, 1987. — 288 с.

[3] В. А. Успенский, А. Л. Семёнов, А. Х. Шень. Может ли индивидуальная последовательность нулей и единиц быть случайной? // Успехи математических наук, 1990. Т. 45, вып. 1, с. 105–162.

[4] V. A. Uspensky, A. Shen. *Relations between varieties of Kolmogorov complexities* // *Mathematical Systems Theory*, 1996. Vol. 29, no. 3, p. 271–292.

[5] An. A. Muchnik, A. L. Semenov, V. A. Uspensky. *Mathematical metaphysics of randomness* // *Theoretical Computer Science*, 1998. Vol. 207, p. 263–317.

[6] А. Шень. О соотношениях между различными алгоритмическими определениями случайности // Доклады Академии наук СССР, 1988. Т. 302, № 3, с. 548–552.

[7] В. В. Выюгин. Алгоритмическая энтропия (сложность) конечных объектов и её применение к определению случайности и количества информации // Семиотика и информатика. Выпуск 16. — М: ВИНИТИ, 1981. — С. 14–43.

[8] M. Li, P. Vitányi. *An Introduction to Kolmogorov Complexity and Its Applications*. — New York e. a.: Springer-Verlag, 1993. — xx+546 pp., 38 illustrations;

Second ed. — New York e. a.: Springer-Verlag, 1997. — xx+637pp., 41 illustrations.
Сам этот список из восьми названий никоим образом не претендует на полноту. Однако в этих публикациях (особенно в [8]) можно найти дальнейшие ссылки, и вкупе с этими ссылками некое подобие полноты уже достигается.

В книге [2] следует обратить внимание на § 2.6 «Приложения к теории вероятностей: определения случайной последовательности». Следует также иметь в виду, что терминология этой книги несколько архаична: хаотические последовательности называются там случайными по Колмогорову, а типические — случайными по Мартин-Лёфу. Частотоустойчивые, они же стохастические, последовательности называются в [2] случайными по Мизесу, стохастические по Чёрчу — случайными по Мизесу — Чёрчу, стохастические по Колмогорову — случайными по Мизесу — Колмогорову — Лавлэнду (а в [3] — стохастическими по Колмогорову — Лавлэнду; Д. Лавлэнд (D. Loveland) открыл эти последовательности независимо от Колмогорова, хотя и позже: соответствующая статья Колмогорова была опубликована в 1963 г., статья Лавлэнда — в 1966 г.). Что касается непредсказуемых последовательностей — в том точном понимании, как было сформулировано выше, — то они в указанной книге отсутствуют, поскольку появились в литературе лишь в 1998 г. в статье [5].

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

Теория сложности объектов (в дополнение к уже развивавшейся в то время теории сложности вычислений) была основана Колмогоровым на его семинарах в Московском университете в начале 60-х годов ХХ века и имела своей главной целью перестройку понятийной базы теории информации (на основе представления о том, что чем сложнее объект, тем больше информации он содержит) с последующим приложением к теории случайности. В опубликованной в 1969 г. (английский вариант в 1968 г.) статье Колмогоров писал:

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

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

Предложение измерять сложность объекта длиной его кратчайшего описания и понятие оптимального языка были изложены Колмогоровым в статье 1965 г.; за год до того сходные идеи были опубликованы американским исследователем Рэем Соломоновым (Ray Solomonoff), о работах которого Колмогоров узнал лишь позже. Ввиду этого теорему о существовании оптимального языка мы называем теоре-
мой Соломонова – Колмогорова. В эти же годы (т. е. в середине 60-х годов ХХ в.) Колмогоров высказывает на своих семинарах предположение о том, что быстрота роста энтропии начальных отрезков последовательности может служить критерием случайности рассматриваемой последовательности. Однако введённое им в рассмотрение языковое семейство приводило к энтропии, непригодной для поставленной цели. Как уже говорилось выше, в главке о хаотичности, годное для этой цели семейство обнаружил в 1973 г. Леонид Левин, введя в рассмотрение монотонную энтропию.

Типические последовательности (под названием “random”, то есть «случайные») были, как уже отмечалось в главке о типичности, открыты в 1966 г. Пером Мартин-Лёфом (Per Martin-Löf).

Утверждение о том, что класс последовательностей, стохастических по Колмогорову, шире класса типических (они же — хаотические) последовательностей, доказал Александр Шень (см. [6], а также [2, п. 6.2.4])<fnref n="1" />.

Пусть $К$ — энтропия в каком-то из вариантов этого понятия. (В литературе исследованы не менее шести таких вариантов: простая, априорная, монотонная, процессная, префиксная и энтропия разрешения; все эти варианты существенно различны в том точном смысле, что разность энтропий, принадлежащих любым двум из перечисленных вариантов, не ограничена.) Скажем, что последовательность $a_1, a_2, a_3, \dots, a_n, \dots$ является хаотической относительно $K$ (при равномерном распределении!), если

$$ \exists c \forall n \text{ выполнено } K(a_1, a_2, a_3, \dots, a_n) > n - c. $$

(Заметим для ясности, что ни для простой энтропии, ни для энтропии разрешения последовательностей с таким свойством нет вовсе, а для каждой из остальных четырёх энтропий хаотичность оказывается равнообъёмной типичности.) В той же статье Левина 1973 г., в которой была введена монотонная энтропия, содержалось и доказательство того факта, что понятие хаотичности относительно монотонной энтропии равнообъёмно понятию типичности. Независимо от Левина в том же 1973 г. Клаус-Петербург Шнорр (Claus-Peter Schnorr; предварительная публикация в трудах конференции в 1972 г.) ввёл в рассмотрение свой вариант энтропии, так называемую процессную энтропию (у Шнорра — process complexity), и доказал (независимо от Левина, но очень похожим способом), что понятие хаотичности относительно процессной энтропии также равнообъёмно понятию типичности. Хотя процессная энтропия и монотонная энтропия существенно различаются (как показал Владимир Выогин [7, строки 6–4 снизу], их разность не ограничена никакой константой) и хотя впоследствии сам Шнорр перестал пользоваться своей процессной энтропией, фактически от неё отказавшись, вышеуказанную теорему Левина иногда называют теоремой Левина – Шнорра.

Префиксную энтропию ввели Левин (в диссертации на соискание учёной ступени кандидата физико-математических наук, представленную к защите в 1971 г.;

<footnote n="1">¹Основная идея этого доказательства была предложена М. Ламбальгеном для монотонных правил выбора и легко обобщается на произвольные.</footnote>
её, однако, защитить не удалось, и определение префиксной энтропии было опубликовано лишь в 1974 г.)<fnref n="1" /> и позже (но независимо от Левина) — Грегори Чейтин (Gregory J. Chaitin) (см. его статью *A theory of program size formally identical to information theory // Journal of the Association of Computing Machinery*, 1975, v. 22, no. 3, p. 329–340). В той же статье Чейтин ввёл понятие хаотичности относительно префиксной энтропии и объявил (без доказательства), что этот вариант хаотичности равносилен типичности; первое опубликованное доказательство этого факта появилось в статье Выюгина [7]: следствие 3.2 на с. 38. *Префиксная энтропия* может быть определена как энтропия для семейства префиксных языков. Язык Е называется *префиксным*, если он перечислим и выполнено условие:

$$ (\langle x_1, y_1 \rangle \in E \ \& \ \langle x_2, y_2 \rangle \in E \ \& \ (x_1 \approx x_2)) \Rightarrow (y_1 = y_2). $$

Заметим ещё, что в литературе термин «сложность» ("complexity") часто употребуется в смысле *энтропия*, т. е. в смысле сложность относительно оптимального языка.

Непредсказуемые последовательности (в смысле настоящей статьи) впервые возникли весной 1991 г. в совместном докладе под названием «Randomness and Lawlessness» («Случайность и беззаконность»), который Андрей Мучник, Алексей Семёнов и автор этих строк сделали на конференции в Калифорнии. Конференция была посвящена основаниям теории случайности и проходила с 4 по 7 марта в Институте математических исследований в социальных науках (Institute for Mathematical Studies in the Social Sciences) Станфордского университета. Содержание доклада было опубликовано в 1998 г. в виде статьи [5]. В этой статье приведены, в частности, теоремы о соотношении непредсказуемости с другими алгоритмическими лицами случайности.<fnref n="2" />

Отметим, что определение непредсказуемости в нашем настоящем очерке отличается одной деталью от определения в [5]. Именно, в [5] для корректности ставки требовалось выполнение не строгого неравенства $v(k) < V(k-1)$, а более слабого нестрогого неравенства $v(k) \le V(k-1)$. Класс непредсказуемых последовательностей остаётся одним и тем же при обоих пониманиях корректности. Замена в определении корректности нестрогого неравенства на строгое вызвана двумя причинами. Во-первых, сама игра становится более содержательной: ведь в случае неравенства ставки текущему капиталу стоит Игроку ошибиться в своём предсказании, как его капитал обнулится и он будет вынужден в дальнейшем делать лишь нулевые ставки. Во-вторых, именно строгое неравенство позволяет при переносе определений с рационально-вычислимых мер (каковые только и рассматривались в [5]) на любые вычислимые меры сохранить эффективность действий игрока. Ведь каждый раз Игрок должен удостоверяться в корректности хода. Получить же такое удостоверение алгоритмическим путём возможно лишь в варианте строгого неравенства: существует алгоритм, в том и только в том случае дающий положительный

<footnote n="1">¹См. работу [76] из библиографии к основному тексту.</footnote>

<footnote n="2">²Для случая, когда члены последовательности просматриваются слева направо, игровой подход к случайности и соответствующее понятие мартингала было предложено Ж. Виллем в 1930-е годы в качестве альтернативы подходу фон Мизеса, основанному на устойчивости частот.</footnote>
ответ на вопрос «v(k) < V(k - 1)?», когда и в самом деле v(k) < V(k - 1); не существует алгоритма, в том и только в том случае дающего положительный ответ на вопрос «v(k) ≤ V(k - 1)?», когда и в самом деле v(k) ≤ V(k - 1).

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

Множество целых чисел обозначается $\mathbb{Z}$, множество натуральных чисел (включая нуль) — $\mathbb{N}$, множество действительных чисел — $\mathbb{R}$. Множество рациональных чисел обозначается $\mathbb{Q}$, среди них выделяются двоично-рациональные числа (конечные двоичные дроби), имеющие вид $m/2^n$ при целых $m$ и $n$.

Число элементов в конечном множестве $A$ обозначается $|A|$.

Если основание логарифмов не указано явно, $\log x$ обозначает логарифм по основанию 2 (как обычно, $\ln x$ — натуральный логарифм).

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

Как обычно, запись $f \le g + O(1)$ (где $f$ и $g$ — выражения, которые могут содержать переменные) означает, что существует число $c$, для которого $f \le g + c$ при всех значениях переменных. Аналогичным образом $f \le g + O(h)$ (при неотрицательном $h$) означает, что при некотором $c$ и при всех значениях переменных выполняется неравенство $f \le g + ch$. Запись $f = g + O(h)$ (при неотрицательном $h$) означает, что при некотором $c$ и при всех значениях переменных выполняется неравенство $|f - g| \le ch$. В частности, $f = O(h)$ означает, что $|f| \le ch$ для некоторой константы $c$; запись $f = \Omega(h)$ означает, что $|f| \ge ch$ для некоторой константы $c > 0$ (обычно выражение $f$ положительно), а $f = \Theta(h)$ означает, что $c_1 h \le |f| \le c_2 h$ (также обычно используется для неотрицательного $f$).

Через $\mathbb{B}$ мы обозначаем множество $\{0, 1\}$. Конечные последовательности нулей и единиц называются двоичными словами, их множество мы обозначаем $\Xi$. Для любого конечного множества (алфавита) $A$ через $A^n$ обозначается множество всех слов алфавита $A$ длины $n$, то есть множество всех последовательностей длины $n$, составленных из элементов множества $A$ (букв алфавита $A$). Через $A^*$ обозначается множество слов всех длин (включая пустое слово $\Lambda$ длины 0), так что, например, $\Xi = \mathbb{B}^*$. Длина слова $x$ обозначается $l(x)$. Через $ab$ мы обозначаем конкатенацию слов $a$ и $b$, то есть результат приписывания слова $b$ справа к слову $a$. Говорят, что слово $a$ является началом, или префиксом, слова $b$, если $b = ax$ для некоторого слова $x$. Говорят, что $a$ является концом, или суффиксом, слова $b$, если $b = xa$ для некоторого слова $x$. Говорят, что $a$ является подсловом слова $b$, если $b = xay$ для некоторых слов $x$ и $y$ (другими словами, если $a$ является началом конца $b$ или концом начала $b$).

Мы рассматриваем также бесконечные последовательности нулей и единиц. Множество таких последовательностей мы называем $\Omega$. Для всякого двоичного слова $x$ можно рассмотреть множество всех бесконечных последовательностей, на-
чинающихся на х. Это множество обозначается $\Omega_x$. Множества такого вида называются интервалами. Естественным образом определяется конкатенация двоичного слова и бесконечной последовательности нулей и единиц. Рассматриваются также бесконечные последовательности букв произвольного алфавита $A$; их множество обозначается $A^\infty$.

Иногда полезно рассматривать вместе конечные и бесконечные последовательности. Мы используем обозначение $\Sigma$ для множества конечных и бесконечных последовательностей нулей и единиц (так что $\Sigma = \Xi \cup \Omega$). Через $\Sigma_x$ мы обозначаем множество всех конечных и бесконечных продолжений (конечного) слова $x$.

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

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

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

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

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

Мы рассматриваем *меры* (распределения вероятностей) на пространстве $\Omega$; они задаются своими значениями на интервалах $\Omega_x$ и потому мы отождествляем их с неотрицательными действительными функциями $p$ на словах, для которых $p(\Lambda) = 1$, а $p(x) = p(x0) + p(x1)$ для любого $x$, и говорим о мерах на двоичном дереве. Мы рассматриваем также полумеры на двоичном дереве, то есть распре-
деления вероятностей на конечных и бесконечных последовательностях. Они соответствуют функциям p, для которых $p(\Lambda) = 1$ и $p(x) \ge p(x_0) + p(x_1)$. Мы также говорим о полумерах на натуральных числах, имея в виду последовательности $p_i$ неотрицательных действительных чисел, для которых $\sum_{i \in N} p_i \le 1$. Можно отложить такие последовательности с распределениями вероятностей на множестве $N_\perp$, содержащим натуральные числа и дополнительный символ $\perp$ («неопределённое значение»).

Среди полумер (на дереве и на натуральных числах) выделяются перечислимые снизу. В каждом из этих двух классов существует наибольшая полумера (с точностью до умножения на константу). Она называется *априорной вероятностью* (на дереве или на натуральных числах). Априорная вероятность натурального числа *n* обозначается обычно $m(n)$; априорная вероятность вершины дерева *x* (двоичного слова *x*) обозначается обычно *a(x)*. Иногда мы говорим также о значении *m(x)* для двоичного слова *x*, имея в виду вычислимое взаимно однозначное соответствие между двоичными словами и натуральными числами.

Для различных видов колмогоровской сложности используются такие обозначения: $KS(x)$ обозначает простую колмогоровскую сложность (в англоязычной литературе обычно пишут $C(x)$). Префиксная сложность обозначается $KP(x)$ или $KP'(x)$, если мы хотим подчеркнуть, что мы используем определение с беспефиксными способами описания. (В англоязычной литературе обычно используется обозначение $K(x)$.) Те же буквы используются для сложности пар, троек и т. д., а также условной сложности. Например, $KS(x|y)$ есть условная сложность (обычная, не префиксная) слова *x* при известном *у*, а $m(x,y|z)$ есть априорная вероятность пары $(x,y)$ (точнее, натурального числа, соответствующего ей) при известном $z$. Для монотонной сложности используется обозначение $KM$, априорная сложность (минус логарифм априорной вероятности на дереве) обозначается $KA$. (В англоязычной литературе используются обозначения $Km$ и даже $K_m$ для монотонной сложности и $KM$ для априорной сложности.) Наконец, сложность разрешения мы обозначаем $KR$.

Максимальное время работы оптимального декомпрессора на программах длины не более *n* мы обозначаем $BB(n)$ (в префиксном варианте $BP(n)$), эта величина тесно связана с максимальным натуральным числом, имеющим сложность не выше *n*, которое обозначается $B(n)$.

Мы используем также некоторые топологические понятия. Пространство $N_\perp$ состоит из натуральных чисел с добавленным к ним элементом $\perp$ (неопределённость); открытым считается всё пространство, а также любые множества, не содержащие $\perp$. Это пространство, наряду с пространством $\Sigma$ (открытыми множествами являются объединения множеств вида $\Sigma_\chi$) используется в общей схеме классификации сложностей. В пространствах последовательностей и действительных чисел мы говорим об эффективно открытых множествах, имея в виду объединения перечислимых семейств интервалов (или множествах вида $\Sigma_\chi$ и интервалов с рациональными концами).

Большинство понятий теории вычислимости (в том числе и связанных с колмогоровской сложностью) допускает релятивизацию, когда во всех алгоритмах решается обращение к внешней процедуре, оракулу. Эта процедура отвечает на
вопросы о принадлежности к некоторому множеству А, которое тоже называют оракулом. Соответствующие понятия называют «разрешимостью с оракулом А», «перечислимостью с оракулом А» и т. д.; в обозначениях для сложности добавляют верхний индекс, скажем, простая сложность слова x с оракулом А обозначается $KS^A(x)$.

Из классической теории информации мы используем понятие шенноновской энтропии; для случайной величины $\xi$, принимающей k значений с вероятностями $p_1, \dots, p_k$, её энтропия $H(\xi)$ равна $-\sum_k p_k \log p_k$. Это определение имеет смысл и для пар величин, и с его использованием условная энтропия величины $\xi$ при известной $\eta$ определяется как $H(\xi, \eta) - H(\eta)$. Разность $H(\xi) + H(\eta) - H(\xi, \eta)$ называется взаимной информацией в случайных величинах $\xi$ и $\eta$ и обозначается $I(\xi:\eta)$. То же обозначение $I(x:y)$ употребляется для взаимной информации в алгоритмической теории, но поскольку она не в точности симметрична, то обычно читают его как «информация в x об y» и определяют как $KS(y) - KS(y|x)$.
## Литература

[1] Ahlswede R., Cai N., Li S. R., Yeung R., Network Information Flow, *IEEE Transactions on Information Theory*, v. 46 (2000), no. 4, p. 1204–1216.

[2] Ahlswede R., Körner J., On common information and related characteristics of correlated information sources, Preprint, Presented at the 7th Prague Conference on Information Theory (1974).

[3] Alon N., Newman I., Shen A., Tardos G., and Vereshchagin N., Partitioning multi-dimensional sets in a small number of "uniform" parts, *European Journal of Combinatorics*, v. 28 (2007), p. 134–144.
Предварительная версия: ECCC<fnref n="1" /> TR05-095 (2005).

[4] Becher V., Figueira S., and Picchi R., Turing unpublished algorithm for normal numbers, *Theoretical Computer Science*, v. 377 (2007), no. 1–3, p. 126–138.

[5] Bennett C. H., Gács P., Li M., Vitányi P. M. B., and Zurek W., Information distance, *IEEE Trans. Information Theory*, v. 44 (1998), no. 4, p. 1407–1423.
Предварительная версия: Thermodynamics of computation and information distance, *Proc. 25th ACM Symp. on Theory of Computing* (STOC 1993), p. 21–30.

[6] Bienvenu L., *Game-theoretic characterization of randomness: unpredictability and stochasticity*, Ph.D. thesis, University of Marseille, 2008.

[7] Bienvenu L., Downey R., Kolmogorov complexity and Solovay functions, *Electron-ic Proc. 26th Symp. on Theoretical Aspects of Computer Science* (STACS 2009), stacs2009.informatik.uni-freiburg.de/proceedings.php

[8] Бьенвеню Л., Гач П., Хойруп М., Рохас К., Шень А., Алгоритмические тесты и слу-чайность относительно классов мер. *Труды МИАН*<fnref n="2" />, т. 274 (2011), с. 41-102.
Английский вариант: Bienvenu L., Gács P., Hoyrup M., Rojas C., and Shen A., Algo-rithmic tests and randomness with respect to a class of measures, *Proc. of the Steklov Institute of Mathematics*, v. 274 (2011), p. 41–102. См. также: arXiv:1103.1529v2.

[9] Bienvenu L., Muchnik An., Shen A., Vereshchagin N.K., Limit complexities revisited, *Theory of Computing Systems*, v. 47 (2010), no. 3, p. 720–736.
См. также: arXiv:0802.2833. Исправленная версия (включая более простые доказа-тельства более сильных утверждений): arXiv:1204.0201

[10] Bienvenu L., Sablik M., The dynamics of cellular automata in shift-invariant topologies, *Proc. 11th Conference on Developments in language theory* (DLT 2007), LNCS<fnref n="3" /> v. 4588, p. 84–95.

<footnote n="1">¹ECCC = Electronical Colloquium on Computational Complexity. Опубликованные в ECCC статьи вы-ложены в eccc.hpi-web.de.</footnote>

<footnote n="2">²МИАН = Математический институт им. В. А. Стеклова Академии Наук</footnote>

<footnote n="3">³LNCS = Lecture Notes in Computer Science.</footnote>
[11] Bienvenu L., Shafer G., Shen A., On the history of martingales in the study of randomness, *Electronic Journal for History of Probability and Statistics*, v. 5 (2009), no. 1, p. 1–40, www.jehps.net/juin2009/BienvenuShaferShen.pdf
Более подробное изложение: Bienvenu L., Shen A., Algorithmic information theory and martingales, arXiv:0906.2614.

[12] Борель Э., Случай, Перевод с франц., М., Петроград: Госиздат, 1923, 215 с. (Современные проблемы естествознания. Кн. 8.)

[13] Борель Э., Вероятность и достоверность, Перевод с франц., 3-е изд. М.: Наука, 1969. 112 с.

[14] Buhrman H., Fortnow L., Laplante S., Resource-bounded Kolmogorov complexity revisited, *SIAM Journal on Computing*, v. 31 (2002), no. 3, p. 887-905.

[15] Buhrman H., Fortnow L., Newman I., Vereshchagin N., Increasing Kolmogorov complexity. *Proc. 22nd Symp. on Theoretical Aspects of Computer Science* (STACS 2005), LNCS v. 3404, p. 412–421.
Предварительная версия: ECCC TR04-081 (2004).

[16] Calude C.S., *Information and randomness: an algorithmic perspective*. 2nd ed., Springer-Verlag, 2002 (first edition, 1994), 450 pp. ISBN 3-540-43466-6.

[17] Calude C.S., Hertling P., Khoussainov B., Wang, Y., Recursively enumerable reals and Chaitin Omega numbers, *Proc. 15th Symp. on Theoretical Aspects of Computer Science* (STACS 1998), LNCS v. 1373, p. 596–606.

[18] Calude C. S., Staiger L. and Terwijn S., On partial randomness. *Annals of Pure and Applied Logic*, v. 138 (2006), no. 1-3, p. 20–30.

[19] Chaitin G. J., On the length of programs for computing binary sequences, *Journal of the ACM*, v. 13 (1966), no. 4, p. 547–569.

[20] Chaitin G. J., On the length of programs for computing binary sequences: statictical considerations, *Journal of the ACM*, v. 16 (1969), no. 1, p. 145–159.

[21] Chaitin G. J., Computational complexity and Gödel's incompleteness theorem, *ACM SIGACT News*, no. 9 (1971), p. 11–12.

[22] Chaitin G. J., Information-theoretic limitations of formal systems, *Journal of the ACM*, v. 21 (1974), no. 3, p. 403–424.

[23] Chaitin G. J., A theory of program size formally identical to information theory, *Journal of the ACM*, v. 22 (1975), no. 3, p. 329–340.

[24] Chaitin G. J., Incompleteness theorems for random reals, *Advances in Applied Mathematics*, v. 8 (1987), p. 119–146.

[25] Chaitin G. J., *Algorithmic information theory*, Cambridge University Press, 1987. Third printing, 1990.

[26] Champernowne D. G., The construction of decimals normal in the scale of ten, *Journal of the London Mathematical Society*, v. 8 (1933), p. 254–260.

[27] Chan T. H., Yeung R. W., On a relation between information inequalities and group theory, *IEEE Transactions on Information Theory*, v. 48 (2002), no. 7, p. 1992–1995.

[28] Chernov A., Muchnik An. A., Romashchenko A., Shen A., Vereshchagin N. K. Upper semi-lattice of binary strings with the relation “x is simple conditional to y”. *Theoretical Computer Science*, v. 271 (2002), no. 1–2, p. 69–95.
Предварительная версия: Proc. 14th IEEE Conference on Computational Complexity (CCC 1999), p. 114–122.
[29] Chernov A., Hutter M., Schmidhuber J., Algorithmic complexity bounds on future prediction errors, *Information and Computation*, v. 205 (2007), p. 242–261. DOI 10.1016/j.ic.2006.10.004, см. также arXiv:cs/0701120.

[30] Chernov A., Shen A., Vereshchagin N., Vovk V., On-line Probability, Complexity and Randomness, *Proc. 19th Conference on Algorithmic Learning Theory* (ALT 2008), p. 138–153.

[31] Chung F. R. K., Graham R. L., Frankl P., Shearer J. B., Some intersection theorems for ordered sets and graphs. *Journal of Combinatorial Theory, A*, v. 43 (1986), p. 23–37.

[32] Church A., On the concept of a random sequence. *Bull. Amer. Math. Soc*, v. 46 (1940), no. 2, p. 130–135.

[33] Cormen T. H., Leiserson C. E., Rivest, R. L., Stein C., *Introduction to Algorithms*, 3 ed., Cambridge, MIT Press, 2009.

[34] Daley R.P., Minimal-program complexity of pseudo-recursive and pseudo-random sequences, *Mathematical Systems Theory* (now *Theory of Computing Systems*), v. 9 (1975), no. 1, p. 83-94.

[35] David A. P., de Rooij S., Shafer G., Shen A., Vereshchagin N. K., and Vovk V., Insuring against loss of evidence in game-theoretic probability, *Statistics & Probability Letters*, v. 81 (2011), no. 1, p. 157–162. См. также: arXiv:1005.1811.

[36] Day, A., Increasing the gap between descriptional complexity and algorithmic probability, *Proc. 24th IEEE Conference on Computational Complexity* (CCC 2009), p. 263–273.
Более подробное изложение:
homepages.mcs.vuw.ac.nz/~adam/papers/day_monotone_a_priori.pdf.

[37] Downey R., Hirschfeldt D., *Algorithmic randomness and complexity*, Springer-Verlag, 2010, 855 pp. ISBN 978-0387955674.

[38] Downey R., Hirschfeldt D., Nies A., Terwijn S., Calibrating randomness., *The Bulletin of Symbolic Logic*, v. 12 (2006), no. 3, p. 411–491.

[39] Durand B., Levin L., Shen A., Complex tilings, *Journal of Symbolic Logic*, v. 73 (2007), no. 2, 593–613. См. также: arXiv:cs/0107008.

[40] Durand D., Shen A., and Vereshchagin N., Descriptive complexity of computable sequences, *Theoretical Computer Science*, v. 171 (2001), p. 47–58.
Предварительные версии: *Proc. 16th Symp. on Theoretical Aspects of Computer Science* (STACS 1999), LNCS v. 1563, p. 153–162 и ECCC TR01-087 (2001).

[41] Durand B. and Vereshchagin N., Kolmogorov – Loveland stochasticity for finite strings, *Information Processing Letters*, v. 91 (2004), p. 263–269.

[42] Fortnow L., Lee T., Vereshchagin N., Kolmogorov complexity with error, *Proc. 23rd Symp. Theoretical Aspects of Computer Science* (STACS 2006), LNCS v. 3884, p. 137–148.
Предварительная версия: ECCC TR04-080 (2004).

[43] Гач П., О симметрии алгоритмической информации. *Доклады АН СССР, т. 218* (1974), № 6, с. 1265–1267.
АНглийский перевод: Gács P., On the symmetry of algorithmic information. *Soviet Math. Dokl*, v. 15 (1974), no. 5, p. 1477-1480.

[44] Gács P., Exact expressions for some randomness test, *Zeitschrift für Math. Logik und Grundlagen d. Math.*, v. 26 (1980), p. 385–394.
[45] Gács P., On the relation between descriptional complexity and algorithmic probability, *Theoretical Computer Science*, 1983, v. 22, p. 71–93.
Предварительная версия: *Proc. 22nd Symp. on Foundations of Computer Science* (FOCS 1981), p. 296–303.

[46] Gács P., Every sequence is reducible to a random one, *Information and Control* (now *Information and Computation*), v. 70 (1986), no. 2–3, p. 186–192.

[47] Gács, P., and Körner, J. Common information is far less than mutual information, *Problems of Control and Information Theory*, v. 2 (1973), no. 2, p. 149–162.

[48] Goldreich O., *Foundations of Cryptography. V. 1. Basic Tools*. Cambridge University Press, Cambridge, 2007.

[49] Gorbunov K. Yu., On a complexity of the formula $A \lor B \Rightarrow C$, *Theoretical Computer Science*, v. 207 (1998), no. 2, p. 383–386.

[50] Халмош П., *Теория меры*, М.: ИЛ, 1953, 292 с.

[51] Hammer D., Romashchenko A., Shen A., Vereshchagin N., Inequalities for Shannon entropies and Kolmogorov complexities, *Journal of Computer and System Sciences*, v. 60 (2000), p. 442–464.
Предварительная версия: *Proc. 12th IEEE Conference on Computational Complexity* (CCC 1997), p. 13–23.

[52] Hammer D., Shen A., A strange application of Kolmogorov complexity, *Theory of Computing Systems*, v. 31 (1998), no. 1, p. 1–4.

[53] Hölzl R., Kräling T., Merkle W., Time-bounded Kolmogorov complexity and Solovay functions, *Proc. 34th Symp. Mathematical Foundations of Computer Science* (MFCS 2009), LNCS v. 5734, p. 392–402.

[54] Impagliazzo R., Shaltiel R., and Wigderson A., Extractors and pseudo-random generators with optimal seed length, *Proceedings of the 32nd ACM Symp. on the Theory of Computing* (STOC 2000), p. 1–10.

[55] Kakutani S., On equivalence of infinite product measures, *Annals of Mathematics*, Second Series, v. 49 (1948), no. 1, p. 214–224.

[56] Kalinina E., Prefix-free and prefix-correct complexities with compound conditions, *Proc. 5th Computer Science Symp. in Russia* (CSR 2010), LNCS v. 6072, p. 259–265.

[57] Karpovich P., Monotone complexity of a pair, *Proc. 5th Computer Science Symp. in Russia* (CSR 2010), LNCS v. 6072, p. 266–275.

[58] Kjos-Hanssen B., The probability distribution as a computational resource for randomness testing, *Open access Journal of Logic and Analysis*, v.2 (2010), logicanalysis.org/index.php/jla/article/view/78.

[59] Kjos-Hanssen B., Merkle W., Stephan F., Kolmogorov complexity and the recursion theorem, *Transaction of the American Mathematical Society*, v. 363 (2010), p. 5465–5480.
Предварительная версия: *Proc. 23rd Symp. on Theoretical Aspects of Computer Science* (STACS 2006), LNCS v. 3884, p. 149–161.

[60] Kleene S. C., On the interpretation of intuitionistic number theory. *Journal of Symbolic Logic*, v. 10 (1945), pp. 109–124.

[61] Kolmogoroff A., Zur Deutung der intuitionistischen Logik. *Mathematische Zeitschrift*, Bd. 35 (1932), H. 1, S. 58–65.
Русский перевод: К толкованию интуиционистской логики, в сборнике: Колмогоров А. Н., *Избранные труды. Математика и механика*, М.: Наука, 1985, с. 142–148.
[62] Kolmogorov A. N., On tables of random numbers, *Sankhyā, The Indian Journal of Statistics, Ser. A*, v. 25 (1963), no. 4, p. 369–376. Перепечатано в: *Theoretical Computer Science*, v. 207 (1998), no. 2, p. 387–395.

Русский перевод: О таблицах случайных чисел. *Семиотика и информатика*, 1982, вып. 18, с. 3–13, М.: ВИНИТИ. Перепечатано в: *Колмогоров А. Н., Теория информации и теория алгоритмов*, М.: Наука, 1987, с. 204–213.

[63] Колмогоров А. Н., Три подхода к определению понятия «количество информации», *Проблемы передачи информации*, т. 1 (1965), вып. 1, с. 3–11

Английский перевод: Kolmogorov A. N., Three approaches to the quantitative definition of information. *Problems Inform. Transmission*, v. 1 (1965), no. 1, p. 1–7.

[64] Колмогоров А. Н., К логическим основам теории информации и теории вероятностей, *Проблемы передачи информации*, т. 5 (1969), вып. 3, с. 3–7.

Несколько раньше опубликован английский перевод (переводчик не указан): Kolmogorov A. N., Logical basis for information theory and probability theory, *IEEE Trans. Inform. Theory*, v. 14 (1968), p. 662–664.

[65] Колмогоров А. Н., Комбинаторные основания теории информации и исчисления вероятностей [доклад на Международном математическом конгрессе (Ницца, 1970)], *Успехи математических наук*, т. 38 (1983), № 4, с. 27–36.

[66] Колмогоров А. Н., Фомин С. В. *Элементы теории функций и функционального анализа*, 4-е изд., М.: Наука, 1976, 544 с.

[67] Колмогоров А. Н., Успенский В. А., Алгоритмы и случайность, *Теория вероятностей и её применения*, т. 32 (1987), вып. 3, с. 425–455.

Английские переводы: Kolmogorov A. N. and Uspensky V. A., Algorithms and randomness, *SIAM J. Theory Probab. Appl.* v. 32 (1987) p. 389–412 [with annoying translation errors<fnref n="1" />]. Without annoying translation errors: Prokhorov Yu. V. and Sazonov V. V., Eds., *Proc. 1st World Congress of the Bernoulli Society* (Tashkent 1986), v. 1: Probab. Theory and Appl., VNU Science Press, Utrecht 1987, p. 3–55.

[68] *Колмогоров и кибернетика*. Под ред. Д. А. Поспелова, Я. И. Фета. Новосибирск: издательство ИВМ и МГ СО РАН, 2001. (Вопросы истории информатики, вып. 2). Стенограмма доклада Колмогорова в Институте философии АН СССР (23 апреля 1965 года) опубликована на с. 118–137. Её также можно найти (октября 2014) по адресу http://cshistory.nsu.ru/?int=VIEW&el=1832&templ=INTERFACE.

[69] Kučera A., Measure, $\Pi_1$-classes and complete extensions of PA, in сборнике: Ebbinghaus H.-D., Müller G. H. and Sacks G. E. (Eds.), *Recursion Theory Week (Oberwolfsach, 1984)*, Lecture Notes in Mathematics, v. 1141 (1985), p. 245–259.

[70] Kučera A., Slaman T., Randomness and recursive enumerability, *SIAM Journal on Computing*, v. 31 (2001), no. 1, p. 199–211.

[71] Kuipers L., Niederreiter H., *Uniform distribution of sequences*, Wiley-Interscience, 1949.

[72] Kummer M., On the complexity of random strings, *Proc. 13th Symp. on Theoretical Aspects of Computer Science* (STACS 1996), LNCS v. 1046, p. 25–36.

[73] van Lambalgen M., *Random sequences*, Ph. D. Thesis, University of Amsterdam, 1987.

[74] de Leeuw K., Moore E. F., Shannon C. E., and Shapiro N., Computability by probabilistic machines, in сборнике: C. E. Shannon and J. McCarthey (Eds.), *Automata Studies*, Princeton University Press, Princeton, New Jersey, 1956, p. 183–212.

<footnote n="1">¹Some of those errors drastically distort meaning; e. g. Russian term перечислимый, which should be translated as enumerable, or recursively enumerable, was translated as countable.</footnote>
[75] Левин Л. А., О понятии случайной последовательности, Доклады АН СССР, т. 212 (1973), № 3, с. 548–550.
Английский перевод: Levin L.A., On the notion of a random sequence, *Soviet Math. Dokl.*, v. 14 (1973), p. 1413–1416.

[76] Левин Л. А., Законы сохранения (невозрастания) информации и вопросы обоснования теории вероятностей, Проблемы передачи информации, т. 10 (1974), вып. 3, с. 30–35.
Английский перевод: Levin L. A., Laws of information conservation (nongrowth) and aspects of the foundation of probability theory, *Problems of Information Transmission*, v. 10 (1974), p. 206–210.

[77] Левин Л. А., О различных мерах сложности конечных объектов (аксиоматическое описание), Доклады АН СССР, т. 227 (1976), № 4, с. 804–807.
Английский перевод: Levin L. A., Variuos measures of complexity for finite objects (axiomatic description), *Soviet Math. Dokl.*, v. 17 (1976), p. 522–526.

[78] Левин Л. А. О принципе сохранения информации в интуиционистской математике, Доклады АН СССР, т. 227 (1976), № 6, с. 1293-1296.
Английский перевод: Levin L. A., On the principle of conservation of information in intuitionistic mathematics, *Soviet Math. Dokl.*, v. 17 (1976), no. 2, p. 601–605

[79] Левин Л. А., Равномерные тесты случайности, Доклады АН СССР, т. 227 (1976), № 1, с. 33-35.
Английский перевод: Levin L.A., Uniform tests of randomness, *Soviet Math. Dokl.*, v. 17 (1976), issue 2, p. 337-340.

[80] Левин Л. А., Об одном конкретном способе задания сложностных мер, Доклады АН СССР, т. 234 (1977), № 3, с. 536–539.
Английский перевод: On a concrete method of assigning complexity measures, *Soviet Math. Dokl.*, v. 18 (1977), no. 3, p. 727–731.

[81] Levin L. A., A concept of independence with application in various fields of mathematics, MIT Technical Report, MIT/LCS/TR-235, 1980, 21 p.

[82] Levin L. A., Randomness conservation inequalities: information and independence in mathematical theories, *Information and Control*, v. 61 (1984), no. 1–2, p. 15–37.

[83] Levin L. A., Vyugin V. V., Invariant properties of informational bulks, *Proc. 6th Symp. on Mathematical Foundations of Computer Science* (MFCS 1977), LNCS v. 153, p. 359–364.

[84] Levin L. A., Forbidden information, 2002, 8 pp., arXiv:cs/0203029.
Предварительная версия: *Proc. 43th IEEE Symp. on Foundations of Computer Science* (FOCS 2002), p. 761–768.

[85] Li M., Vitányi P., *An Introduction to Kolmogorov complexity and its applications*, 3rd ed., Springer, 2008 (1 ed., 1993; 2 ed., 1997), 792 pp. ISBN 978-0-387-49820-1.

[86] Li S. R., Yeung R. W., Cai N., Linear network coding, *IEEE Transactions on Information Theory*, v. 49 (2003), no. 2, p. 371–381.

[87] Loomis L. H., Whitney H., An inequality related to the isoperimetric inequality, *Bulletin American Mathematical Society*, v. 55 (1949), p. 961–962.

[88] Loveland D. W., A new interpretation of von Mises' concept of a random sequence, *Z. Math. Logik und Grundlagen d. Math.*, v. 12 (1966), p. 279–294.

[89] Loveland D. W., The Kleene hierarchy classification of recursively random sequences, *Trans. Amer. Math. Soc.*, v. 125 (1966), p. 497–510.
[90] Loveland D. W., A Variant of the Kolmogorov concept of complexity, *Information and Control* (now *Information and Computation*), v. 15 (1969), p. 510–526.

[91] Loveland D. W., On minimal-program complexity measures, *Proc. 1st ACM Symp. on Theory of Computing* (STOC 1969), p. 61–65.

[92] Lutz J., Dimension in complexity classes, *SIAM Journal on Computing*, v. 32 (2003), p. 1236–1259.
Предварительная версия: *Proc. 15th IEEE Conference on Computational Complexity* (CCC 2000), p. 158–169.

[93] Lutz J. H., The dimensions of individual strings and sequences, *Information and Compu-tation*, v. 187 (2003), no. 1, p. 49–79.
Предварительная версия: Gales and the constructive dimension of individual sequences, *Proc. 27th Colloquium on Automata, Languages, and Programming* (ICALP 2000), LNCS v. 1853, p. 902–913.

[94] Makarychev K., Makarychev Yu., Chain independence and common information. *IEEE Transactions on Information Theory*, v. 58 (2012), no. 8, p. 5279–5286.
См. также: *Conditionally independent random variables*, arXiv:cs/0510029.

[95] Makarychev K., Makarychev Yu., Romashchenko A., Vereshchagin N., A new class of non-Shannon-type inequalities for entropies, *Communications in Information and Systems*, v. 2 (2002), no. 2, p. 147–166.

[96] Манин Ю.И. Вычислимое и невычислимое, М.: Советское радио, 1980, 128 с.

[97] Martin-Löf P., The definition of random sequences, *Information and Control* (now *Information and Computation*), v. 9 (1966), p. 602–619.

[98] Martin-Löf P., Algorithmen und zufällige Folgen, Vier Vorträge von Per Martin-Löf (Stockholm) gehalten am Mathematischen Institut der Universität Erlangen–Nürnberg, Als Manuskript vervielfältigt, Erlangen, 1966, 61 pp, см. также www/probabilityandfinance.com/misc/erlangen.pdf.

[99] Martin-Löf P., Complexity oscillations in infinite binary sequences, *Z. Wahrscheinlichkeitstheorie verw. Geb.*, v. 19 (1971), p. 225–230.

[100] Mayordomo E., A Kolmogorov complexity characterization of constructive Hausdorff dimension, *Information Processing Letters*, v. 84 (2002), no. 1, p. 1–3.

[101] Merkle W. The Kolmogorov–Loveland stochastic sequences are not closed under selecting subsequences, *Journal of Symbolic Logic*, v. 68 (2003), p. 1362–1376.
Предварительная версия: *Proc. 29th Colloquium on Automata, Languages, and Programming* (ICALP 2002), LNCS v. 2380, p. 390–400.

[102] Merkle W., The complexity of stochastic sequences, *Proc. 18th IEEE Conference on Computational Complexity* (CCC 2003), p. 230–235.

[103] Miller J., Every 2-random real is Kolmogorov random, *Journal of Symbolic Logic*, v. 69 (2004), no. 3, p. 907–913.

[104] Miller J., Contrasting plain and prefix-free Kolmogorov complexity, (preprint from 2006), www.math.wisc.edu/~jmiller/Notes/contrasting.pdf.

[105] Miller J., Yu L., On initial segment complexity and degrees of randomness, *Transactions of the American Mathematical Society*, v. 360 (2008), no. 6, p. 3193–3210.

[106] Miller J., Two notes on subshifts, *Proceedings of the American Mathematical Society*, v. 140 (2012), no. 5, p. 1617–1622. См. также www.math.wisc.edu/~jmiller/Papers/subshifts.pdf
[107] von Mises R., Grundlagen der Wahrscheinlichkeitsrechnung, *Mathematische Zeitschrift*, Bd. 5 (1919), S. 52–99. Перепечатано в книге: Selected Papers of Richard von Mises. Volume Two. Probability and Statistics, General. American Mathematical Society, 1964. p. 57–106.

[108] von Mises R., *Wahrscheinlichkeit, Statistik und Wahrheit*, Wien: Springer-Verlag, 1928, 189 p.
Русский перевод: Мизес Р., *Вероятность и статистика*, М. – Л.: Госиздат, 1930.

[109] von Mises R., On the foundations of probability and statistics, *Annals of Mathematical Statistics*, v. 12 (1941), p. 191–205. Перепечатано в книге: Selected Papers of Richard von Mises. Volume Two. Probability and Statistics, General. American Mathematical Society, 1964. p. 340–355.

[110] von Mises R., Doob J. L., Discussion of papers on probability theory. *Annals of Mathematical Statistics*, v. 12 (1941), p. 215–217. (Перепечатано в книге: Selected Papers of Richard von Mises. Volume Two. Probability and Statistics, General. American Mathematical Society, 1964, p. 356–359.)

[111] Moser R.A., A constructive proof of the Lovasz Local Lemma. *Proc. 41st ACM Symp. on Theory of Computing* (STOC 2009), p. 343–350, см. также arXiv:0810.4812.

[112] Moser R.A., Tardos G., A constructive proof of the general Lovasz Local Lemma, *Journal of the ACM*, v.57 (2010), no. 2, p. 11.1–11.15, см. также arXiv:0903.0544.

[113] Мучник Ан. А. Об основных структурах дескриптивной теории алгоритмов. *Доклады АН СССР*, 1985, т. 285, № 2, с. 280–283.
Английский перевод: Muchnik An. A., On the basic structures of the descriptive theory of algorithms, *Soviet Math. Dokl.*, v. 32 (1985), no. 3, p. 671–674.

[114] Мучник Ан. А., Нижние пределы частот в вычислимых последовательностях и реля-
тивизованная ариорная вероятность, *Теория вероятностей и её применения*, т. 32
(1987), № 3, с. 563–565.

Английский перевод: Muchnik An. A., Lower limits on frequences in computable se-
quences and relativized a priori probability, *SIAM Theory Probab. Appl.*, v. 32 (1987)
p. 513–514.

[115] Muchnik An. A., On common information, *Theoretical Computer Science*, v. 207, no. 2 (1998), p. 319–328.

[116] Muchnik An. A. Conditional complexity and codes, *Theoretical Computer Science*, v. 271 (2002), no. 1–2, p. 97–109.

Предварительная версия: Muchnik A., Semenov A., Multi-conditional descriptions and codes in Kolmogorov complexity, ECCC TR00-015 (2000).

[117] Muchnik An. A., Mezhirov I., Shen A., Vereshchagin N. K., *Game interpretation of Kolmogorov complexity*, 2010, arXiv:1003.4712.

[118] Muchnik An. A., Positselsky S. E., Kolmogorov entropy in the context of computability theory, *Theoretical Computer Science*, v. 271 (2002), no. 1–2, p. 15–35.

[119] Мучник Ан. А., Ромащенко А. Е., Устойчивость колмогоровских свойств при реля-
визации. Проблемы передачи информации, т. 46, вып. 1 (2010), с. 42–67.
Английский перевод: Muchnik An. A., Romashchenko A., Stability of properties of Kol-
mogorov complexity under relativization. *Problems of Information Transmission*, v. 46,
no. 1 (2010), p. 38–61.

Предварительная версия: Muchnik An. A., Romashchenko A., Random oracle does not help extract the mutual information, *Proc. 33rd Symp. on Mathematical Foundations of Computer Science* (MFCS 2008), LNCS v. 5162, p. 527–538.
[120] Muchnik An. A., Semenov A. L., Uspensky V. A., Mathematical metaphysics of randomness, *Theoretical Computer Science*, v. 207, no. 2 (1998), p. 263–317.

[121] Muchnik An. A., Shen A., Ustinov M., Vereshchagin N. K., Vyugin M., Non-reducible descriptions for conditional Kolmogorov complexity. *Theoretical Computer Science*, v. 384 (2007), no. 1, p. 77–86.
Предварительные версии: Muchnik An. A., Shen A., Vereshchagin N. K., Vyugin M., Non-reducible descriptions for conditional Kolmogorov complexity, Proc. 3rd Conference on Theory and Applications of Models of Computation (TAMC 2006), LNCS v. 3959, p. 308–317 и ECCC TR04-054 (2004).

[122] Muchnik An. and Vereshchagin N., Shannon entropy vs. Kolmogorov complexity, Proc. 1st Computer Science Symp. in Russia (CSR 2006), LNCS v. 3967, p. 281–291.

[123] Musatov D., Improving the space-bounded version of Muchnik's conditional complexity theorem via "naive" derandomization, Proc. 6th Computer Science Symp. in Russia (CSR 2011), LNCS v. 6651, p. 64–76.

[124] Musatov D., Space-bounded Kolmogorov extractors, Proc. 7th Computer Science Symp. in Russia (CSR 2012), LNCS v. 7353, p. 266–277.

[125] Musatov D., Romashchenko A., Shen A., Variations on Muchnik's conditional complexity theorem, Theory Comput. Syst., v. 49 (2011), no.2, p. 227–245.
Предварительная версия: Proc. 4th Computer Science Symp. in Russia (CSR 2009), LNCS v. 5675, p. 250–262.

[126] Niederreiter H., A combinatorial problem for vector spaces over finite fields, Discrete Mathematics, v. 96 (1991), no. 3, p. 221–228.

[127] Nies A., Computability and randomness, Oxford University Press, 2009, 420 pp. ISBN 978-0-19-923076-1

[128] Nies A., Stephan F., Terwijn S., Randomness, relativization and Turing degrees, Journal of Symbolic Logic, v. 70 (2005), no. 2, p. 515–535.

[129] Razenshteyn I., Common information revisited, 2012, arXiv:1104.3207.

[130] Reimann J., Computability and fractal dimension, PhD thesis, Ruprecht-Karls Universität Heidelberg, 2004 (URN: urn:nbn:de:bsz:16-opus-55430), см. www.ub.uni-heidelberg.de/archiv/5543.

[131] Ромашенко А. Е., Пары слов с нематериализуемой взаимной информацией, Проблемы передачи информации, т. 36 (2000), вып. 1, с. 3–20.
Английский перевод: Romashchenko A., Pairs of words with nonmaterializable mutual information, Problems of Information Transmission, v. 36 (2000), no. 1, p. 3–20.

[132] Romashchenko A. Extracting the mutual information for a triple of binary strings. Proc. 18th IEEE Conference on Computational Complexity (CCC 2003), p. 221–235.

[133] Ромашенко А., Румянцев А., Шень А., Заметки по теории кодирования, Изд-во МЦНМО, 2011, 80 с.

[134] Romashchenko A., Shen A., Vereshchagin N., Combinatorial interpretaion of Kolmogorov complexity, *Theoretical Computer Science*, v. 271 (2002), no. 1–2, p. 111–123.
Предварительные версии: Proc. 15th IEEE Conference on Computational Complexity (CCC 2000), p. 131–137 и ECCC TR00-026 (2000).

[135] Rumyantsev A., Kolmogorov complexity, Lovasz Local Lemma and critical exponents, Proc. 2nd Computer Science Symp. in Russia (CSR 2007), LNCS v. 4649, p. 349–355.
См. также: arXiv:1009.4995.
[136] Rumyantsev A., *Infinite computable version of Lovasz Local Lemma*, 2010, arXiv:1012.0557.

[137] Rumyantsev A., Ushakov M., *Forbidden substrings, Kolmogorov complexity and almost periodic sequences*, *Proc. 23rd Symp. on Theoretical Aspects of Computer Science* (STACS 2006), LNCS v. 3884, p. 396–407. См. также: arXiv:1009.4455.

[138] Schmidt W., *On normal numbers*, *Pacific Journal of Mathematics*, v. 10 (1960), no. 2, p. 661–672.

[139] Schnorr C. P., *Eine Bemerkung zum Begriff der zufälligen Folge. Zeitschrift für Wahrscheinlichkeitstheorie und Verw. Gebiete*, v. 14 (1969), p. 27–35.

[140] Schnorr C. P., *Über die Definition effektiver Zufallstests. Teil I. Zeitschrift für Wahrscheinlichkeitstheorie und Verw. Gebiete*, v. 15 (1970), p. 297–312.

[141] Schnorr C. P., *Über die Definition effektiver Zufallstests. Teil II. Zeitschrift für Wahrscheinlichkeitstheorie und Verw. Gebiete*, v. 15 (1970), p. 313–328.

[142] Schnorr C. P., *Klassifikation der Zufallsgesetze nach Komplexität und Ordnung*, Zeitschrift für Wahrscheinlichkeitstheorie und Verw. Gebiete, v. 16 (1970), p. 1–21.

[143] Schnorr C. P., *Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie*, Lecture Notes in Mathematics, v. 218, IV+212 S, Springer, 1971.

[144] Schnorr C. P., *A unified approach to the definition of random sequences*, *Mathematical Systems Theory* (now *Theory of Computing Systems*), v. 5 (1971), no. 3, p. 246–258.

[145] Schnorr C. P., *Optimal Gödel numberings*. Proc. IFIP congress 71 (1971), v. 1, p. 56–58.

[146] Schnorr C. P., *Process complexity and effective random tests*, *Journal of Computer and System Sciences*, v. 7 (1973), p. 376–388.

Предварительная версия: Proc. 4th ACM Symp. on Theory of Computing (STOC 1972), p. 168–176.

[147] Schnorr C. P., *Optimal enumerations and optimal Gödel numberings*, *Mathematical Systems Theory* (now *Theory of Computing Systems*), v. 8 (1975), no. 2, p. 182–191.

[148] Shafer G., Shen A., Vereshchagin N. K., Vovk V., Test martingales, Bayes factors, and p-values, *Statistical Science* v. 26 (2011), no. 1, p. 84–101. См. также arXiv:0912.4269.

[149] Shafer G., Vovk V. *Probability and finance: it's only a game!* New York: Wiley, 2001.

[150] Шень А., *Аксиоматическое описание понятия энтропии конечного объекта, Логика и основания математики*. Тезисы VIII Всесоюзной конференции «Логика и методология науки», г. Паланга, 26–28 сентября 1982 г., Вильнюс, 1982, с. 104–105.

[151] Шень А., *К логическим основам применения теории вероятностей*, *Семиотические аспекты формализации интеллектуальной деятельности*, Школа-семинар, г. Тельави, 29 октября–6 ноября 1983 г., с. 144–146.

[152] Шень А., *Алгоритмические варианты понятия энтропии*, Доклады АН СССР, т. 276 (1984), № 3, с. 563–566.

Английский перевод: Shen A., *Algoritmic variants of the notion of entropy*, *Soviet Math. Dokl.*, v. 29 (1984), no. 3, p. 569–573.

[153] Шень А., *О соотношениях между различными алгоритмическими определениями слухачности*, Доклады АН СССР, т. 302 (1988), № 3, с. 548–552.

Английский перевод: Shen A., *On relations between different algorithmic definitions of randomness*, *Soviet Math. Dokl.*, v. 38 (1989), no. 2, p. 316–319.
[154] Shen A., Algorithmic information theory and Kolmogorov complexity, kecture notes, http://www.it.uu.se/research/publications/reports/2000-034.

[155] Shen A., Multisource algorithmic information theory, *Proc. 3rd Conference on Theory and Applications of Models of Computation* (TAMC 2006), LNCS v. 3959, p. 327–338.

[156] Shen A., Algorithmic information theory and foundations of probability, *Proc. 3rd Workshop on Reachability Problems* (2009), LNCS v. 5797, p. 26–34.

[157] Shen A. and Vereshchagin N., Logical operations and Kolmogorov complexity, *Theoretical Computer Science*, v. 271 (2002), p. 125–129.
Предварительная версия: ECCC TR01-088 (2001).

[158] Sipser M., *Introduction to the theory of computation*, PWS Publishing, 1996.

[159] Slepian D., Wolf J. K., Noiseless coding of correlated information sources, *IEEE Transactions on Information Theory*, v. IT-19 (1973), no. 4, p. 471–480.

[160] Solomonoff R. J., A formal theory of inductive inference, part 1, part 2. *Information and Control* (now *Information and Computation*), v. 7 (1964), p. 1–22, p. 224–254.

[161] Solovay R., *Draft of a paper (or series of papers) on Chaitin's work*, done for the most part during Sept. – Dec. 1974, unpublished (but available to many people in the field).

[162] Solovay R. M., On Random R.E. Sets, in сборнике: A.I. Arruda, N.C.A. da Costa, R. Chaqui (Eds.), Non-classical logics, model theory and computability, North-Holland, Amsterdam, 1977, p. 283–307.

[163] Tadaki K., A generalization of Chaitin's halting probability Ω and halting self-similar sets, *Hokkaido mathematical journal*, v. 31 (2002), no. 1, p. 219–253. См. также: arXiv:nlin/0212001.

[164] Takahashi H., On a definition of random sequences with respect to conditional probability, *Information and Computation*, v. 206 (2008), no. 12, p. 1375–1382.

[165] Takahashi H., Algorithmic randomness and monotone complexity on product space, *Information and Computation*, v. 209 (2011), no. 2, p. 183–197, dx.doi.org/10.1016/j.ic.2010.10.003. См. также arXiv.org:0910.5076.

[166] Успенский В. А., Семёнов А. Л., *Алгоритмы: основные идеи и приложения*, М.: Наука, 1987, 288 с.
Английский перевод: Uspensky V., Semenov A., *Algorithms: main ideas and applications*, translated by A. Shen, Kluwer Academic Publishers, 1993, 269 pp. ISBN: 0-7923-2210-X.

[167] Успенский В. А., Семёнов А. Л., Шень А., Может ли (индивидуальная) последовательность нулей и единиц быть случайной? *Успехи математических наук*, т. 45 (1990), вып. 1 (271), с. 105–162
Английский перевод: Uspenskii V. A., Semenov A. L., Shen’ A. Kh., Can an individual sequence of zeros and ones be random? *Russian Math. Surveys*, v. 45 (1990), no. 1, p. 121–189.

[168] Uspensky V. A., Shen A., Relations between varieties of Kolmogorov complexities, *Mathematical Systems Theory* (now *Theory of Computing Systems*), v. 29 (1996), no. 3, p. 271–292.

[169] Vereshchagin N. K. Kolmogorov complexity conditional to large integers. *Theoretical Computer Science*, v. 271 (2002), no. 1–2, p. 59–67.
Предварительная версия: ECCC TR01-086 (2001).
[170] Vereshchagin N., Kolmogorov complexity of enumerating finite sets, *Information Processing Letters*, v. 103 (2007), p. 34–39.
Предварительная версия: ECCC TR04-030 (2004).

[171] Vereshchagin N. K., Kolmogorov complexity and games, *Bulletin of the EATCS*. v. 94 (2008), p. 43–75.

[172] Vereshchagin N., Minimal sufficient statistic revisited, *Proc. 5th Conference on Computability in Europe* (CiE 2009), LNCS v. 5635, p. 478–487.

[173] Верещагин Н. К., Мучник Ан. А., О совместной условной сложности (энтропии), *Труды МИАН*, т. 274 (2011), с. 103–118.
Английский перевод: Vereshchagin N. K. and Muchnik An. A, On joint conditional complexity (Entropy), *Proc. of the Steklov Institute of Mathematics*, v. 274 (2011), p. 90-104.

Предварительные версии: Muchnik An. A. and Vereshchagin N. K., Logical operations and Kolmogorov complexity. II. *Proc. 16th IEEE Conference on Computational Complexity* (CCC 2001), p. 256–265 и ECCC TR01-089 (2001).

[174] Верещагин Н. К., Шень А., Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления, 3-е изд., М.: МЦНМО, 2008, ftp://ftp.mccme.ru/users/shen/logic/firstord.

[175] Верещагин Н. К., Шень А., Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции, 3-е изд., М.: МЦНМО, 2008, ftp://ftp.mccme.ru/users/shen/logic/comput.

Английский перевод: Vereshchagin N. K. and Shen A., *Computable functions*, American Mathematical Society, Student mathematical library, vol. 19, 2003.

[176] Верещагин Н. К., Скворцов Д. П., Скворцова Е. 3., Чернов А. В., Варианты понятия реализуемости для пропозициональных формул, приводящие к логике слабого закона исключённого третьего, *Труды МИАН*, т. 242 (2003), с. 77–97.

Английский перевод: Chernov A., Skvortsov D., Skvortsova E., and Vereshchagin N., Variants of realizability for propositional formulas and the logic of the weak law of excluded middle. *Proc. of Steklov Institute of Mathematics*, v. 242 (2003), p. 67–85. Предварительная английская версия: *Proc. 16th Workshop on Computer Science Logic* (CSL 2002), LNCS v. 2471, p. 74–88.

[177] Vereshchagin N. K., and Vitányi P. M. B., Kolmogorov's structure functions with an application to the foundations of model selection, *IEEE Transactions on Information Theory*, v. 50 (2004), no. 12, p. 3265–3290.
Предварительная версия: *Proc. 43th IEEE Symp. on Foundations of Computer Science* (FOCS 2002), p. 751–760.

[178] Vereshchagin N. K., and Vitányi P. M. B., Rate distortion and denoising of individual data using Kolmogorov complexity, *IEEE Transactions on Information Theory*, v. 56 (2010), no. 7, p. 3438–3454, см. также arXiv:cs/0411014 (2004).
выложено в arXiv:cs/0411014 (2004).

[179] Vereshchagin N. and Vyugin M., *Independent minimum length programs to translate between given strings*, *Theoretical Computer Science*, v. 271 (2002), p. 131–143.
Предварительная версия: ECCC TR00-035 (2000).

[180] Ville J., *Étude critique de la notion de collectif*, Gauthier-Villars, 1939. (Monographies des probabilités. Calcul des probabilites et ses applications. Publiée sous la direction de M. Émile Borel. Fascicule III.)
[181] Вовк В. Г., Об одном критерии случайности, Доклады АН СССР, т. 294 (1987), № 6, с. 1298–1302.
Английский перевод: Vovk V.G., On a randomness criterion, *Soviet Mathematics Doklady*, v. 35 (1987), no. 3, p. 656–660. См. также: www.vovk.net/criterion.pdf

[182] Вовк В. Г., Закон повторного логарифма для случайных по Колмогорову, или хаотических, последовательностей. Теория вероятностей и её применения, т. 32 (1987), № 3, с. 456–468. Английский перевод: Vovk V.G., The law of the iterated logarithm for random Kolmogorov, or chaotic, sequences. *Theory of Probability and its Applications*, v. 32 (1987), no. 3, p. 413–425.

[183] Vovk V., V'yugin V.V., On the empirical validity of Bayesian method, *Journal of the Royal Statistical Society*, B, v. 55 (1993), p. 253–266.

[184] Вьюгин В. В., Алгоритмическая энтропия (сложность) конечных объектов и её применение к определению случайности и количества информации, Семиотика и информатика, вып. 16 (1981), с. 14–43, М: ВИНИТИ.
Английский перевод: V'yugin V. V., Algorithmic entropy (complexity) of finite objects and its application to defining randomness and amount of information. *Selecta Mathematica formerly Sovietica*, v. 13 (1994), no. 4, p. 357–389.

[185] V'yugin V.V., Ergodic theorems for individual random sequences, *Theoretical Computer Science*, v. 207 (1998), no. 2, p. 343–361.

[186] V'yugin V.V., Non-stochastic infinite and finite sequences, *Theoretical Computer Science*, v. 207 (1998), no. 2, p. 363–382.

[187] Wald A., Sur la notion de collectif dans le calcul des probabilités (On the notion of collective in probability theory), présentée par M. Émile Borel. *Comptes rendus*, v. 202, p. 180–183 (séance du 20 janvier 1936).

[188] Wald A., Die Wiederspruchsfreiheit des Kollektivbegriffes der Wahrscheinlichkeitsrechnung, *Ergebnisse eines matematischen Kolloquiums*, v. 8 (1937), p. 38–72. Перепечатано в: Menger K., *Ergebnisse eines Mathematischen Kolloquiums*, Springer: Wien, New York, 1998.

[189] Wall D. D., *Normal Numbers*. Ph. D thesis, University of California, Berkeley CA, 1949.

[190] Wigderson, A., Randomness extractors — applications and constructions. *Proc. 29th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)*, DOI 10.4230/LIPIcs.FSTTCS.2009.2340, drops.dagstuhl.de/opus/volltexte/2009/2340/.

[191] Yeung, R. W., *A First course in information theory*, Kluwer Academic / Plenum Publishers, 2002.

[192] Заславский И. Д., Цейтин Г. С., О сингулярных покрытиях и связанных с ними свойствах конструктивных функций, Труды МИАН, т. 67 (1962), с. 458–502.

[193] Zhang Z., Yeung R.W., A non-Shannon-type conditional information inequality, *IEEE Transactions on Information Theory*, v. 43 (1997), p. 1982–1986.

[194] Zhang Z., Yeung R.W., On characterization of entropy function via information inequalities, *IEEE Transactions on Information Theory*, v. 44 (1998), p. 1440–1450.

[195] Zimand M., Guest Column: Possibilities and Impossibilities in Kolmogorov complexity extraction. *SIGACT News*, December 2010.

[196] Звонкин А.К., Левин Л.А., Сложность конечных объектов и обоснование понятий информации и случайности с помощью теории алгоритмов. *Успехи математических наук*, т. 25 (1970), вып. 6 (156), с. 85–127.
Английский перевод: Zvonkin A K., Levin L. A., The complexity of finite objects and the
development of the concepts of information and randomness by means of the theory of
algorithms. *Russian Math. Surveys*, v. 25 (1970), no. 6, p. 83–124.

[197] Miller J.S., The *K*-Degrees, Low for *K* Degrees, and Weakly Low for *K* Sets. *Notre Dame Journal of Formal Logic*, v. 50, no. 4 (2009), p. 381–391.

[198] Bauwens B., *Plain and prefix complexity characterizations of 2-randomness: simple proofs*, arXiv:1310.5230 (2013).
Предметный указатель

1-случайная последовательность 179

2-случайная последовательность 179

α-вычислимая функция 228

α-мартингал 319

α-нулевое множество 195

α-перечислимое множество 228

Λ, пустое слово 10

F, пространство частичных функций 227

0' 38

Ω 20, 179, 180, 183, 195

πx 165

≤1 181

≤c 182

Ξ 10

a(x) 141

B(n) 32, 35

BB(n) 35

bin(n) 10

BP(n) 192

с-эквивалентность 391

C(x) 25

dE 87

dP 87

f₀-пространство в смысле Ершова 223, 227

H(ξ) 16, 244

H(x) 25

I(x:y) 55, 393

I(x:y:z) 61

K(x) 25

K(x || A) 230

KA(X) 141

KM(x) 150

КР-низкие множества 229

КР'(x) 97

КР(x) 96

КР(x|z) 120

КР<sup>A</sup>(x) 121

KR(x) 218

KS(x) 25

KS(x, y) 40

KS(x|y) 43

KS<sup>A</sup>(x) 121

KS≥ 32

I(x), длина слова x 10

m-сводимость 38

m(i) 95

m(x|z) 120

r-отделимое множество 38

ample excess, лемма 172

busy beaver, функция 35

IPC 448, 457

Kollektiv 21

MDL (minimal description length) 20, 476

PSPACE 417

абсолютно нормальное число 296

аддитивность 64

алгоритм вероятностный 88

алгоритмическая задача 444

— решение 444

алгоритмической сложностью 6

Алсведе – Кёрнера теорема 389

амплитуда 511

априорная вероятность 95, 113, 141

— дискретная 141, 179

— натурального числа 117

— непрерывная 141

— условная 120

априорная сложность 141, 150, 153, 169

априорный дефект случайности 202

арифметическое кодирование 167

Арсланова теорема 39

базисная функция 85

базисное неравенство 58, 251, 355, 378

безатомная мера 200
Безиковича расстояние 290

безостановочная стратегия 530

бернуллиева мера 20, 66, 78

Бертрана постулат 400

бесконечность множества простых чисел
262

беспрефиксная функция 97, 100

беспрефиксное вычисление 100

беспрефиксное кодирование 40

беспрефиксный код 239

блокирующее чтение 102

борелевские множества 63

Бореля – Кантелли лемма 68

бритва Оккама 19, 500

Бэра теорема 203

вероятностная мера 200

вероятностный алгоритм 88, 133

вероятностный метод 439

вероятность 511

— априорная 95

— буквы 240

— остановки 89

— по Мизесу 292

— события 64

— условная 246, 307

взаимная информация 56, 249, 393

Вилля пример 299, 301

Вольфа – Слепяна теорема 409, 418

всюду плотное множество 203

вход 407

входная лента 100

выделение общей информации 432

выход 407

вычислимая мера 72

вычислимая последовательность 52

вычислимая функция 10, 517

вычислимое отображение 24, 106, 218, 227

вычислимое число 72

вычислимый Marktингал 310

вычислимый ряд 182

генератор псевдослучайных битов 508

генерическая последовательность 83, 203

гёделева (главная) нумерация 227

Гиббса неравенство 241

гипотеза 484

— минимальная 497

границная пара 111

граф 398

— двудольный 398, 412

— отпечаток вершины 411

— паросочетание 416

— разрез 426

— случайный 412

— экспандер 411

группа 361, 383

двоичный отрезок 165

двудольный граф 398, 412

действие группы 361

декомпрессор 9, 24, 218

— оптимальный 11

дефект оптимальности 495

дефект полноты 182

дефект случайности 17, 84, 167, 207, 471

— априорный 202

— ограниченный в среднем 87, 171

— ограниченный по вероятности 87

— префиксный 472

дизъюнкция 445

дискретная априорная вероятность 179

дискретная полумера 93, 135

длина слова 513

домен Скотта 227

допустимое по Колмогорову правило
отбора 517

допустимое по Чёрчу правило отбора 517

допустимое правило отбора 516

достаточная статистика 434

Дуба теорема 307

задача алгоритмическая 444

— дизъюнкция 445

— импликация 445

— конъюнкция 445

— сложность 444

закон больших чисел для переменных
вероятностей 338

— усиленный 203, 340

закон Пирса 448

закон повторного логарифма 269, 301

запрещение 279

запрещённая последовательность 279

запрещённое слово 278

игра 51, 414, 417, 436, 493

извращённость слова 482
измеримое множество 64

импликация 445

— критическая 457

Инглетона неравенство 380, 404

интервал 63

интуиционистская логика 447

информация взаимная 56

— по Шеннону 249

инъективный код 239

Какутани теорема 333

канторово множество 196

канторовское пространство 63, 196, 289

Кёнига лемма 273

КНФ 279

код 239

— буквы 239

— инъективный 239

— однозначно декодируемый 239

— префиксный 239

— средняя длина 240

код Хаффмана 243

кодирование при двух условиях 421

кодовое слово 239

количество информации алгоритмический подход 349

— в х об у 16, 55

— в слове 13

— вероятностный подход 349

— комбинаторный подход 349

коллектив 21, 292, 347

Колмогорова неравенство 303

Колмогорова – Левина теорема 47, 49

Колмогорова – Соломонова теорема 24, 44

колмогоровская сложность 6, 10, 12

— монотонная 150

— пары слов 40, 59

— префиксная 97

— простая (обыкновенная) 24

— релятивизованная 228

— тройки слов 42, 59

— условная 43

комбинаторная интерпретация неравенств 366, 372

комбинаторное количество информации 353

компрессор 507

конечный автомат 265

конструктивный носитель меры 537

конъюнкция 445

коперечислимость 236

корректная программа 102, 147

корректная функция 71

Коши неравенство 288

кратчайшее описание 392

Крафта неравенство 241

Крафта – Макмиллана неравенство 244, 249

Крафта – Чейтина лемма 109

Крипке модель 457, 458

критерий случайности по Мартин-Лёфу 144, 167, 187

— в терминах предсказаний 184

— для обычной сложности 173

— Соловея 76, 83, 185

критерий случайности по Шнорру 83

критическая импликация 457

Кульбака – Лейблера расстояние 242

Кучеры – Гача теорема 214

Ламбальгена теорема 210

Левина лемма 271

Левина – Шнорра теорема 167

лемма ample excess 172

— Бореля – Кантелли 68

— Левина 271

— Ловаса 276

— — эффективное доказательство 282

— о шторах (Крафта – Чейтина) 109

Липшица свойство 26

липшицево отображение 289

Ловаса лемма 274

локальная лемма Ловаса 276

Макмиллана неравенство 244, 249

максимальная полумера 93

маргинальное распределение 213

марковская цепь 62, 251

мартингал 303, 308, 347

— выигрывающий на последовательности 305, 325

— вычислимый 198, 310, 312

— относительно распределения 306

— перечислимый снизу 310

— сильно выигрывающий на последовательности 305

— частичный 325

математическая статистика 470

математическое ожидание 256

матроид 380
машина Тьюринга 21, 99

— скорость переноса информации 262

— след 263

Медведева теорема 457

медленная сходимость в смысле Соловея 189

мера 64, 196

— безатомная 200

— бернуллиева 20, 66, 78, 88

— вычислимая 72, 138

— Лебега 64

— перечислимая снизу 141

— равномерная 65

мера извращённости 482

Миллера – Ю теорема 176

минимальная гипотеза 497

минимальная достаточная статистика 433, 434

МЛ-случайность 75

множество r-отделимое 38

— α-нулевое 195

— с-однородное 362

— беспрефиксное 115

— борелевское 63

— всюду плотное 203

— измеримое 64

— канторово 63

— наследственное вверх 395

— низкое 205

— нулевое 64, 294

— однородное 355, 356

— открытое 63, 104

— пар корректное 223

— перечислимое 26, 91, 521

— полное по Тьюрингу 38

— полной меры 179

— почти однородное 362, 364

— простое 31, 136

— разрешимое 31

— униформное 223

— эффективно α-нулевое 196

— эффективно нулевое 69, 70, 168

— эффективно нулевое по Шнорру 82

— эффективно открытое 83, 203

множество меры нуль 21

модель Крипке 457

монотонная машина 147

монотонная сложность 18, 150, 152

Муавра – Лапласа теорема 259

Мучника теорема 409

— комбинаторный смысл 414

надграфик функции 28

наибольшая полумера 93

— на дереве 140

наследственное вверх множество 395

начало 513

не хуже, сравнение способов описания 11, 24

неблокирующее чтение 102

невычислимость сложности 18

независимизация 388

независимость слов 59, 62

— случайных величин 248

— условная 62, 383, 384, 404

неотделимые множества 38

непредсказуемая последовательность 526, 530, 537, 542

непредсказуемость 514

непрерывная полумера 135

непрерывное отображение 218

— Σ → Σ 146

непрерывность меры 64

неравенства для сложности 349

неравенство Азумы – Хёфдинга 338, 341

— базисное 251, 355, 378

— Гиббса 241

— Инглетона 380, 404

— Колмогорова 303

— Коши 288

— Крафта 241

— Крафта – Макмиллана 244, 249

— нешенноновское 385

— Фано 252

— Чебышёва 117, 493

несжимаемое слово 17, 54, 391

нестохастическое слово 473

нешенноновское неравенство 385

нижние оценки сложности 18

низкое множество 205

нормальная последовательность 296

нормальное число 296

нулевое множество 21, 64, 294

нумерация 227

— вычислимая 227

— гёделева (главная) 227

— оптимальная 228
общёënная подпоследовательность 517

образ меры 206

общая информация 391, 393, 432

— в трёх словах 61

— комбинаторный смысл 398

— релятивизованная 121

объём трёхмерного тела 288

объём шара 514

объяснение слова 471

ограниченный в среднем тест 86

ограниченный класс гипотез 484

ограниченный по вероятности тест
случайности 86

однородное множество 355, 356

— построение 359

описание 24, 43, 519

— кратчайшее 392

— самоограниченное 95

оптимальная нумерация 228

оптимальный префиксный код 243

оптимальный способ описания 11, 24, 97,
149, 226

— беспефиксный 193

— префиксно корректный 120

оптимальный способ условного описания 44

оптимальный язык описания 520

оракул 38, 39, 228

— 0' 229

— невычислимый 204

орбита точки 361

открытое подмножество 63

отношение перечислимое 419

отношение эквивалентности 391

отображение вычислимое 24, 106, 147, 218,
227

— липшицево 289

— непрерывное 105, 218

— непрерывное Σ → Σ 146

— подграфик 146

— покрытие 440

отпечаток 411, 422

парадокс Берри 18

— кучи 513

паросочетание 416

— в режиме on-line 417

передача информации при известном слове
409

перечень 480

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

перечислимая снизу полумера 92

перечислимая снизу последовательность 90

перечислимая снизу функция на
последовательностях 85

перечислимое множество 26, 91, 521

перечислимое семейство множеств 26

перечислимое снизу число 81, 89, 180

перечислимость снизу 89, 90

перечислимый снизу мартингал 310

перечислимый снизу ряд 93

Пирса закон 448

побитовая сумма 428

подграфик отображения 146

покрытие отображения 440

поле 429

полное по Соловье число 182

полнота по Тьюрингу 38

полумартингал 311

полумера 107, 122, 311

— дискретная 93, 135

— максимальная (наибольшая) 93

— на дереве 134

— непрерывная 134, 135

— перечислимая снизу 92

— простая 136

— универсальная 93, 141

— — на дереве 140

последовательность 1-случайная 179

— 2-случайная 179

— генерическая 83, 203

— запрещённая 279

— непредсказуемая 347, 526, 530

— нормальная 296

— перечислимая снизу 90

— правильная 202

— сбалансированная 293

— скорость сходимости 181

— случайная 77, 513

— случайная относительно вычислимых
мартингалов 312, 318, 348

— случайная относительно частичных
вычислимых мартингалов 325, 348

— случайная по Курцу 83, 318, 348

— случайная по Мартин-Лёфу 75, 257,
302, 347, 475, 525

— — критерий 145
— случайная по Мизесу – Колмогорову – Лавлэнду 326, 332, 342, 345, 347, 348

— случайная по Мизесу – Чёрчу 296, 297, 302, 317, 348

— случайная по Мизесу – Чёрчу – Дэли 321, 332, 341, 348

— случайная по Шнорру 82, 297, 315, 317

— типическая (типичная) 75

— характеристическая 80

постулат Бертрана 400

поток информации через разрез 426

почти однородное множество 362, 364

правило выбора 293, 321

— допустимое по Колмогорову – Лавлэнду 326

— допустимое по Чёрчу 295

— допустимое по Чёрчу – Дэли 321

правильная последовательность 202

предсказание 184

префиксная сложность 97, 169

— пары слов 123

— тройки слов 124, 127

префиксно корректная функция 95

префиксный дефект случайности 472

префиксный код 239

пример Вилля 299, 301

принцип Курно 503, 505

принцип сравнения MDL 476

проблема остановки 34, 38

программа корректная 102, 147

продолжение меры 64

пропозициональная формула 447

пропускная способность 407

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

простая полумера 136

простое множество 31, 136

простое семейство множеств 136

простое слово 31

пространство частичных функций 227

протокол 267

профиль пары слов 435

псевдодизъюнкция 446

псевдослучайные биты, генератор 508

псевдослучайный генератор 418

пустое слово 10, 513

равномерная мера 65

равномерное распределение вероятностей 514

равномерные тесты случайности 77

разделение секрета 428

размерность Хаусдорфа 195, 196

разрез 426

разрешимое множество 31

распределение маргинальное 213

распределение Бернулли 531

распределение вероятностей 531

— вычислимое 531

расстояние Безиковича 290

расстояние Кульбака – Лейблера 242, 309

расстояние между последовательностями 63

расстояние Хемминга 486

регулятор сходимости 32, 192

релятивизация 57, 120, 228, 251

— неравенств 250

ряд медленно сходящийся 192

самоограниченная запись 12

самоограниченное описание 95

самоограниченный вход 99

сбалансированная последовательность 293

сводимость по Соловье 182

сводимость по Тьюрингу 38

свойство Липшица 26

свойство устойчивости частот 292

семейство множеств перечислимое 26

— простое 136

сечение множества 48

сигма-алгебра 63

симметрия информации 56

синглетон 198

следов метод 263

слепая (безоракульная) случайность 77

слово с-эквивалентность 391

— двоичное 513

— запрещённое 278

— кодовое 239

— несжимаемое 17, 38, 391

— пустое 513

— случайное 17

— стохастическое 473

сложная подпоследовательность 281

сложностной вектор 364, 373

сложность 223

— аксиоматическое определение 29

— априорная 141, 150
— больших чисел 32

— задачи 444

— колмогоровская 10, 12

— комбинаторная интерпретация 366

— конструктивного объекта 25

— литературных текстов 166

— монотонная 18, 150, 152, 255

— условная 226

— натуральных чисел 25

— относительно способа описания 24

— относительно языка описания 519

— пары слов 40, 59, 355, 393

— префиксная 99, 123

— префиксная 97, 106, 112

— пары слов 113

— релятивизованная 112

— тройки слов 124, 127

— условная 119, 226

— простая 24

— разрешения 218

— последовательности 220

— условная 226

— релятивизованная 228

— с оракулом 37, 229, 402

— тотальная 45, 416, 482

— тройки слов 42, 59, 355

— условная 16, 43, 225, 445

— относительно множества 230

— функции 227

случайная величина критерий независимости 248

— математическое ожидание 256

— условная независимость 383, 384

— энтропия 244

случайная последовательность 69, 292, 513

случайная точка 81

случайное действительное число 81

случайное слово 17, 119

случайность действительного числа 180

— дефект 17, 84

— относительно вычислимых мартингалов 318, 348

— относительно образа меры 206

— относительно частичных вычислимых мартингалов 348

— по Курцу 83, 318, 348

— по Мартин-Лёфу 75, 257, 347, 525

— по Мизесу – Колмогорову – Лавлэнду 326, 347, 348

— по Мизесу – Чёрчу 317, 348

— по Мизесу – Чёрчу – Дэли 321, 341, 348

— по Шнорру 82, 315, 317

— слепая (безоракульная) 77

случайный граф 412

смежный класс 361

согласованные слова 523

Соломонова – Колмогорова теорема 11

способ описания 9, 24, 149, 218, 223

— беспрефиксный 106, 114

— оптимальный 24, 149, 220, 226

— оптимальный в классе префиксно корректных 97

— префиксно корректный 106, 151

— условный 43

— функции 227

сравнимость слов 223

средняя длина кода 240

стабилизатор точки 361

стохастическая по Колмогорову последовательность 516, 518, 523, 530, 534, 536

стохастическая по Чёрчу последовательность 516

стохастическая последовательность 515, 533

стохастическое слово 473

стратегия 529

— безостановочная 530

— выигрывающая на последовательности 530

стратификация 480

супермартингал 311

суффиксный код 240

тавтология 448

теорема Алсведе – Кёрнера 389

— Арсланова 39

— Бэра 203

— Вольфа – Слепяна 418

— Гача – Дея 225

— Гёделя о неполноте 22

— Дуба 307

— Какутани 333

— Ламбальгена 210

— Левина – Шнорра 5, 21, 165, 167, 197

— в форме Чейтина 169

— Мартин-Лёфа 73, 533, 537

— Медведева 457
— Ромашенко 350, 364, 365

— Соломонова – Колмогорова 11

— Форда – Фалкерсона 420, 428

— Холла 420

— Чена – Янга 360, 362

— Шеннона о кодировании 259

— Шеннона об идеальном шифре 253

тест случайности ограниченный в среднем
86

— ограниченный по вероятности 86

— по Мартин-Лёфу 84

типизация 364, 365, 371

типическая последовательность 75, 524,
525

типичность 514

типичный представитель 471

тотальная условная сложность 45, 416, 482

транзитивность 290

тьюрингова степень 201

универсальная полумера 93, 141

универсальное перечислимое неразрешимое
множество 229

универсальный вероятностный алгоритм
вероятность остановки 179

униформное множество 223

усилен тревоги 273

усиленный закон больших чисел 21, 66, 78,
83, 268, 308, 340

условие 43

условная вероятность 246, 307

условная независимость 62, 251, 383, 384,
404

условная сложность 16, 225

— относительно множества 230

— префиксная 119

условная энтропия 246

устойчивость частот 292, 514

Форда – Фалкерсона теорема 420, 428

формула пропозициональная 447

формула Стирлинга 254

фрактал 195

функция α-вычислимая 228

— базисная 85

— беспрефиксная 97, 100

— беспрефиксно вычислимая 100

— вычислимая 10, 24, 517

— на множестве двоичных слов
перечислимая снизу 134

— перечислимая сверху 28

— перечислимая снизу 85, 310

— префиксно корректная 95

— относительно первого аргумента 119

— Соловея 189, 190, 192

— хеш 410

хаотическая последовательность 521, 523,
536, 541

хаотичность 514

характеристическая последовательность 80,
203

характеристическая функция множества 229

хаусдорфова размерность 196, 318

— последовательности 290

— эффективная 198, 321

Хаффмана код 243

хеш-функция 410

Холла теорема 420

частичный мартингал 325

частота 21, 236, 514

— нижняя 236

частота буквы 240

частотоустойчивость 514

Чебышёва неравенство 117, 493

чёрный ящик 470

число абсолютно нормальное 296

— нормальное по основанию b 296

— перечислимое снизу 89, 180

— полное по Соловею 182

число Ω 179, 180, 183, 195, 499

— как число мудрости 195

шар 514

шар Хемминга 486

— мощность 487

шенноновская энтропия 16, 67, 239, 240,
244, 350

эквивалентность по Тьюрингу 195, 201

эквивалентность с точностью с 391

экспандер 411, 422

экстрактор 418

экстрактор случайности 140

энтропия 6, 350

— пары 113, 244
— пары случайных величин 245

— условная 244, 246

— Шеннона 239, 240, 244, 253, 254

— шенноновская 16, 67

энтропия алгоритмическая 520

энтропия монотонная (алгоритмическая) 523

энтропия префиксная (алгоритмическая) 542

эффективная хаусдорфова размерность 198

эффективно α-нулевое множество 196

эффективно нулевое множество 69, 70, 168

эффективно нулевое по Шнорру множество 82

эффективно открытое множество 83, 203

язык описания 519

язык, распознаваемый автоматом 265

языковое семейство 520
## Указатель имён

Азума К. (Kazuoki Azuma) 338, 341

Алсведе Р. (Rudolf F. Ahlswede) 389, 390, 427

Андреев Михаил 7

Арзуманян Виталий 7

Арсланов Марат Мирзаевич 39

Асарин Евгений Александрович 7

Бауэнс Б. (Bruno Bauwens) 8, 51, 130

Безикович Абрам Самойлович (Abram Samoilovich Besicovitch) 290

Беннет Ч. (Charles H. Bennett) 419

Бернулли Якоб (Jacob Bernoulli) 531

Берри Г. (G.G. Berry) 18

Бертран Ж. (Joseph Louis François Bertrand) 504

Бехер В. (Verónica Becher) 297

Блюм М. (Manuel Blum) 508

Борель Э. (Félix Édouard Justin Émile Borel) 68, 83, 503, 504

Бьенвеню Л. (Laurent Bienvenu) 8, 87, 179, 187, 189, 204, 213, 232, 235, 290, 317

Бэр Р. (René-Louis Baire) 203

Бюрман Г. (Harry Buhrman) 8, 418

Вальд А. (Abraham Wald) 294, 299

Ванг Й. (Yongge Wang) 180

Вигдерсон А. (Avi Wigderson) 140

Виль Ж. (Jean-André Ville) 299, 301, 303, 305, 347, 542

Витаньи П. (Paul Michael Bela Vitanyi) 4, 8, 265, 419

Вовк Владимир 7, 269, 310, 333

Вольф Дж. (Wolf Jack K.) 409, 418

Воробьёв Сергей 8

Выюгин Владимир Вячеславович 7, 205, 541, 542

Выюгин Михаил Владимирович 7, 433

Вялый Михаил Николаевич 7

Гач П. (Péter Gács) 8, 51, 77, 87, 152, 172, 177, 205, 213, 214, 225, 419

Гёдель К. (Kurt Gödel) 22

Гиббс Дж. (Josiah Willard Gibbs) 241

Голдрайх О. (Oded Goldreich) 508

Дей А. (Adam Day) 152, 225

Дектярёв Михаил Владимирович 7

Доуни Р. (Rod Downey) 5, 39, 189, 205, 229

Дуб Дж. (Joseph Leo Doob) 307

Дэли Р. (Robert P. Daley) 321, 327, 328, 332, 341, 345, 347, 348

Дюран Б. (Bruno Durand) 8, 271

Ершов Юрий Леонидович 223, 227

Жанг Ж. (Zhen Zhang) 385

Жордан К. (Marie Ennemond Camill Jordan) 83

Заславский Игорь Дмитриевич 76

Звонкин Александр Калманович 7, 201–203

Зиманд М. (Marius Zimand) 140

Инглетон О. (Aubrey William Ingleton) 380, 404

Какутани С. (Shizuo Kakutani) 333

Калинина Елена 7, 51, 234

Калюде К. (Cristian Sorin Calude) 5, 8, 180

Кантелли Ф. (Francesco Paolo Cantelli) 68, 83

Кантор Г. (Georg Ferdinand Ludwig Philipp Cantor) 196

Карпович Павел 7, 224

Кеплер И. (Johannes Kepler) 19

Кёниг Ю. (Julius König) 273

Кёрнер Я. (János Körner) 389, 390

Клини С. К. (Stephen Cole Kleene) 447

Колмогоров Андрей Николаевич 4, 7, 11, 24, 47, 166, 227, 303, 325–328, 332, 342, 345, 347, 348, 447, 514–516, 518, 520, 534, 540, 541
Коуцки М. (Michal Koucký) 8

Коши О. (Augustin-Louis Cauchy) 288

Крафт Л. (Leon G. Kraft) 241, 244

Крелинг Т. (Thorsten Kräling) 189

Крипке С. (Saul Aaron Kripke) 457, 458

Куиперс Л. (Lauwerens Kuipers) 297

Кульбак С. (Solomon Kullback) 242

Кумок Аким 7

Курно А. (Antoine Augustin Cournot) 503, 505, 511

Курц С. (Stewart A. Kurtz) 83, 301, 348

Кучера А. (Antonín Kučera) 180, 187, 188, 205, 213, 214

Кьёс-Хансен Б. (Bjørgn Kjos-Hanssen) 77

Кэй Н. (Ning Cai) 427

Лавлэнд Д. (Donald Loveland) 219, 299, 325–328, 332, 342, 345, 347, 348, 540

Ламбальген М. ван (Michiel van Lambalgen) 210, 332, 341, 541

Лаплант С. (Sophie Laplante) 418

Левин Леонид Анатольевич 4, 8, 18, 21, 47, 77, 87, 98, 130, 165, 167, 169, 171, 180, 183, 197, 201–203, 224, 271, 523, 533, 541

Лейблер Р. (Richard Leibler) 242

Лехтонен Ольга 7

Ли М. (Ming Li) 4, 265, 419

Литлвуд Дж. (John Edensor Littlewood) 270

Ли Ш. (Shuo-Yen Robert Li) 427

Ловас Л. (László Lovász) 274, 276

Лумис Л. (Lynn Harold Loomis) 253, 286

Лутц Дж. (Jack H. Lutz) 198

Майордомо Э. (Elvira Mayordomo) 198

Макарычев Константин Сергеевич 7, 274, 385

Макарычев Юрий Сергеевич 7, 385

Макмиллан Б. (Brockway McMillan) 244, 249

Манин Юрий Иванович 31

Маркарян Никита 509

Мартин-Лёф П. (Per Martin-Löf) 4, 18, 21, 69, 73, 75, 167, 177, 178, 180, 257, 302, 327, 332, 342, 345, 347, 525, 533, 537, 540, 541

Махлин Антон Юрьевич 7

Медведев Юрий Тихонович 457

Межиров Илья Владимирович 7

Меркле В. (Wolfgang Merkle) 8, 189, 315, 322, 326, 346, 347

Мизес Р. (Richard von Mises) 21, 292, 296, 297, 302, 321, 327, 328, 330, 332, 341, 342, 345, 347, 348, 505, 515, 534, 540, 543

Микэли С. (Silvio Micali) 508

Миллер Дж. (Joseph S. Miller) 8, 118, 119, 172, 176, 179, 273, 274

Минасян Александр 7

Мозер Р. (Robin A. Moser) 283

Мусатов Даниил Владимирович 7, 418

Мучнйк Альберт Абрамович 209

Мучнйк Андрей Альбертович 8, 118, 179, 232, 235, 238, 280, 328, 330, 393, 399, 409, 414, 421, 422, 433, 458, 542

Нидеррайтер Г. (Harald Niederreiter) 224, 297

Нис А. (Andre Nies) 5, 8, 39, 179, 205, 229

Окам (William of Ockam, также Occam) 19, 500

Пирс Ч. (Charles Sanders Peirce) 448

Подольский Владимир Владимирович 7

Портер К. (Christopher Porter) 213

Посицельский Семён Ефимович 7, 118

Пост Э. (Emil Leon Post) 31

Притыкин Юрий 7

Птолемей (Klaudios Ptolemaios) 19

Разенштейн Илья Петрович 7, 401, 402

Райман Я. (Jan Reimann) 8, 196

Раскин Михаил 7

Ромащенко Андрей Евгеньевич 7, 253, 350, 351, 364, 365, 384, 387, 403

Рохас К. (Cristobal Rojas) 87

Румянцев Андрей Юрьевич 7, 170, 272, 274, 279

Саблик М. (Mathieu Sablik) 290

Савин Арсений 7

Савчик Алексей Владимирович 7

Сальников Сергей 7

Семёнов Алексей Львович 7, 280, 542

Симпсон С. (Steve Simpson) 8

Сипсер М. (Michael Sipser) 8

Скотт Д. (Dana Scott) 227

Слепян Д. (David Slepian) 409, 418

Слэман Т. (Theodore A. Slaman) 180, 187, 188

Соловей Р. (Robert Martin Solovay) 76, 83, 119, 130, 131, 182, 188, 189, 192

Соломонов Р. (Ray Solomonoff) 4, 11, 24, 520, 540
Сопрунов Сергей Фёдорович 7

Тадаки К. (Kohtaro Tadaki) 196

Тарасов Сергей 7

Тардош Г. (Gábor Tardos) 283

Тервайн С. (Sebastiaan A. Terwijn) 179

Тьюринг А. М. (Alan Mathison Turing) 21, 99, 262, 297

Уитни Х. (Hassler Whitney) 253, 286

Устинов, Михаил 7

Ушаков Максим Александрович 7, 272

Фалкерсон Д. (Delbert Ray Fulkerson) 428

Фано Р. (Robert Mario Fano) 252

Фейгельман Марина Михайловна 7

Форд Л. (Lester Randolf Ford, Jr.) 428

Фортноу Л. (Lance Jeremy Fortnow) 283, 418

Харди Г. (Godfrey Harold Hardy) 270

Хаусдорф Ф. (Felix Hausdorff) 195, 196, 270

Хаффман Д. (David A. Huffman) 242, 243

Хемминг Р. (Richard Wesley Hamming) 486

Хертлинг П. (Peter Hertling) 180

Хёльцль Р. (Rupert Hölzl) 189

Хёфдинг В. (Wassily Hoeffding) 338, 341

Хинчин Александр Яковлевич 270

Хиршфельдт Д. (Dennis R. Hirschfeldt) 5, 8, 39, 205

Ходырев Александр 7, 197

Хойруп М. (Mathieu Hoyrup) 8, 87

Холл Ф. (Philipp Hall) 420

Хусаинов Бахадыр (Bakhadyr Khoussainov) 180

Цурек В. (Wojciech H. Zurek) 419

Чампернаун Д. (David Gawen Champernowne) 297

Чейтин Г. (Gregory Chaitin) 4, 22, 32, 98, 169, 179, 195, 542

Челноков Георгий Максимович 7

Чен Т. (Terence Chan) 360, 362

Чернов Алексей Вячеславович 7, 403, 457

Чёрч А. (Alonzo Church) 295–297, 302, 321, 327, 328, 330, 332, 341, 345, 347, 348, 516, 517, 540

Шейфер Г. (Glenn Shafer) 310

Шеннон К. (Claude Elwood Shannon) 6, 16, 239, 240, 244, 253, 259

Ширер Дж. (James B. Shearer) 253

Шмидт В. (Wolfgang M. Schmidt) 297

Шнорр К.-П. (Claus-Peter Schnorr) 4, 18, 21, 82, 83, 165, 167, 169, 171, 197, 227, 228, 297, 315, 523, 541

Штейнгауз Г. (Hugo Steinhaus) 270

Штефан Ф. (Frank Stephan) 179

Шувалов Виктор Валерьевич 7

Эйнштейн А. (Albert Einstein) 508

Ю Л. (Liang Yu) 172, 176

Янг Р. (Raymond W. Yeung) 360, 362, 385, 427

Яо А. (Andrew Chi-Chih Yao) 508
# Оглавление

Предисловие 4

О чём эта книга? 9

1. Простая колмогоровская сложность 24

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

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

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

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

2. Сложность пары и условная сложность 40

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

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

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

3. Случайность по Мартин-Лёфу 63

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

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

3.3. Эффективно нулевые множества 70

3.4. Свойства случайных последовательностей 78

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

4. Априорная вероятность и префиксная сложность 88

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

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

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

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

4.4.1. Беспрефиксные функции 100

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

4.4.3. Непрерывные вычислимые отображения 104

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

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

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

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

4.7.2. Свойства условной префиксной сложности 121
<table>
  <tbody>
    <tr>
      <td>4.7.3. Префиксная сложность пары</td>
      <td>123</td>
    </tr>
    <tr>
      <td>4.7.4. Обычная и префиксная сложности</td>
      <td>130</td>
    </tr>
    <tr>
      <td><b>5. Монотонная и априорная сложности и случайность</b></td>
      <td><b>133</b></td>
    </tr>
    <tr>
      <td>5.1. Вероятностные машины и полумеры на дереве</td>
      <td>133</td>
    </tr>
    <tr>
      <td>5.2. Наибольшая перечислимая полумера на дереве</td>
      <td>140</td>
    </tr>
    <tr>
      <td>5.3. Свойства априорной сложности</td>
      <td>141</td>
    </tr>
    <tr>
      <td>5.4. Вычислимые отображения Σ → Σ</td>
      <td>145</td>
    </tr>
    <tr>
      <td>5.4.1. Непрерывные отображения Σ → Σ</td>
      <td>146</td>
    </tr>
    <tr>
      <td>5.4.2. Монотонные машины с неблокирующим чтением</td>
      <td>147</td>
    </tr>
    <tr>
      <td>5.4.3. Перечислимость множества вычислимых отображений</td>
      <td>148</td>
    </tr>
    <tr>
      <td>5.5. Монотонная сложность</td>
      <td>149</td>
    </tr>
    <tr>
      <td>5.5.1. Доказательство теоремы Гача-Дея</td>
      <td>153</td>
    </tr>
    <tr>
      <td>5.6. Теорема Левина-Шнорра</td>
      <td>165</td>
    </tr>
    <tr>
      <td>5.7. Случайное число Ω</td>
      <td>179</td>
    </tr>
    <tr>
      <td>5.7.1. Сводимость и полнота по Соловею</td>
      <td>180</td>
    </tr>
    <tr>
      <td>5.7.2. Полные по Соловею числа случайны</td>
      <td>183</td>
    </tr>
    <tr>
      <td>5.7.3. Критерий случайности в терминах предсказаний</td>
      <td>184</td>
    </tr>
    <tr>
      <td>5.7.4. Случайные перечислимые снизу числа полны</td>
      <td>188</td>
    </tr>
    <tr>
      <td>5.7.5. Медленная сходимость и функции Соловея</td>
      <td>188</td>
    </tr>
    <tr>
      <td>5.7.6. Свойство Соловея для ряда определяется его суммой</td>
      <td>190</td>
    </tr>
    <tr>
      <td>5.7.7. Регуляторы сходимости и функция BB(n)</td>
      <td>192</td>
    </tr>
    <tr>
      <td>5.8. Эффективная размерность Хаусдорфа</td>
      <td>195</td>
    </tr>
    <tr>
      <td>5.9. Случайность по различным мерам</td>
      <td>200</td>
    </tr>
    <tr>
      <td>5.9.1. Переход от одной меры к другой</td>
      <td>200</td>
    </tr>
    <tr>
      <td>5.9.2. Последовательности, не случайные по вычислимым мерам</td>
      <td>201</td>
    </tr>
    <tr>
      <td>5.9.3. Случайность по образу меры</td>
      <td>205</td>
    </tr>
    <tr>
      <td>5.9.4. Теорема Ламбальгена</td>
      <td>210</td>
    </tr>
    <tr>
      <td>5.9.5. Теорема Кучеры-Гача</td>
      <td>213</td>
    </tr>
    <tr>
      <td><b>6. Общая классификация сложностей</b></td>
      <td><b>218</b></td>
    </tr>
    <tr>
      <td>6.1. Сложность разрешения</td>
      <td>218</td>
    </tr>
    <tr>
      <td>6.2. Сравнение сложностей</td>
      <td>222</td>
    </tr>
    <tr>
      <td>6.3. Условные сложности</td>
      <td>225</td>
    </tr>
    <tr>
      <td>6.4. Сложности и оракулы</td>
      <td>228</td>
    </tr>
    <tr>
      <td>6.4.1. Сложность с оракулом</td>
      <td>228</td>
    </tr>
    <tr>
      <td>6.4.2. Сложность при условии больших чисел</td>
      <td>230</td>
    </tr>
    <tr>
      <td>6.4.3. Пределы частот и априорная вероятность относительно 0'</td>
      <td>235</td>
    </tr>
    <tr>
      <td><b>7. Шенноновская энтропия и колмогоровская сложность</b></td>
      <td><b>239</b></td>
    </tr>
    <tr>
      <td>7.1. Шенноновская энтропия</td>
      <td>239</td>
    </tr>
    <tr>
      <td>7.1.1. Коды</td>
      <td>239</td>
    </tr>
    <tr>
      <td>7.1.2. Определение шенноновской энтропии</td>
      <td>240</td>
    </tr>
    <tr>
      <td>7.1.3. Код Хаффмана</td>
      <td>242</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>7.1.4. Неравенство Крафта – Макмиллана</td>
      <td>244</td>
    </tr>
    <tr>
      <td>7.2. Энтропия пары и условная энтропия</td>
      <td>244</td>
    </tr>
    <tr>
      <td>7.2.1. Энтропия пары случайных величин</td>
      <td>244</td>
    </tr>
    <tr>
      <td>7.2.2. Условная энтропия</td>
      <td>246</td>
    </tr>
    <tr>
      <td>7.2.3. Независимость и энтропия</td>
      <td>248</td>
    </tr>
    <tr>
      <td>7.2.4. «Релятивизация» и базисные неравенства</td>
      <td>250</td>
    </tr>
    <tr>
      <td>7.3. Сложность и энтропия</td>
      <td>253</td>
    </tr>
    <tr>
      <td>7.3.1. Колмогоровская сложность и энтропия частот</td>
      <td>254</td>
    </tr>
    <tr>
      <td>7.3.2. Математическое ожидание сложности</td>
      <td>256</td>
    </tr>
    <tr>
      <td>7.3.3. Сложность начальных отрезков случайных последовательностей</td>
      <td>257</td>
    </tr>
    <tr>
      <td>7.3.4. Вероятность отклонения сложности от энтропии</td>
      <td>258</td>
    </tr>
    <tr>
      <td>7.3.5. Теорема Шенна о кодировании</td>
      <td>259</td>
    </tr>
    <tr>
      <td><b>8. Некоторые приложения</b></td>
      <td><b>262</b></td>
    </tr>
    <tr>
      <td>8.1. Бесконечность множества простых чисел</td>
      <td>262</td>
    </tr>
    <tr>
      <td>8.2. Перенос информации по ленте</td>
      <td>262</td>
    </tr>
    <tr>
      <td>8.3. Конечные автоматы с несколькими головками</td>
      <td>265</td>
    </tr>
    <tr>
      <td>8.4. Усиленный закон больших чисел</td>
      <td>268</td>
    </tr>
    <tr>
      <td>8.5. Последовательности без запрещённых подслов</td>
      <td>271</td>
    </tr>
    <tr>
      <td>8.5.1. Запрещённые и простые слова</td>
      <td>271</td>
    </tr>
    <tr>
      <td>8.5.2. Лемма Ловаса</td>
      <td>274</td>
    </tr>
    <tr>
      <td>8.5.3. Лемма Ловаса и запрещённые слова</td>
      <td>278</td>
    </tr>
    <tr>
      <td>8.5.4. Запрещённые подпоследовательности</td>
      <td>279</td>
    </tr>
    <tr>
      <td>8.5.5. Сложные подпоследовательности</td>
      <td>281</td>
    </tr>
    <tr>
      <td>8.5.6. «Эффективное» доказательство леммы Ловаса</td>
      <td>282</td>
    </tr>
    <tr>
      <td>8.6. Доказательство одного неравенства</td>
      <td>286</td>
    </tr>
    <tr>
      <td>8.7. Нетранзитивность липшицевых преобразований</td>
      <td>289</td>
    </tr>
    <tr>
      <td><b>9. Частотный и игровой подходы к определению случайности</b></td>
      <td><b>292</b></td>
    </tr>
    <tr>
      <td>9.1. Исходный замысел фон Мизеса</td>
      <td>292</td>
    </tr>
    <tr>
      <td>9.2. Правила выбора как множества слов</td>
      <td>293</td>
    </tr>
    <tr>
      <td>9.3. Случайность по Мизесу – Чёрчу</td>
      <td>295</td>
    </tr>
    <tr>
      <td>9.4. Пример Вилля</td>
      <td>299</td>
    </tr>
    <tr>
      <td>9.5. Мартингалы</td>
      <td>302</td>
    </tr>
    <tr>
      <td>9.6. Отступление: мартингалы в теории вероятностей</td>
      <td>308</td>
    </tr>
    <tr>
      <td>9.7. Перечислимые мартингалы</td>
      <td>310</td>
    </tr>
    <tr>
      <td>9.8. Вычислимые мартингалы</td>
      <td>312</td>
    </tr>
    <tr>
      <td>9.9. Мартингалы и случайность по Шнорру</td>
      <td>315</td>
    </tr>
    <tr>
      <td>9.10. Мартингалы и эффективная размерность</td>
      <td>318</td>
    </tr>
    <tr>
      <td>9.11. Частичные правила выбора</td>
      <td>321</td>
    </tr>
    <tr>
      <td>9.12. Немонотонные правила выбора</td>
      <td>325</td>
    </tr>
    <tr>
      <td>9.13. Случайность по изменённой мере</td>
      <td>332</td>
    </tr>
    <tr>
      <td>9.13.1. Случайность по двум мерам</td>
      <td>332</td>
    </tr>
    <tr>
      <td>9.13.2. Закон больших чисел для переменных вероятностей</td>
      <td>338</td>
    </tr>
  </tbody>
</table>
<table><tr><td>9.13.3. Закон больших чисел для подпоследовательностей</td><td>340</td></tr><tr><td>9.13.4. Примеры</td><td>345</td></tr></table>

<table><tr><td>10. Неравенства для энтропии, сложности и размера</td><td>349</td></tr><tr><td>10.1. Постановка задачи и результаты</td><td>349</td></tr><tr><td>10.2. Однородные множества</td><td>355</td></tr><tr><td>10.3. Построение однородного множества</td><td>359</td></tr><tr><td>10.4. Однородные множества и орбиты</td><td>361</td></tr><tr><td>10.5. Почти однородные множества</td><td>362</td></tr><tr><td>10.6. Метод типизации</td><td>364</td></tr><tr><td>10.7. Комбинаторная интерпретация: примеры</td><td>366</td></tr><tr><td>10.8. Комбинаторная интерпретация: общий случай</td><td>369</td></tr><tr><td>10.9. Комбинаторная интерпретация: другой вариант</td><td>372</td></tr><tr><td>10.10. Неравенства для двух и трёх слов</td><td>375</td></tr><tr><td>10.11. Размерности и неравенство Инглетона</td><td>378</td></tr><tr><td>10.12. Условно независимые случайные величины</td><td>383</td></tr><tr><td>10.13. Неравенства, не сводящиеся к базисным</td><td>385</td></tr></table>

<table><tr><td>11. Общая информация</td><td>391</td></tr><tr><td>11.1. Представление слов в несжимаемом виде</td><td>391</td></tr><tr><td>11.2. Выделение общей информации</td><td>392</td></tr><tr><td>11.3. Комбинаторный смысл общей информации</td><td>398</td></tr><tr><td>11.4. Условная независимость и общая информация</td><td>403</td></tr></table>

<table><tr><td>12. Алгоритмическая теория информации для нескольких источников</td><td>407</td></tr><tr><td>12.1. Постановка задачи о передаче информации</td><td>407</td></tr><tr><td>12.2. Условное кодирование</td><td>409</td></tr><tr><td>12.3. Условное кодирование: теорема Мучника</td><td>409</td></tr><tr><td>12.4. Комбинаторный смысл теоремы Мучника</td><td>414</td></tr><tr><td>12.5. Отступление: on-line паросочетания</td><td>416</td></tr><tr><td>12.6. Относительное кодирование пары слов</td><td>418</td></tr><tr><td>12.7. Кодирование при двух условиях</td><td>421</td></tr><tr><td>12.8. Поток информации через разрез</td><td>426</td></tr><tr><td>12.9. Сети с одним источником</td><td>427</td></tr><tr><td>12.10. Выделение общей информации</td><td>432</td></tr><tr><td>12.11. Упрощение программы</td><td>432</td></tr><tr><td>12.12. Минимальная достаточная статистика</td><td>433</td></tr></table>

<table><tr><td>13. Информация и логика</td><td>444</td></tr><tr><td>13.1. Задачи, логические операции, сложность</td><td>444</td></tr><tr><td>13.2. Сложность задач и интуиционистская логика</td><td>446</td></tr><tr><td>13.3. Примеры</td><td>448</td></tr><tr><td>13.4. Примеры и доказательство теоремы о полноте</td><td>451</td></tr><tr><td>13.5. Теорема о полноте и модели Крипке</td><td>458</td></tr></table>
<table><tr><td>13.6. Задача, не сводящаяся к условным сложностям</td><td>462</td></tr><tr><td>14. Алгоритмическая статистика</td><td>470</td></tr><tr><td>14.1. Постановка задачи. Дефект случайности.</td><td>470</td></tr><tr><td>14.2. Стохастические объекты</td><td>473</td></tr><tr><td>14.3. Двухчастные описания</td><td>476</td></tr><tr><td>14.4. Ограниченные классы гипотез</td><td>484</td></tr><tr><td>14.5. Дефект оптимальности и дефект случайности</td><td>495</td></tr><tr><td>14.6. Минимальные гипотезы</td><td>497</td></tr><tr><td>14.7. Немного философии</td><td>500</td></tr><tr><td>Приложение 1. Колмогоровская сложность и основания теории вероятностей</td><td>502</td></tr><tr><td>Приложение 2. Четыре алгоритмических лица случайности</td><td>512</td></tr><tr><td>Используемые понятия и обозначения</td><td>544</td></tr><tr><td>Литература</td><td>548</td></tr><tr><td>Предметный указатель</td><td>562</td></tr></table>