Реферат: Случаен ли исход бросания монеты?

Случаен ли исход бросания монеты?

Дж. Форд, Профессор физики Технологического института шт. Джорджия, редактор журнала Physica D: Nonlinear Phenomena

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

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

Лаплас

Теория вероятностей — вот истинная логика этого мира.

Максвелл

Вероятностный подход к макроскопическим явлениям на протяжении веков сосуществовал с детерминистским подходом. Например, в период с 1650 по 1750 г. Ньютон построил детерминистское дифференциальное и интегральное исчисление, а представители семейства Бернулли разработали теорию вероятностей для случайных игр и различных других проблем многих тел. Оглядываясь назад, можно лишь удивляться тому, что столь явно противоположные взгляды на мир никогда не приводили к острым столкновениям. Столкновения, наверное, были бы неизбежны, если бы не Лаплас, необычайно успешно способствовавший возведению ньютоновского детерминизма в ранг догмата научной веры. После Лапласа вероятностное описание считалось не более чем полезным приёмом, к которому надлежало прибегать, когда по тем или иным причинам детерминистские уравнения движения трудно или даже невозможно решить точно. Более того, считалось, что вероятностное описание может быть выведено из детерминистских уравнений, хотя никто и никогда не указывал конкретно, как это можно было бы осуществить.

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

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

первый член которого H0 есть гамильтониан системы с N степенями свободы, допускающей точное аналитическое решение, а второй — возмущение H1 с малым параметром λ, характеризующим интенсивность возмущения; через (q, p) обозначен полный аргумент (q1, ..., qN, p1, ..., pN). Существует физико-математический миф о том, что будто бы при малом числе степеней свободы N гамильтонианы такого вида аналитически разрешимы и детерминированны, а при больших N вступает в силу статистическая механика и закон больших чисел. Но такой миф сразу же вызывает сомнения, стоит лишь вспомнить о снискавшей печальную известность неразрешимости проблемы трёх тел или даже о тесно связанной с ней проблеме двух тел; о предостережении Пуанкаре, обнаружившего, что независимо от N гамильтоновы системы в подавляющем большинстве случаев не имеют других регулярных интегралов движения, кроме самого гамильтониана H; о том, что ни одна теорема о вероятностях никогда не выводилась из аналитического решения уравнения движения для игральной кости; и наконец, о существовании бесконечного класса аналитически разрешимых проблем многих тел при произвольно большом N, который без особого труда можно построить с помощью классической теории возмущений 1 . Итак, неразбериха в вопросе о случайном и детерминированном вполне очевидна. Но гораздо хуже, что ещё большая неразбериха царит в вопросе о том, какого рода поведения следует ожидать от решений системы с любым конкретным гамильтонианом. Трудно поверить, хотя это действительно так, что на протяжении многих десятилетий в учебных аудиториях и учебниках преподаватели и учёные хранят весьма примечательное почти полное молчание 2 обо всём этом, как если бы гамильтониан (1) был болен неизлечимой болезнью, о которой не принято упоминать в хорошем обществе. Но примерно с начала 50-х годов XX века, через триста лет после рождения Ньютона, новая междисциплинарная область науки — так называемая нелинейная динамика — принялась средствами своих смежных дисциплин за решение некоторых проблем, возникающих в связи с такими гамильтонианами. Мы кратко изложим один новый результат, имеющий прямое отношение к затронутой нами теме. Более подробное изложение можно найти в обзорных статьях Дж. Лебовитца и О. Пенроуза [3], а также М. Берри [4].

СОВРЕМЕННЫЕ РЕЗУЛЬТАТЫ

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

При достаточно малой энергии E гамильтониан H в очень хорошем приближении описывает два несвязанных гармонических осциллятора. С возрастанием же энергии системы на поведении траекторий начинает всё сильнее сказываться нелинейная кубическая связь. Этот гамильтониан привлёк внимание многих после того, как был опубликован в неоднократно цитированной и ставшей классической работе М. Хенона и К. Хейлеса [5]. Читателю, которому приводимое ниже краткое резюме покажется недостаточно вразумительным, мы рекомендуем обратиться за объяснениями к статье [5].

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

