Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dubna/2005/notes/uspensky.pdf Дата изменения: Thu Sep 8 12:27:47 2005 Дата индексирования: Sat Dec 22 14:12:00 2007 Кодировка: koi8-r Поисковые слова: http www.astronomy.ru forum index.php topic 4644.0.html

четыре алгоритмических лица случайности
В. А. Успенский
Дубна, 23 июля 2005 г.

ПРЕДИСЛОВИЕ
Если кто-либо скажет нам, что он подбросил честную монету двадцать раз и, о бозначив гер б единицей, а решётку нулём, получил такой результат: 10001011101111010000 или такой: (I)

01111011001101110001; ((II) мы вряд ли будем удивлены. Однако если нам скажут, что результат бросаний был таким: 00000000000000000000 ((III) или таким: 01010101010101010101 ((III) | мы будем поражены и воо бще не поверим или же усомнимся в корректности эксперимента. Возникает вопрос, почему. По-видимому, цепочки (I) и (II) воспринимаются как случайные, а цепочки (III) и (IV) | как неслучайные. Но что означают слова воспринимается как случайная? Классическая теория вероятностей не даёт ответа на этот важный вопрос. Не столь редко можно услышать следующее о бъяснение: вероятность каждой из цепочек (III) и (IV) слишком мала, она равна 2-20 , что меньше одной миллионной. Но ведь ровно такую же вероятность имеют цепочки (I) и (II). Три важных замечания. Во-первых, понимание случайности зависит от распределения вероятностей. Если одна сторона монеты тяжелее другой или если человек в процессе бросания научается подкидывать монету так, что бы она падала на нужную сторону, то появление цепочек (III) или (IV) может стать вполне ожидаемым. Для простоты мы будем заниматься лишь независимыми бросаниями с вероятностью одна вторая для гер ба и решки. Во-вторых, точной границы между случайными и неслучайными цепочками нет и не может быть. Ведь если в случайной цепочке заменить один знак, она должна остаться случайной. Но, заменяя много раз, мы от любой цепочки можем прийти к (III) или (IV). В-третьих, говорить о случайности имеет смысл лишь в применении к очень длинным цепочкам. Бессмысленно спрашивать, которая из цепочек 00, 01, 10, 11 более случайна, чем другие. Поэтому следует заниматься только очень длинными цепочками, а проще всего | бесконечными (т. е. последовательностями), что мы и будем делать. Воо бще, бесконечность | это такое полезное приближение сверху к очень большому конечному. 1


Оказывается, бесконечные последовательности уже можно довольно осмысленно разделить на случайные и неслучайные. Иными словами, можно пытаться найти строгое математическое определение для понятия `случайная последовательностей нулей и единиц'. Нам будут полезны некоторые термины и о бозначения. Множество всех бесконечных последовательностей нулей и единиц о бозначаем . Всякая конечная цепочка i1 ; : : : ; in нулей и единиц называется также двоичным словом, а число n | длиной этого слова. Длина слова может быть равна нулю; слово длины ноль ничего не содержит и называется пустым. Пустое слово о бозначается буквой . Множество всех двоичных слов о бозначается буквой . Длина слова x о бозначается так: |x |. Для последовательности a1 ; a2 ; a3 ; a4 ; : : : каждое из двоичных слов a1 ; a2 : : : ; an является её началом. Пусть x | двоичное слово. Множество всех тех последовательностей из , для которых x служит началом, о бозначим через x . Каждое множество вида x , где x , принято называть шаром. Шару x приписывается его объём v(x), равный 2-|x| . Содержательно, каждую последовательность из мы рассматриваем как серию результатов бросаний монеты. Ещё раз подчеркнём, что для наглядности мы ограничиваемся ситуацией, когда результаты всех бросаний равновероятны и независимы друг от друга. На математическом языке это означает, что на задано так называемое равномерное распределение вероятностей | а это, в свою очередь, означает следующее: для каждого шара вероятность того, что случайно выбранная последовательность из попадёт в этот шар, равна о бъёму этого шара. Наша цель | попытаться выделить из некоторое точно описанное подмножество, претендующее на роль множества всех случайных последовательностей. Традиционная теория вероятностей не только не приближается к решению этой задачи, но даже не может её сформулировать в своих терминах. На помощь приходит теория алгоритмов. Может показаться парадоксальным, что понятие случайности уточняется на основе такого чуждого случайности понятия, как алгоритм, | тем не менее дело о бстоит именно так: все известные до сих пор определения случайности индивидуального о бъекта (в нашем примере | индивидуальной последовательности нулей и единиц) опираются на понятие алгоритма. Что бы найти тре буемое определение, поступают так. Формулируют некое характеристическое свойство, которым о бладают случайные (в неформальном, интуитивном смысле) последовательности. А затем последовательности, о бладающие этим свойством, и о бъявляют | по определению | случайными. Какими же свойствами о бладает случайная последовательность нулей и единиц? Во-первых, она частотоустойчива. Вот что это означает для того простейшего случая, когда нули и единицы равновероятны | а только такой случай мы и будем рассматривать: частота нулей, как и частота единиц, стремится к одной второй. (Частота нулей | это их доля в начальном отрезке последовательности.) При этом указанная устойчивость частот выполняется не только для последовательности в целом, но и для любой её законной, разумной подпоследовательности. Во-вторых, она хаотична. Это означает, что она сложно устроена и не может иметь 2

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

3


Лицо Первое: ЧАСТОТОУСТОЙЧИВОСТЬ
По-видимому, первым поставил вопрос о том, что такое отдельно взятая случайная последовательность замечательный немецкий математик Рихард фон Мизес в начале XX века | в 1919 г.. Во всяком случае, он первым попытался на этот вопрос ответить. Мизес исходил из того, что случайной последовательности должна быть присуща устойчивость частот. А именно, доля единиц (как и доля нулей) в начальном отрезке случайной последовательности должна стремиться к одной второй при неограниченном увеличении длины начального отрезка. Но этого недостаточно. Например, этим свойством устойчивости частот о бладает заведомо неслучайная последовательность 0; 1; 0; 1; 0; 1; 0; 1; : : : : Очевидным о бразом нео бходимо, что бы устойчивостью частот о бладала не только вся последовательность целиком, но и её подпоследовательности. Однако устойчивостью частот не могут о бладать в c е подпоследовательности. В самом деле, возьмём самую что ни на есть случайную последовательность и отберём в подпоследовательность те её члены, которые равны нулю. . . Значит, подпоследовательность, в которой должна со блюдаться устойчивость частот, должна быть разумной, или допустимой. Сам Мизес о бъяснял, какие последовательности следует считать допустимыми, в расплывчатых терминах. Первое уточнение предложил в 1940 г. американский математик Алонзо Чёрч | один из создателей теории алгоритмов. Чёрч предложил, что бы допустимые подпоследовательности строилась на основе определённых алгоритмов. Последовательности, в которых устойчивость частот наблюдается во всех допустимых по Чёрчу подпоследовательностях, получили название стохастических по Чёрчу. Однако оказалось, что определение Чёрча слишком широко: существует стохастическая по Чёрчу последовательность, перестающая быть таковой после вычислимой перестановки её членов. В 1963 г. Колмогоров усовершенствовал конструкцию Чёрча, предложив более о бширный класс допустимых алгоритмов отбора членов исходной последовательности в подпоследовательность и тем самым более о бширный класс допустимых подпоследовательностей; в частности, колмогоровский алгоритм разрешает членам подпоследовательности иметь иной порядок следования, чем в исходной последовательности. Поэтому класс всех последовательностей, стохастических по Колмогорову (т. е. таких, у которых устойчивость частот наблюдается во всех допустимых по Колмогорову подпоследовательностях), является подклассом класса последовательностей, стохастических по Чёрчу | на самом деле даже строгим подклассом, т. е. не совпадающим с о бъемлющим классом. Но и этот подкласс оказался слишком широк: может быть, например, построена такая стохастическая по Колмогорову последовательность, в каждом начальном отрезке которой единиц больше, чем нулей; а это противоречит как интуиции, так и законам теории вероятностей (например, закону возвратности состояний при случайном блуждании). Для дальнейших ссылок класс всех последовательностей, стохастических по Колмогорову, о бозначим буквой S. Таким о бразом, наиболее продвинутое на сегодняшний день математически строгое уточнение идей Мизеса не даёт полного отражения интуитивного представления о случайности (хотя и это неполное отражение может оказаться полезным). 4


Для большей ясности приведём конструкции Чёрча и Колмогорова. Центральным для о беих конструкций является указание тех правил, согласно которым из членов рассматриваемой последовательности составляются допустимые подпоследовательности. Поскольку каждое такое правило производит отбор членов последовательности для включения их в допустимую подпоследовательность, сами эти правила принято называть допустимыми правилами отбора. Для наглядности представим се бе, что члены исследуемой последовательности написаны на картах. Карты лежат одна за другой, лицевой стороной вниз, так что мы не видим, что на них написано. Наша цель | ото брать некоторые из этих карт и составить из них другую последовательность | допустимую подпоследовательность. (Как мы увидим, в случае колмогоровской конструкции термин \подпоследовательность" имеет более широкий смысл, чем это о бычно принято.) Допустимое правило отбора представляет со бою алгоритм, который на каждом этапе построения подпоследовательности предписывает, во-первых, которую из карт надлежит открыть и, во-вторых, следует или нет включать эту уже открытую карту в подпоследовательность. Входом алгоритма служит информация о всех уже открытых к этому моменту картах. Может случиться, что алгоритм отберёт лишь конечное число членов исходной последовательности; в этом случае считается, что никакой допустимой подпоследовательности не о бразовалось. (Напомним, что исходная последовательность признаётся стохастической при наличии устойчивости частот в любой её допустимой подпоследовательности.) Переходим к более точному описанию. Функция называется вычислимой, коль скоро существует алгоритм, перерабатывающий каждый из её аргументов в соответствующее значение, | иными словами, вычисляющий её значение по заданному аргументу. Исследуемую на устойчивость последовательность о бозначим a1 a2 a3 : : :, так что на n-ой карте записана цифра an , равная 0 или 1. Допустимое по Чёрчу правило отбора состоит в предъявлении произвольной вычислимой функции G, определённой на множестве всех двоичных слов и принимающей одно из двух значений: Д а и Н ет. Карты открываются последовательно, одна за другой, начиная с первой, и каждый раз | до открытия очередной карты | решается вопрос, включать ли эту карту в подпоследовательность. Вопрос этот решается следующим о бразом. Пусть уже открыты n карт, на которых записаны, соответственно, цифры a1 ; : : : ; an . Если G(a1 : : : an ) есть Н ет, то следующая, (n + 1)-я карта не включается в подпоследовательность. Если G(a1 : : : an ) есть Д а, то следующая, (n + 1)-я карта включается в подпоследовательность в качестве очередного члена. Включать или не включать в подпоследовательность член a1 , зависит от значения G( ). Таким о бразом, правилу G отвечает бесконечная подпоследовательность (в случае, если таковая о бразовалась) an(1) an(2) an(3) : : :, где числа n(1), n(2), n(3), . . . о бразуют возрастающую последовательность, составленную из всех чисел n, для которых G(a1 : : : an-1 ) = Д а. Изложению конструкции Колмогорова предпошлём следующее о бо бщение понятия последовательности. Обобщённой подпоследовательностью последовательности a1 a2 : : : an : : : назовём всякую последовательность вида
a
(1) a(2)

::: a

(k)

:::;

5


для которой выполнено условие
i < j = (i) = (j ):

Для о бычной подпоследовательности (которая является частным случаем о бо бщённой) это условие заменено на более сильное | с правой частью (i) < (j ). Каждое допустимое по Колмогорову правило отбора о бразует некоторую о бо бщённую подпоследовательность исходной последовательности. (Для стохастичности по Колмогорову тре буется устойчивость частот в каждой из допустимых, то есть о бразованных каким-либо допустимым по Колмогорову правилом, о бо бщённых подпоследовательностей.) Само правило состоит в предъявлении двух вычислимых функций: F и G. Первая служит для о бразования некой вспомогательной о бо бщённой подпоследовательности. Окончательная же о бо бщённая подпоследовательность исходной последовательности строится при помощи функции G в качестве о бычной подпоследовательности вспомогательной о бо бщённой подпоследовательности. Аргументами функций F и G служат двоичные слова | но не о бязательно все слова, так что каждая из этих функций определена на своём подмножестве множества . Значениями функции F служат целые положительные числа, у функции G два возможных значения: Д а и Н ет. Сперва строится последовательность натуральных чисел n(1) n(2) n(3) : : ::
n(1) = F ( ); n(2) = F (a
n(1)

); : : : ; n(k + 1) = F (an

(1)

::: a

n(k)

):

Построение этой последовательности прекращается, как только наступает один из трёх случаев: значение F (an(1) : : : an(k) ) не определено; значение G(an(1) : : : an(k) ) не определено; значение F (an(1) : : : an(k) ) совпадает с одним из чисел n(1); : : : ; n(k). Если же остановки в построении не произошло и возникла бесконечная последовательность номеров n(1) n(2) n(3) : : :, то далее строится вспомогательная о бо бщённая подпоследовательность an(1) an(2) an(3) : : :. Из неё, наконец, отбираются | в порядке возрастания k | те её члены an(k) , для которых выполнено равенство G(an(1) : : : an(k-1) ) = Д а.

6


Лицо Второе: ХАОТИЧНОСТЬ
Вернёмся к примерам конечных цепочек из Предисловия и вспомним о бъяснение, предложенное Колмогоровым: цепочки (I) и (II) воспринимаются как случайные, потому что они сложны; цепочки (III) и (IV) воспринимаются как неслучайные, потому что они просты. По-видимому, мы ожидаем, что результат случайного эксперимента окажется сложным и удивляемся, когда получаем что-то простое. Некоторые о бъекты можно квалифицировать как большие или маленькие, другие | как тяжёлые или лёгкие, третьи | как сложные или простые. В начале 60-х годов Колмогоров наметил математическую теорию, позволяющую оценивать сложность о бъектов. Сейчас эта теория называется теорией колмогоровской сложности В основе теории колмогоровской сложности лежит следующая простая и естественная идея: В самом деле, каждый о бъект может иметь сколь угодно сложные описания, но сложный о бъект невозможно описать коротко. Пусть Y | множество всех о бъектов, которые мы рассматриваем, а X | множество всех мыслимых описаний этих о бъектов. Через |x| о бозначим длину описания x. Сложность о бъекта y о бозначим Comp(y). В соответствии со сказанным, Comp(y) = min {|x| : x есть описание для y}: x Если о бъект y неописуем, т. е. для него не существует описания, то, естественно, его сложность равна бесконечности. Разумеется, длины надо мерить единоо бразным спосо бом, что бы не получилось, что описание одного и того же о бъекта имеет на китайском языке длину единица (один иероглиф), а на русском | сорок (сорок букв). Поэтому все описания кодируются в двоичном алфавите | в виде двоичных цепочек. Вот эти-то двоичные коды мы и будем отныне считать описаниями, так что отныне X = . Множество всех таких пар x; y , что x служит описанием для y, естественно называть языком. Заметим, что и один и тот же о бъект может иметь в данном языке много описаний, и одно и то же описание может служить описанием многих о бъектов (таково, например, описание: двоичное слово, состоящее только из нулей). Всё сказанное носило предварительный характер, что бы оправдать нижеследующее формальное изложение. В декартовом произведении в Y рассматриваем произвольное подмножество E , которое называем языком. Если x; y E , будем говорить, что x является описанием о бъекта y. Сложность CompE о бъекта y относительно языка E определяется так: CompE (y) = min {|x| : x; y}: x Напоним, что минимум по пустому множеству принято считать равным бесконечности. Для языке E = в Y , в котором каждое x служит описанием для каждого y, сложность любого о бъекта y равна нулю, поскольку одним из описаний этого y является 7

сложность о бъекта измеряется длиной его кратчайшего описания.


пустое слово; такой язык мыслим, но не будет встречаться в тех семействах языков, которые мы будем рассматривать. Представим се бе два языка, причём описание какого-либо о бъекта на втором языке происходит путём удвоения описания этого же о бъекта на первом языке. Ясно, что второй язык хуже первого. Предпочтительнее те языки, которые в состоянии давать более короткие описания. Будем говорить, что язык A не хуже языка B и писать A B , если существует такая константа c, что для всякого y справедливо неравенство CompA (y) < CompB (y) + c | короче, если c y CompA (y ) < CompB (y ) + c: Если принять, что для так называемых естественных языков, то есть для тех, которыми пользуется человечество, могут быть сформулированы правила перевода с одного языка на другой, то становится очевидным, что каждый из этих языков не хуже другого. Ведь, скажем, турецкое описание какого-либо о бъекта можно составить так: взять японское описание этого о бъекта и дополнить его правилами японо-турецкого перевода. И турецкое, и японское описания, и правила перевода считаются закодированными в виде двоичных слов. Поэтому длина турецкого описания равна длине японского описания плюс не зависящая от выбора о бъекта длина правил перевода. В итоге получаем, что турецкий язык не хуже японского. Встаёт вопрос о выборе оптимального языка | такого, который не хуже любого другого. Пусть L | некоторое языков семейство, т. е. попросту некоторое множество ое языков. Язык A из этого семейства L называется оптимальным (для L), если он не хуже любого другого языка из этого семейства, т. е. если


B L A B:

Если оптимальный язык существует, то именно с его помощью следует измерять сложность. Сложность о бъекта относительно оптимального языка называется энтропией этого о бъекта. Энтропию и рассматривают как окончательную искомую меру сложности | в рамках заданного языков о семейства. ог Для некоторых важных языковых семейств имеет место теорема о существовании оптимального языка, а тем самым и энтропии. Эта теорема называется Теоремой Соломонова { Колмогорова. Для данного семейства может существовать (и, как правило, существует) много оптимальных языков а, следовательно, много энтропий. Однако, в силу определения оптимальности, любын две энтропии (взятые для одного и того же фиксированного языков о семейства) различаются не более чем на аддитивную константу. Иными слоог вами, если A и B суть два оптимальных для L языка, то существует такая константа c, что |CompA (y ) - CompB (y )| < c: З а м е ч а н и е . Конечно, неприятно, что энтропия, претендующая на роль истинной сложности определяется не однозначно, а всего лишь с точностью до аддитивной до бавки, не превышающей константы. Однако попытки найти среди энтропий наиболее оптимальную пока что ни к чему хорошему не привели. С другой стороны, 8


ведь, скажем, и длина, и вес также определены неоднозначно, а с точностью до мульипликативной константы, зависящей от выбранной единицы измерения (10 см и 100 мм; 2 кг и 2000 г). Из уважения к Колмогорову энтропию о бозначают о бычно буквой K; иногда к этой букве K до бавляют ещё вторую букву, указывающую то языков семейство, к которому ое относится рассматривая энтропия. Если K и K суть две энтропии, относящие к одному и тому же языков семейству, то, как отмечалось, ому
|

K - K | < c:

Колмогоров не только сформулировал понятие энтропии о бъекта, но и приложил его к исследованию случайных последовательностей. Наблюдение Колмогорова состояло в том, что в случайной последовательности энтропия начального отрезка растёт достаточно быстро при неограниченном увеличении длины этого отрезка. (Ничего не поделаешь, случайная последовательность может начинаться с миллиона нулей | но и этот миллион ничто перед бесконечностью, и если взять все начальные отрезки в совокупности, то их энтропия неизбежно будет расти.) Итак, в качестве описываемых о бъектов мы будем рассматривать двоичные цепочки | такие, как (I), (II), (III), (IV) и т. п. Поэтому отныне Y = . Если язык содержит пару z ; z , то это означает попросту что цепочка z описывает самоё се бя. Язык D, состоящий в точности из пар такого вида, называется диагональным (термин из математики), или автонимным (термин из лингвистики). Для такого языка CompD (y) = |y|. Ограничимся языковыми семействами, содержащими автоним ный язык (таким будет, в частности, семейство монотонных языков, описанное ниже). Тогда для каждой энтропии K, соответствующей этому семейству, и подходящей константы с будет выполнено неравенство: K(y) < |y| + c: Таким о бразом, если прене бречь аддитивной константой, максимально возможное значение для энтропии цепочки равно длине цепочки. Колмогоров предположил, что у случайной последовательности энтропия начального отрезка достигает этого максимума, т. е. равна длине этого отрезка, | опять-таки, при прене брежении аддитивной константой. В этом состояла основная идея Колмогорова относительно хаотичности. Итак, фиксируем некоторое языков семейство и одну из соответствующих этому ое семейству энтропий K. Назовём последовательность
a1 ; a2 ; : : : ; an ; : : :

хаотической, если существует такая константа c, что
K(a1 ; a2 ; : : : ; an ) > n - c: Очевидно, свойство хаотичности не зависит от выбранной энтропии, а только от выбранного семейства. Оказалось, что при подходяще выбранном языковом семействе строгое понятие хаотичности хорошо отражает интуитивное представление о случайности. 9


Создавая теорию сложности о бъектов, Колмогоров придал соотношению `описание { о бъект' алгоритмический характер. Следуя Колмогорову, ограничимся перечислимыми языками. Понятие перечислимого множества | это одно из основных понятий теории алгоритмов (да и математики в целом). Этому понятию можно дать такое наглядное о бъяснение. Представим се бе безостановочно работающий принтер, последовательно печатающий слова. Перед напечатанием очередного слова принтер берёт время на размышление. Это время может оказаться бесконечным, и тогда слово не печатается вовсе; в таком случае напечатанным будет лишь конечное множество слов | в частности, пустое множество, если принтер в самом начале своей работы задумался навсегда. Так вот, множество всех когда-либо напечатанных таким принтером слов окажется перечислимым | и всякое перечислимое множество может быть получено таким о бразом при подсоединении принтера к идеальному компьютеру. Перечислимо и множество теорем любой формальной теории. Здесь нет места разъяснять, ни что такое идеальный компьютер, ни что такое формальная теория. Но определение понятия `перечислимое множество' мы сейчас приведём. Для наглядности начнём с термина \счётное множество". Термин этот имеет два варианта значения. В первом, более узком (и более распространённом) значении счётное множество | это такое множество, которое можно поставить во взаимно однозначное соответствие с натуральным рядом. Во втором, более широком значении счётное множество | это такое множество, которое можно поставить во взаимно однозначное соответствие с каким-либо начальным отрезком натурального ряда. Напомним, что начальным отрезком натурального ряда называется произвольное множество M натуральных чисел, содержащее вместе со всяким своим элементом и все меньшие числа. Таким о бразом, и весь натуральный ряд, и пустое множество являются начальными отрезками. Поэтому при втором понимании счётности все конечные множества, в том числе пустое множество, оказываются счётными. Именно это второе, более широкое понимание счётности удо бно для наших целей; его мы и примем. А тогда счётному множеству можно дать и такое определение: множество называется счётным, ес-

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

конечное множество a; b; c можно расположить в последовательность a; b; c; c; c; c; : : :. Заменяя в приведённом определении счётного множества термин \последовательность" на термин \вычислимая последовательность", мы получаем определение перечислимого множества. Что касается определения термина \вычислимая последовательность", то оно сейчас будет дано. Последовательность w1 ; w2 ; : : : ; wn ; : : : называется вычислимой, коль скоро существует алгоритм, вычисляющий её n-ый член wn по его номеру n. Поэтому понятие вычислимой последовательности называют алгоритмическим аналогом или эффективным аналогом понятия последовательности, а понятие перечислимого множества | алгоритмическим аналогом или эффективным аналогом понятия счётного множества. Перечислимые множества называются также эффективно счётными. Повторим определение: множество называется перечислимым, или эффективно счётным,

если оно либо пусто, либо может быть расположено в вычислимую последовательность (то есть является множеством членов какой-либо вычислимой
10


Все рассматриваемые нами языки суть подмножества декартова произведения в и, следовательно, счётны. Идеология Колмогорова состояла в том, что бы рассматривать только эффективно счётные (они же | перечислимые) языки. Окончательно надлежащий выбор языков о семейства произвёл колмогоровский ог ученик Леонид Левин. Именно, в 1973 г. он ввёл в рассмотрение семейство монотонных языков и изучил соответствующее этому семейству понятие хаотичности. Приведём нео бходимые определения. Будем говорить, что двоичные слова u и v согласованы и писать u v, если одно из этих слов есть начало другого. Язык E называется монотонным, если он перечислим и выполнено условие: [ x1 ; y1 E & x2 ; y2 E & (x1 x2 )] = [y1 y2 ]: Последовательность, удовлетворяющую условию хаотичности для семейства монотонных языков, то есть условию
c

последовательности).

n KP(a1 ; a2 ; : : : ; an ) > n - c

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

C = T.

TC



S, TC = S.

11


Лицо Третье: ТИПИЧНОСТЬ
Сказать про какой-либо о бъект, что он типичен | это значит сказать, что он принадлежит к любому подавляющему большинству. Например, типичный человек, встреченный на московской улице, имеет рост менее двух метров (т. е. принадлежит к подавляющему большинству людей, имеющих рост менее двух метров), возраст более трёх лет (т. е. принадлежит к подавляющему большинству людей, имеющих возраст более трёх лет) и т. д. Конечно, любое из большинств, о которых идёт речь, должно быть разумным: ведь какой о бъект ни возьми, он заведомо не принадлежит к подавляющему большинству, о бразованному всеми остальными, отличными от данного, о бъектами. Мы исходим из интуитивного представления о том, что случайный о бъект должен о бладать свойством типичности. Наша цель | дать строгое математическое определение этого свойства для последовательностей нулей и единиц при равномерном распределении вероятностей на пространстве таких последовательностей. Последовательности, удовлетворяющие этому строгому определению, мы будем называть типическими, оставляя слово типичный для употре бления на интуитивном уровне. В силу сказанного выше, нам надо определить сперва, что есть подавляющее большинство последовательностей, а затем | какие большинства следует считать разумными. А тогда класс типических последовательностей автоматически определится как пересечение всех разумных большинств, Оставляя термин \подавляющее большинство" для интуитивного употре бления, мы будем говорить о больших множествах последовательностей. Дополнение к большому множеству до всего будем называть малым. Очевидно, достаточно определить, что такое малое множество, | а тогда большие множества определятся как дополнения к малым. Итак, пусть дано какое-то множество Q последовательностей, Q . Мы хотим определить, когда его следует считать малым. В терминах теории вероятностей мы сказали бы, что Q малое, коль скоро вероятность попадания в Q равна нулю. В терминах теории меры мы сказали бы, что Q малое, коль скоро оно имеет меру нуль. Мы, однако, постараемся определить, что такое малое множество в более простых терминах. Множество Q называется малым, если его можно покрыть шарами, сумма о бъёмов которых сколь угодно мала. Определению малого множества можно дать такую формулировку: множество Q называется малым, когда для каждого натурального числа m найдётся такая последовательность двоичных слов x(1); x(2); : : : ; x(n); : : : , что

Q
n

n

x(n)

;
<

v(

x(n)

)=

n

2-|

x(n)|

1 : m

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


\Разумность" вводится путём следующей корректировки определения. Во-первых, потре буем, что бы упоминаемая в определении последовательность двоичных слов x(1); x(2); : : : ; x(n); : : : была вычислимой. Другими словами, мы тре буем, что бы существовал алгоритм, вычисляющий её n-ый член xn по его номеру n. Во-вторых, потре буем, что бы такая вычислимая последовательность не просто существовала для каждого m, но строилась бы по этому m эффективно. Слово \эффективно" означает `с помощью алгоритма'. Здесь нео бходимы разъяснения. Дело в том, что алгоритм, получающий на вход m и выдающий на выходе тре буемую последовательность, невозможен просто потому, что последовательность | это бесконечный о бъект, а алгоритмы оперируют лишь с конечными о бъектами. Однако в нашем случае, поскольку последовательность вычислима, то у неё есть алгоритм, который её вычисляет | даже очень много таких алгоритмов. Алгоритмы (в другой системе терминов | программы алгоритмов) являются конечными о бъектами и потому вполне осмысленно говорить о б алгоритме, который по числу m, поступившему на его вход, выдаёт на выходе один из алгоритмов (в другой системе терминов | одну из программ), вычисляющих последовательность x(1); x(2); : : : ; x(n); : : : . Внеся в определение малого множества эти два до бавления, мы получаем определение эффективно малого множества | а тем самым и определение эффективно большого множества. Пересечение всех эффективно больших множеств оказывается непустым. Более того, оно само является эффективно большим. Это наименьшее среди эффективно больших множеств и есть искомое множество T всех типических последовательностей. Типические последовательности называют также случайными по Мартин-Лёфу | по имени ученика Колмогорова, замечательного шведского математика Пера МартинЛёфа, который в 1966 г. сформулировал только что изложенное определение случайности. Как уже говорилось, класс T всех типических последовательностей совпадает с классом C всех хаотических последовательностей: Поэтому типические последовательности можно именовать также хаотическотипическими или типическо-хаотическими, а сам класс всех таких последовательностей о бозначать CT или TC. Как мы уже знаем,

T = C.

CT



S, CT = S.

13


Лицо Четвёртое: НЕПРЕДСКАЗУЕМОСТЬ
Вот начало Двенадцати стульев Ильфа и Петрова: \В уездном городе N было так много парикмахерских заведений и бюро похоронных процессий, что казалось, жители города рождаются лишь затем, что бы по бриться, остричься, освежить голову вежеталем и умереть". Суждение остаётся верным, если заменить N на Москву, парикмахерские на залы игровых автоматов, похоронные бюро на казино, а цель рождения на \играть и умереть". Этот печальный факт, однако, позволяет наглядно о бъяснить то свойство случайных последовательностей, которое мы называем непредсказуемостью. Интуитивно ясно, что всякая случайная последовательность является непредсказуемой в том смысле, что в каком бы порядке мы не выбирали её члены, знание значений уже выбранных членов не позволяет предсказать значение того следующего члена, который мы намереваемся выбрать. Таким о бразом, Казино, о бладающее такой последовательностью и предлагающее Игроку угадывать её члены и делать при этом денежные ставки, не разорится; говоря более точно, Казино уверено, что никакой Игрок не может о бладать такой стратегией игры, которая приведёт к разорению Казино. Итак, представим се бе что Игрок приходит в Казино. Каждая из сторон | и Казино, и Игрок | о бладает своим начальным капиталом. Казино располагает некоторой фиксированной, но неизвестной Игроку последовательностью нулей и единиц и предлагает Игроку предсказывать её члены | нео бязательно в монотонном порядке их следования и даже нео бязательно все её члены. Для наглядности представим се бе, что члены последовательности написаны на картах, которые лежат рубашками вверх, так что Игрок не видит, что там написано. Последовательность предстает перед Игроком в виде бесконечного ряда таких карт. Игра состоит в том, что Игрок на каждом своём ходу указывает ту карту, которая должна быть открыта, одновременно предсказывая значение, которое о бнаружится на этой карте, и о бъявляя размер денежной ставки. Если предсказание окажется правильным, Казино выплачивает Игроку сумму ставки, если неправильным | Игрок выплачивает эту сумму Казино. Считается, что Игрок выиграл, если он сумел разорить Казино. Разумеется, если Игроку открыт кредит, он всегда может разорить Казино, удваивая ставки. Но Игра идёт на наличные, так что величина ставки ограничена текущим капиталом Игрока. Последовательность называется предсказуемой, если Игрок о бладает алгоритмом, позволяющим ему разорить Казино, каким бы начальным капиталом это Казино ни о бладало. Последовательность называется непредсказуемой, если она не является предсказуемой. На математическом языке ситуация описывается так. Рассматривается бесконечная последовательность нулей и единиц

a = a1 ; a 2 ; a3 ; : : : ; :
При каждом ходе Игрока возникает тройка чисел
n; i; v ;

где

n N; i {0; 1}; v Q; v 0:

14


Содержательно: натуральное число n есть номер того члена последовательности, на который делается ставка; i есть предсказываемое значение этого члена; неотрицательное рациональное число v есть размер ставки. Ходы делаются друг за другом, начиная с первого; тройка, возникающая на k-том ходу, о бозначается n(k); i(k); v(k) . Более математически грамотно было бы сказать, что каждый ход есть тройка чисел, и что ходы не делаются, а предъявляются. Капитал Игрока перед k-тым ходом о бозначается V (k - 1); без ограничения о бщности можно считать, что начальный капитал Игрока V (0) равен единице. После каждого хода капитал Игрока меняется (если только ставка не была нулевой). А именно: если i(k) = an(k) (Игрок угадал), то V (k) = V (k - 1) + v(k) если i(k) = an(k) (Игрок не угадал), то V (k) = V (k - 1) - v(k). И ещё два прибавления к сказанному. Во-первых, некоторые ходы о бъявляются незаконными. А именно, k-тый ход считается незаконным в одном из двух случаев: 1) если Игрок тре бует открыть карту, уже открытую ранее, т. е. если n(k) совпадает с одним из чисел n(1); : : : ; n(k - 1); 2) если делаемая Игроком ставка превышает имеющийся у него капитал, т. е. если v(k) > V (k - 1). Как только Игрок делает незаконный ход, Игра останавливается, и Игрок остаётся при имеющемся у него к данному моменту капитале. Во-вторых, не исключается возможность того, что Игрок воо бще не делает очередного хода (даже самого первого хода!). В этом случае Игрок также остаётся при имеющемся у него к данному моменту капитале. Однако в этом случае | в отличие от случая незаконного хода | мы избегаем выражения игра останавливается. Дело в том, что ситуацию можно наглядно представить се бе следующим о бразом. Перед каждым своим ходом Игрок решает, делать ли ему ход и если делать, то какой именно. Решение тре бует о бдумывания, и Игрок берёт время на о бдумывание. Время о бдумывания ничем не ограничено и может затянуться до бесконечности. Если Игрок за конечное время принимает решение не делать ход, то можно сказать, что игра останавливается и что капитал Игрока не меняется. Но если Игрок никогда не приходит ни к какому решению, его капитал тоже не меняется, но в этом случае не наступает момента остановки игры. Разумеется, всё сказанное носит иллюстративный характер, и математическое описание не включает в се бя ссылку на такие понятия, как `решать', `о бдумывать' и т. п. По определению, Игрок выигрывает, если sup V (k) = ;
W k Содержательно это означает, что Игрок талом W Казино ни о бладало. Очевидно, условии, что всякий раз, когда ему предст раз этот ход оказывается законным.


т. е. если

k

V (k) > W: разоряет Казино, каким бы исходным капичто Игрок в состоянии выиграть лишь при оит делать ход, он его делает, причём всякий

15

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

(Если k = 0, таблица пуста.) На математическом языке стратегия есть функция, которая каждой подо бной таблице (в том числе пустой) либо ничего не ставит в соответствие, либо ставит в соответствие некоторый ход, т. е. тройку n; i; v . Под \каждой подо бной таблицей" мы понимаем отнюдь не только такую таблицу, которая отражает реальное течение игры, а произвольную таблицу, в которой в первой строке стоят положительные целые числа, в третьей | неотрицательные рациональные числа, а во второй и четвёртой | нули и единицы. Если таблица реально встретилась в процессе игры (в качестве истории игры на каком-то этапе) и если задана стратегия, то первые три строки таблицы однозначно восстанавливаются по её четвёртой строке. В самом деле, применение стратегии к пустой таблице даёт нам первый ход n(1); i(1); v(1) . Тем самым | поскольку четвёртая строка предполагается известной | мы получаем историю игры перед вторым ходом в виде таблицы n(1) i(1) v(1) an(1) Теперь к этой таблице снова применяем стратегию, получаем второй ход n(2); i(2); v (2) и таблицу n(1) n(2) i(1) i(2) v(1) v(2) an(1) an(2) И так далее. 16


Сказанное даёт нам право при определении стратегии брать в качестве аргумента не всю таблицу в целом, а лишь её четвёртую строку. Заметим, что в этой четвёртой строке стоит двоичное слово, т. е. элемент множества . Стратегия должна, имея этот элемент, или не выдавать ничего, или выдавать ход, который есть тройка, то есть элемент декартова произведения N в {0; 1} в Q0 . Здесь символом Q0 о бозначено множество всех неотрицательных рациональных чисел. Мы приходим к окончательному определению понятия стратегии: стратегия есть ото бражение некоторого подмножества множества всех двоичных слов в декартово произведение N в {0; 1} в Q0 :
-

N

в{

0; 1} в Q0 :

Для наших целей осо бый интерес представляет случай, когда указанное ото бражение задаётся каким-то алгоритмом. Поясним, что это значит. Пусть A | алгоритм, на вход которого могут подаваться элементы из множества X , а на выходе получаются элементы из множества Y . В множестве X выделяется область результативности алгоритма A, состоящая из тех и только тех элементов, в применении к которым A даёт результат. Алгоритм A задаёт следующее ото бражение: о бласть определения этого ото бражения совпадает с о бластью результативности алгоритма, и для каждого элемента этой о бласти значение ото бражения на этом элементе совпадает с тем результатом, который получается при применения алгоритма к этому элементу. Если стратегия задана каким-то алгоритмом, она называется вычислимой. (Если подать на вход задающего стратегию алгоритма такую историю игры, для которой очередной ход не определён, то алгоритм либо выдает соо бщение о б отсутствии результата, либо работает на этом входе бесконечное долго, не приходя ни к какому результату, но и не выдавая соо бщение о б отстутствии такового; эта бесконечная работа алгоритма и представляет со бою то бесконечное время, взятое Игроком на о бдумывание, о котором говорилось выше.) Стратегия называется выигрышной, если при её использовании Игрок выигрывает. Последовательность называется предсказуемой, если для неё существует выигрышная вычислимая стратегия, и непредсказуемой в противном случае. Класс всех непредсказуемых последовательностей о бозначается буквой U. Известно, что всякая непредсказуемая последовательность стохастична по Колмогорову (принадлежит классу S) и что всякая типическо-хаотическая последовательность (последовательность класса CT) непредсказуема: CT U S. Известно также, что класс стохастических по Колмогорову последовательностей существенно шире класса непредсказуемых: S = U. Открытым остаётся вопрос о совпадении классов хаотических и непредсказуемых последовательностей: Эта важная про блема ждёт своего решения. 17

CT = U ??


ИСТОРИЯ И БИБЛИОГРАФИЯ
[КУ] А. Н. Колмогоров, В. А. Успенский. Алгоритмы и случайность // Теория вероятностей и её применения, 1987, т. 32, вып. 3, с. 425{455. [УС] В. А. Успенский, А. Л. Семёнов. Теория алгоритмов: основные открытия и приложения. | М.: Физматлит, 1987. | 288 c. [УСШ] В. А. Успенский, А. Л. Семенов, А. Х. Шень. Может ли индивидуальная последовательность нулей и единиц быть случайной? // Успехи математических наук, 1990, т. 45, вып. 1, с. 105{162. [MSU] An. A. Muchnik, A. L. Semenov, V. A. Uspensky. Mathematical metaphysics of randomness // Theoretical Computer Science, 1998, vol. 207, pp. 263{317. [Вь] В. В. Вьюгин. Алгоритмическая энтропия (сложность) конечных о бъ// Семиотика и информатика. Выпуск 16. | М: ВИНИТИ, 1981. | С. 14{43. Разумеется, этот список из пяти названий никоим о бразом не претендует на полноту. Однако в этих публикациях можно найти дальнейшие ссылки, и список этих ссылок уже претендует если не на полноту, то на некоторое приближение к оной. В книге [УС] следует о братить внимание на § 2.6 Приложения к теории вероятностей: определения случайной последовательности. Следует также иметь в виду, что терминология этой книги несколько архаична: хаотические последовательности называются там случайными по Колмогорову, а типические | случайными по Мартин-Лёфу. Частотоустойчивые, они же стохастические, последовательности называются там случайными по Мизесу, стохастические по Чёрчу | случайными по Мизесу{Чёрчу, стохастические по Колмогорову | случайными по Мизесу{Колмогорову{Лавлэнду (а в [УСШ] | стохастическими по Колмогорву{Лавлэнду; Д. Лавлэнд D. Loveland открыл эти последовательности независимо от Колмогорова, хотя и позже: соответствующая статья Колмогорова была опубликована в 1963 г., статья Лавлэнда | в 1966 г.) Что касается непредсказуемых последовательностей | в том точном понимании, как было сформулировано выше, | то они в указанной книге отсутствуют, поскольку появились в литературе лишь в 1998 г. в статье [MSU]. Предложение измерять сложность о бъекта длиной его кратчайшего описания и понятие оптимального языка были сформулированы Колмогоровым в статье 1965 г.; за год то того сходные идеи были опубликованы американским исследователем Рэем Соломоновым Ray Solomono , о работах которого Колмогоров узнал лишь позже. Ввиду этого теорему о существовании оптимального языка мы называем Теоремой Соломонова{ Колмогорова. В эти же годы (т. е. в середине 60-х годов XX в.) Колмогоров высказывает на своих семинарах предположение о том, что быстрота роста энтропии начальных отрезков последовательности может служить критерием случайности рассматриваемой последовательности. Однако введённое им в рассмотрение языков семейство приводиое ло к энтропии, непригодной для поставленной цели. Как уже говорилось выше, в главке о хаотичности, годные для этой цели семейства нашёл Леонид Левин соответственно в 1973 г. (монотонные языки) и в 1974 г. (префиксные языки). Типические последовательности (под названием случайных, random) были, как уже отмечалось в главке о типичности, открыты в 1966 г. Пером Мартин-Лёфом Per 18

ектов и её применение к определению случайности и количества информации


Martin-L . of Утверждение о том, что класс последовательностей, стохастических по Колмогорову, шире класса типических (они же | хаотические) последовательности доказал Александр Шень (доказательство опубликовано в 1988 г.). При доказательстве он использовал последовательность, построенную для других целей голландским математиком ван Ламбальгеном, и потому и своё доказательство иногда приписывает Ламбальгену. Здесь в Шене как бы проявляется ген его научного прадеда Н. Н. Лузина, относительно которого велики французский математик Анри Ле бег писал: \Г-н Лузин лишь тогда бывает совершенно счастлив, когда ему удаётся приписать со бственные открытия кому-либо другому". Пусть K | энтропия в каком-то из вариантов этого понятия (В литературе вопроса исследованы не менее шести таких вариантов: простая, априорная, монотонная, процессная, префиксная и энтропия разрешения; все эти варианты различны в том точном смысле, что разность энтропий, принадлежащих любым двум из перечисленных вариантов, неограниченна.) Скажем, что последовательность a1 a2 a3 :::an ::: является хаотической относительно K, если
c

n K(a1 a2 a3 :::an ) > n - c:

(Заметим для ясности, что ни для простой энтропии, ни для энтропии разрешения последовательностей с таких последовательностей нет вовсе.) В той же статье Левина 1973 г., в которой была введена монотонная энтропия, содержалось и доказательство того факта, что понятие хаотичности относительно монотонной энтропии равноо бъёмно понятию типичности. Независимо от Левина в том же 1973 г. К. П. Шнорр C. P. Schnorr ввел в рассмотрение свой вариант энтропии, так называемую процессную энтропию (у Шнорра | process complexity), и доказал (независимо от Левина, но очень похожим спосо бом), что понятие хаотичности относительно процессной энтропии также равноо бъёмно понятию типичности. Хотя процессная энтропия и монотонная энтропия существенно различаются (как показал В. В. Вьюгин [Вь, с. 35, строки 6{4 снизу], их разность не ограничена никакой константой) и хотя впоследствии сам Шнорр перестал использовать свою процессную энтропию, вышеуказанную Теорему Левина иногда называют Теоремой Левина{Шнорра. Префиксную энтропию ввёл в 1974 г. Левин и годом позже, но, надо полагать, независимо от Левина, Чэйтин Gregory J. Chaitin (см. J. Assoc. Comput. Mach., 1975, v. 22, p. 329{340). В той же статье Чэйтин ввёл понятие хаотичности относительно префиксной энтропии и о бъявил, без доказательства, что этот вариант хаотичности равносилен типичности; первое опубликованное доказательство этого факта появилось в статье В. В. Вьюгина [Вь]: следствие 3.2 на с. 38. Префиксная энтропия | это, по определению, энтропия для семейства префиксных языков. Язык E называется префиксным, если он перечислим и выполнено условие: [ x1 ; y1 E & x2 ; y2 E & (x1 x2 )] = [y1 = y2 ]: Заметим ещё, что в литературе термин сложность (complexity) часто употре бляется в смысле `энтропия', то есть в смысле `сложность относительно оптимального языка'. 19


Непредсказуемые последовательности впервые возникли весной 1991 г. в совместном докладе под названием Randomness and Lawlessness (Случайность и Беззаконность), который Ан. А. Мучник, А. Л. Семёнов и В. А. Успенский сделали на конференции в Калифорнии. Конференция была посвящена основаниям теории случайности и проходила с 4 по 7 марта в Станфордском университете. Содержание доклада было опубликовано в 1998 г. в виде статьи [MSU]. В этой статье приведены, в частности, теоремы о соотношении непредсказуемости с другими алгоритмическими лицами случайности. Сама идея о связи случайности с невозможностью гарантированного выигрыша достаточно очевидна и в тех или иных вариантах высказывалась и раньше, однако формулировка из [MSU] кажется более близкой к интуитивному представлении о случайности. В частности, предшествующие игровые определения заведомо не приводили к классу последовательностей, равноо бъёмному классу типическо-хаотических последовательностей; для определения непредсказуемости из [MSU] этот вопрос, как уже отмечалось, открыт. Ясно, что чем б ольшим количеством лиц случайности характеризуется какой-то точно очерченный класс последовательностей, тем больше надежда, что этот класс может служить формальным аналогом расплывчатого интуитивного представления о случайности.

20