Хенон и Хейлес интегрировали численно уравнения движения для своего гамильтониана, рассчитывая траектории при разных энергиях. Чтобы сразу было видно, по какой — двумерной или трёхмерной — поверхности в четырёхмерном фазовом пространстве проходит та или иная траектория, они выводили на дисплей координаты точек, в которых траектории пересекают плоскость (q2, p2), в виде графиков на плоскости (q2, p2). Если данная траектория лежит на двумерной поверхности, то точки её пересечения с плоскостью (q2, p2) лягут на некую кривую. Если же траектория свободно «плавает» по всей трёхмерной поверхности или по какой-то её части, то точки пересечения с плоскостью (q2, p2) заполнят некоторую часть плоскости. На рис. 1 показаны такие графики.

Рис. 1. Траектории, полученные путём численного интегрирования уравнений движения с нелинейным гамильтонианом (2). На графиках показаны пересечения траекторий с плоскостью (q2, p2). Слева энергия системы равна 1/12. Каждая кривая на графике состоит из точек пересечения одной траектории. Непрерывность и замкнутость кривых означает, что траектории лежат на двумерных поверхностях в четырёхмерном фазовом пространстве (q1, q2, p1, p2). График в центре построен при энергии системы, равной 1/8. Некоторые траектории по-прежнему лежат на двумерных поверхностях. Хаотическую же россыпь точек дала одна траектория, заполняющая некий трёхмерный объём; в этом случае энергия — единственный интеграл движения. На графике справа энергия равна 1/6. Все отдельные точки соответствуют одной траектории, которая свободно блуждает по некоторой части трёхмерной энергетической поверхности. При энергии, равной 1/6, почти все пары точек, находившихся первоначально достаточно близко друг от друга на плоскости (q2, p2) со временем экспоненциально расходятся.

При энергии E = 1/12 всякая траектория даёт некую кривую. Это означает, что при такой энергии движение полностью упорядочено и гамильтониан аналитически разрешим, т.е. интегрируем. Но при энергии E = 1/6 Хенон и Хейлес обнаружили нечто показавшееся тогда удивительным: даже простые системы могут вести себя как бы хаотически. Переход от порядка к хаосу происходит при энергии E = 1/8. В обоих случаях всю россыпь точек дала одна-единственная траектория. На мысль о хаосе и случайности наводит явная беспорядочность в распределении точек: если наблюдать на дисплее за появлением точек пересечения траектории с плоскостью (q2, p2) при E = 1/6, то обнаружить какую-нибудь пространственную или временную упорядоченность не представляется возможным. Итак, переход от траектории на двумерной поверхности к траектории на трёхмерной поверхности привносит в движение элемент хаоса. Быть может, нашей интуиции ближе другое представление: при E = 1/12 две соседние точки пересечения траектории с плоскостью (q2, p2) удаляются друг от друга линейно по времени, а при E = 1/6 — экспоненциально. Аналогичную ситуацию мы видим на рис. 2, где показан переход к турбулентности в струйке дыма от сигареты.

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

ХАОТИЧЕСКИЕ ТРАЕКТОРИИ

Выражение «хаотическая траектория» означало до сих пор лишь немногим больше, чем то, что траектория не лежит на гладкой инвариантной интегральной поверхности, размерность которой меньше размерности энергетической поверхности. Но каков точный смысл того, что такая траектория более случайна или менее детерминированна, чем траектория, лежащая на гладкой инвариантной поверхности меньшей размерности? Нелинейная динамика даёт на этот вопрос целую иерархию ответов [3, 4]; мы обсудим лишь один из них, имеющий непосредственное отношение к нашей основной теме. Представим себе, что заданная энергетическая поверхность динамической системы разделена на конечное множество неперекрывающихся пронумерованных ячеек так, будто мы пытались придать поверхности сходство с колесом рулетки. Предположим, что кто-то точно знающий траекторию системы называет нам через каждую секунду номер ячейки, в которой в данный момент оказывается состояние системы (как если бы кто-нибудь раз в секунду называл номер того сектора вращающегося колеса рулетки, который в данный момент оказался под шариком-указателем). Рассматривая траектории нехаотической системы, например простого гармонического осциллятора или системы Хенона–Хейлеса при малой энергии, мы обнаружим, что номера образуют регулярную последовательность. Правильную прогрессию мы получим даже в том случае, если период осциллятора равен нецелому числу секунд — необходимо лишь накопить данные за несколько периодов. Рассматривая же хаотические траектории, например траектории системы Хенона–Хейлеса при большей энергии или траектории частиц сигаретного дыма за порогом перехода к турбулентности, мы никогда не заметим регулярности. С таким же успехом мы могли бы наблюдать за номерами вращающегося колеса рулетки. Следовательно, в случае хаотической орбиты мы можем, самое большее, указать вероятности переходов от одного номера ячейки к другим, но не можем предсказать сами переходы.

Итак, назовём орбиту хаотической, если, зная номера ячеек, в которых система находилась в прошлом, т.е. все номера ячеек, выпавшие до текущего значения t, невозможно определить номер ячейки при t+1 и при любом большем значении t. (Такое определение может показаться несколько необычным, но, как мы убедимся, оно имеет свой смысл.) В случае хаотических орбит крупнозернистое будущее не определяется однозначно крупнозернистым прошлым. Только полной последовательностью результатов измерений, выполненных с конечной точностью через ненулевые интервалы времени от t = –∞ до t = +∞, можно задать точную траекторию, но и тогда она, возможно, будет задана неоднозначно. В случае же нехаотических орбит будущее полностью и однозначно определяется крупнозернистым прошлым. Нехаотические системы сохраняют крупнозернистую детерминированность, даже если наблюдения производятся с конечной точностью.

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

ПРОСТАЯ МОДЕЛЬ

Тому, кто не искушён в алгоритмическом искусстве генерирования псевдослучайных чисел, итерация вперёд разностного уравнения первого порядка

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

Оно произведёт большее впечатление, если в качестве начального значения X0 написать какое-нибудь число в двоичной форме, например

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

Чтобы убедиться в этом, прежде всего заметим: все результаты итерации уравнения (3) принадлежат единичному интервалу (0, 1), и, следовательно, «энергетическая поверхность» в данном случае есть не что иное, как единичный интервал (0, 1). Разобьём эту «энергетическую поверхность» на две ячейки: левую (0≤X<½) и правую (½≤X<1). По двоичному представлению (5) нетрудно определить, в какой — левой или правой — ячейке единичного интервала окажется результат Xn итерации: для этого необходимо лишь знать, какая цифра — 0 или 1 — стоит справа от переместившейся запятой. Если теперь кто-нибудь знающий точную траекторию системы будет сообщать нам только, в какую из ячеек — левую или правую — попадают результаты последовательных итераций Xn, мы сможем выписать последовательность номеров ячеек, состоящую из нулей и единиц (нуль — левая ячейка, единица — правая). Вся последовательность номеров целиком совпадает с двоичным разложением начального значения X0 для заданной траектории. Иначе говоря, тот, кто знает траекторию, просто считывает двоичную последовательность для X0, а тот, кто слушает (или наблюдает), записывает её. Поскольку в общем случае мы не можем определить будущие цифры двоичного разложения числа X0 по какой-либо конечной прошлой части этой последовательности двоичных цифр, истинная траектория в соответствии с нашим определением хаотична.

Хаотические траектории, удовлетворяющие уравнению (3), позволяют нам продемонстрировать весьма общую непредсказуемость в поведении хаотических траекторий, которая находится в опасной близости к истинной случайности.

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

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

Изложенные соображения относятся к весьма разработанной теории 3 в нелинейной динамике, которая строго доказывает, что чисто детерминированные системы могут в той или иной степени имитировать подлинную случайность. Но существует также строгая теория, в которой показывается, что детерминированная система может вести себя действительно хаотически. Прежде чем переходить к этой теории, напомним, что хаотическим траекториям при разбиении фазового пространства всегда можно сопоставить последовательности целых чисел — номеров ячеек. Кроме того, если удаётся показать, что строка номеров ячеек для какой-то траектории случайна, то и сама траектория также случайна [7]. Но тогда сразу же возникает вопрос о том, как может быть подлинно случайной любая конкретно заданная строка цифр, например десятичное разложение числа π или строка цифр в таблице случайных чисел. Так, мы, наконец, подошли к одному из самых глубоких вопросов теории вероятностей: определению случайности заданных строк цифр.

ТЕОРИЯ СЛОЖНОСТИ АЛГОРИТМОВ

Не уменьшая общности, мы можем ограничиться рассмотрением последовательностей двоичных цифр, причём сначала нас будут интересовать только конечные последовательности. Каждая отдельная двоичная цифра несёт один бит информации (по определению бита). Следовательно, в n-значной двоичной последовательности может содержаться n битов информации. Но часто цифры последовательности бывают заметно коррелированы, и информацию, содержащуюся в n-значной последовательности, можно передать более короткой последовательностью. Такой более короткой последовательностью может быть, например, сравнительно небольшой машинный код, способный порождать более длинные исходные n-значные последовательности на некоторой машине M. А. Н. Колмогоров, Г. Чейтин и Р. Соломонов независимо друг от друга ввели [8] количественную характеристику KM(n) — сложность n-значной последовательности, равную длине (в битах) самой короткой программы, способной заставить машину M отпечатать данную последовательность. Впоследствии А. Н. Колмогоров по существу доказал, что для некой универсальной вычислительной машины величина KM(n) минимальна. Следовательно, индекс M можно без потери общности отбросить. Посмотрим теперь, какова сложность K(n) простой последовательности, состоящей из n единиц. Минимальная программа могла бы быть такой: «PRINT 1, n раз». Длина её в битах при достаточно больших n почти равна log2 n. Более того, сложность K(n) любой последовательности, вычисляемой путём повторения некоторого конечного алгоритма для вычислительной машины, при достаточно больших n мало отличается от log2 n. В то же время сложность n-значной последовательности {Gn} не может намного превышать число n, поскольку такую последовательность всегда можно получить с помощью программы «PRINT G1, G2, ..., Gn», содержащей при больших n число битов, мало отличающееся от n. Согласно определению сложности, максимально сложные n-значные последовательности не могут быть вычислены с помощью какого-либо алгоритма, длина которого (в битах) значительно меньше длины (в битах) самой последовательности. Таким образом, информация, содержащаяся в максимально сложной последовательности, закодирована необратимо и нет более простого способа восстановить последовательность, нежели предъявить её копию. Цифры в таких максимально сложных последовательностях настолько невычислимы, а значит и непредсказуемы, что слово «случайные» кажется неизбежным. Итак, следуя Колмогорову и другим авторам, назовём конечную заданную строку знаков случайной, если она максимально сложна. Исходя из такого определения, можно показать, что большинство конечных последовательностей цифр случайно.

Когда число знаков двоичной последовательности стремится к бесконечности, невольно хочется (и Колмогоров первоначально так и поступил) назвать случайной бесконечной последовательностью такую, сложность K(n) которой при больших n стремится к n. Но, как доказал П. Мартин-Лёф, такое определение бессодержательно, поскольку для случайных последовательностей величина K(n) может колебаться, опускаясь намного ниже среднего значения порядка n, даже при n, стремящемся к бесконечности. Чтобы исключить, или «погасить», такие колебания, можно определить [81 сложность бесконечной последовательности как

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

«Вычислимый критерий» — это критерий, представимый конечным алгоритмом. Так как случайность означает в том или ином смысле отсутствие порядка, а встречающийся в природе беспорядок бесконечно разнообразен, не существует единого вычислимого критерия, который позволял бы строго доказать, что интересующая нас последовательность случайна. Отдельные вычислимые критерии — это необходимые, но недостаточные критерии случайности. Но можно объединить все возможные вычислимые критерии в один сложный критерий и определять, удовлетворяет ли некоторая последовательность всем критериям случайности, вычисление которых посильно для человека. Назовём такой критерий «универсальным критерием случайности». Теперь известно, что почти все максимально сложные последовательности удовлетворяют универсальному критерию случайности. Эта теорема, доказанная Мартин-Лёфом в 1966 г., служит оправданием для нашего определения случайной последовательности как максимально сложной последовательности, поскольку ни один человек не сможет отличить новое определение от нашего старого. Наконец, Мартин-Лёф доказал, что почти все последовательности — максимально сложные и, следовательно, случайные. Из этого доказательства непосредственно следует, что почти все отдельные траектории уравнения (3) не только строго детерминированны, но и полностью случайны — вывод, который подробнее обсудим ниже.

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

В качестве дополнительного следствия из теории сложности алгоритмов отметим одно довольно удивительное обстоятельство: числа π и e не дают случайных строк цифр, так как их оба можно вычислять путём бесконечного повторения коротких алгоритмов, а это означает, что величина K [формула (6)] равна нулю. Кроме того, если мы назовём невычислимым 5 число с максимально сложной строкой двоичных цифр, то почти все действительные числа окажутся невычислимыми — их нельзя вычислить с помощью какого-либо конечного алгоритма. Как говорит М. Кац 6 , почти все числа в континууме невозможно определить конечным числом слов. Следовательно, континуум обладает той отличительной особенностью, что представляет собой вполне определённое множество по большей части неопределённых объектов. Таким образом, вопреки иллюзиям наука реально может пользоваться в вычислениях не более чем плотным множеством вычислимых чисел с нулевой сложностью [вида (6)]. Парадоксально, что хотя это плотное множество вычислимых чисел имеет меру, равную нулю, оно, как легко доказать, несчётно.

НАСКОЛЬКО СЛУЧАЕН ИСХОД БРОСАНИЯ МОНЕТЫ?

Рассмотрим теперь конкретный пример. Идеальная, детерминированная игра «орёл или решка» очень хорошо описывается разностным уравнением (3). При заданном X0 мы можем детерминированно вычислять последовательные значения Xn и тем самым определять, получим ли мы 1 или 0 (орёл или решку), по первой двоичной цифре каждого результата итерации Xn. Такой процесс строго детерминирован. Для него нетрудно доказать теоремы существования и единственности. В то же время этот процесс полностью случаен, потому что строки цифр почти для всех X0 случайны. Как же такое может быть? Разве это не противоположные понятия? Разве полная детерминированность и полная случайность не исключают друг друга?

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

Несмотря на широко распространённое убеждение в обратном, «монета», описываемая уравнением (3), предстаёт как полностью случайная, но разве можно считать, что тем самым детерминированность полностью исключена? Разумеется, нет, поскольку традиционные представления теории вероятностей содержат столь же широкие неявные допущения, как и традиционные представления о детерминированности. В частности, представление о том, что случайность не оставляет места для детерминированности, основано на предположении о невозможности бесконечной точности наблюдений или вычислений. Если же предположить, что наблюдатель и вычислитель бесконечно искусны, то уравнение (3) даёт детерминированную схему вычисления случайного процесса выпадения орла и решки. Исторически в детерминистских теориях не было осознано, что расчёт случайной траектории становится возможным благодаря неявному допущению бесконечной точности, так же как в вероятностных теориях не было осознано, что бесконечная точность может служить связующим звеном с детерминированностью. К вопросу, о том, имеет ли бесконечная точность физический смысл, мы вернёмся несколько позже.

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

где b — иррациональное число. Решение этого уравнения имеет вид

Известно (т.е. строго доказано), что в силу иррациональности числа b результаты итерации X0, даваемые формулой (7), плотны и равномерно распределены на единичном интервале. И даже этот самый слабый и неслучайный вариант «хаоса», получивший название эргодичности [3, 4], отнюдь не зависит от какой бы то ни было случайности в строке цифр числа X0. Действительно, предположим, что в начальное значение X0 вкралась малая ошибка ΔX0. Тогда из уравнения (8) мы сразу же находим, что ΔXn = ΔX0, т.е. ошибка не возрастает с увеличением числа итераций. Уравнение (7) отображает конечные интервалы целиком, как жёсткие единицы, а поэтому ясно, что наличие или отсутствие случайности в числовой записи внутренней точки X0 несущественно для дальнейшей истории траектории. Важно, что в полностью хаотических, случайных системах ошибка нарастает экспоненциально. Именно поэтому траектории такой системы весьма чувствительны к точности задания начального состояния и его случайному характеру. В нехаотических же системах ошибка нарастает не так быстро и, как уже отмечалось, для точного определения грубозернистого будущего достаточно грубозернистого прошлого. Итак, хаотическая траектория случайна и невычислима, содержащаяся в ней информация бесконечна и несокращаема. Чтобы получить хаотическую траекторию, мы можем ввести необходимую бесконечную информацию либо в начальное состояние X0, либо в разностное уравнение, задающее алгоритм, либо в то и другое. Какой способ выбрать — это дело вкуса.

СЛЕДСТВИЯ

Почти во всех физических теориях (в том числе и в квантовой механике) рассматриваются уравнения для скоростей изменения непрерывных переменных. Приверженцы таких теорий стоят за континуум, упирая на то, что для любой переменной, взятой в отдельности, в принципе нет никаких пределов точности измерения. Тем не менее даже самые верные защитники континуума не берутся утверждать, что точность наших наблюдений когда-либо сможет стать бесконечной. Но без бесконечной точности континуум, как показывает теория сложности, утрачивает смысл, если подходить к нему с физических позиций. И это не просто небольшое замечание педагогического или математического характера. Если говорить о физическом эксперименте, то в нехаотической системе ошибка наблюдения возрастает медленно, т.е. начальная ошибка при последующих наблюдениях умножается на некоторую степень времени t, и потому такие системы обычно позволяют нам придерживаться фикций детерминированности и континуума, по крайней мере в лабораторных масштабах времени. К сожалению, нехаотические системы почти столь же редкая вещь, как птичье молоко, хотя наше физическое понимание природы и опирается в основном на их изучение. В хаотических же системах, распространённых гораздо шире и составляющих подавляющее большинство систем, ошибки наблюдений возрастают, как правило, экспоненциально быстро и детерминированность и континуум утрачивают смысл даже во впечатляюще коротких временных масштабах человека. Например, если ошибка в величине X0 в уравнении (3) равна 10–31, то детерминированность полностью исчезает приблизительно к сотой итерации.

Какие следствия вытекают из всего сказанного? Не даст ли нам теория сложности алгоритмов вешки для разметки дороги в будущее?

За три столетия ньютоновская динамика дважды спотыкалась о допущения бесконечности того, что на самом деле не было бесконечным: скорости света c и величины, обратной постоянной Планка h, т.е. 1/h. Стремление избавиться от этих бесконечностей привело сначала к созданию специальной теории относительности, а затем — к созданию квантовой механики. Теория сложности алгоритмов вскрыла третье неявное допущение бесконечности: на этот раз — бесконечной точности наблюдений и вычислений. Вследствие этого ньютоновская динамика сейчас стоит перед необходимостью третьего пересмотра, влияние которого на науку может по значимости не уступать двум предыдущим. Кроме того, и квантовая механика, сама появившаяся в результате второй революции, не останется в стороне от грядущей третьей революции, поскольку в квантовой механике тоже делается предположение о бесконечной точности измерений и вычислений. Как мы сейчас видим, Эйнштейн был прав и квантовая механика неполна. Ибо, если приверженцы квантовой механики располагают бесконечной точностью, необходимой для вычисления точной эволюции во времени непрерывных переменных, то они должны вычислить по-детерминистски все случайные переменные в своей теории. Отказ же от бесконечной точности требует пересмотра квантовой механики, не уступающего по масштабам пересмотру классической динамики.

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

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

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

∞ = (1 + 1 + 1 + ...)

и бесконечно малую

0 = (1 + 1 + 1 + ...)–1.

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

Давным-давно, ещё до начала времени, боги даровали человеку число 1, чтобы ему было чем поразвлечься на досуге. Человеку так понравилось число 1, что он нашёл ему пару и назвал новое число 2, а затем ещё одно число, которое назвал 3. В один из следующих дней, когда человек созерцал истину и красоту числа N, его подруга принесла ему соблазнительный плод, который дал ей змей, назвавший свой дар алевом. Стоило человеку вкусить плода, как ему ударило в голову, и ум его, воспарив, на мгновенье постиг смысл суммы (1+1+1+...), но к утру он не помнил ничего, кроме пустых символов ...

Мораль: не тщись объять необъятное.

Благодарность — в СССР. Эта статья — конечный результат многих разъяснений, советов и замечаний, которыми щедро делился с автором его друг и коллега проф. Б. В. Чириков из СССР. Все комплименты надлежит адресовать именно ему. Критические замечания просьба направлять в Атланту.

Примечания

Joseph Ford. "How random is a coin toss?" — Physics Today, April 1983, p. 40–47. Перевод с английского Ю.А. Данилова. назад к тексту

1. См. ясный, очень хорошо написанный обзор [1]. назад к тексту

2. На этот заговор молчания сетовал также Уайтман [2]. назад к тексту

3. Помимо работ [1–4] см. также библиографию, составленную Хеллеманом [6]. назад к тексту

4. Элементы последовательности номеров не обязательно должны быть статистически независимы, хотя у читателя, возможно, создалось обратное впечатление. (См. статью Мартин-Лёфа [8].) назад к тексту

5. Наше определение невычислимого числа не совпадает с определением, принятым у специалистов по теории вычислительных машин, но не очень сильно от него отличается. назад к тексту

6. В полуофициальных беседах в кулуарах различных конференций. назад к тексту

7. Читатели, питающие склонность к истории, возможно, обратили внимание на множество параллелей между моей статьёй и многочисленными статьями, опубликованными ранее — по крайней мере до времён Максвелла. Но самую полную и разительную параллель можно усмотреть между моей статьёй и статьёй М. Борна «Является ли классическая механика действительно детерминистской?» [9]. назад к тексту

Список литературы

1. Moser J., Memoirs Amer. Math. Soc., No. 81 (1968).

2. Wightman A.S., in: Perspectives in Statistical Physics (ed. H.J. Raveche), North-Holland, Amsterdam, 1981.

3. Lebowitz J.L., Penrose O., Physics Today, February 1973, p. 23.

4. Berry M., in: Topics in Nonlinear Dynamics (ed. S. Jorna), A.I.P. Conf. Proc, 46, 16 (1978).

5. Henon M., Heiles C., Astron. Journ., 69, 73 (1964).

6. Helleman R.G.H., in: Fundamental Problems in Statistical Physics, v. 5 (ed. E.G.D. Cohen), North-Holland, Amsterdam, 1980.

7. Брудно A.A. — Успехи мат. наук, 1978, т. 33, с. 207.

8. Chaitin G.J., Sci. Amer., May 1975, p. 47; Звонкин А.К., Левин Л.А. — Успехи мат. наук, 1970, т. 25, с. 85; Martin-Löf P., Journ. Information and Control, 9, 602 (1966); Alekseev V.M., Yakobson M.V., Phys. Repts., 75, 287 (1981).

9. Born M., Physics In My Generation, Springer-Verlag, New York, 1969, p. 78. [Имеется перевод: Борн М. Физика в жизни моего поколения. — М.: ИЛ, 1963, с. 285.]