Изложенные соображения относятся к весьма разработанной теории 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 сложность бесконечной последовательности как
(6) | Хотя при таком определении возникают кое-какие трудности со сходимостью, можно доказать, что в общем случае такой предел существует. Нестрого мы иногда будем употреблять выражение «максимально сложная» в применении к бесконечной последовательности, сложность K которой, вычисленная по формуле (6), отлична от нуля. Как и прежде, максимально сложную последовательность будем считать случайной. Преимущество такого определения состоит в том, что оно отвечает нашим интуитивным представлениям. Бесконечные максимально сложные последовательности настолько непредсказуемы, что их нельзя вычислить с помощью какого-либо конечного алгоритма; задать такую последовательность можно, только предъявив её копию. Нельзя не отметить и недостаток такого определения: из него не видно, что оно полностью эквивалентно принятым ранее определениям случайности. Попытаемся восполнить этот пробел. Ниже, говоря о последовательностях, я всегда буду иметь в виду бесконечные последовательности.
«Вычислимый критерий» — это критерий, представимый конечным алгоритмом. Так как случайность означает в том или ином смысле отсутствие порядка, а встречающийся в природе беспорядок бесконечно разнообразен, не существует единого вычислимого критерия, который позволял бы строго доказать, что интересующая нас последовательность случайна. Отдельные вычислимые критерии — это необходимые, но недостаточные критерии случайности. Но можно объединить все возможные вычислимые критерии в один сложный критерий и определять, удовлетворяет ли некоторая последовательность всем критериям случайности, вычисление которых посильно для человека. Назовём такой критерий «универсальным критерием случайности». Теперь известно, что почти все максимально сложные последовательности удовлетворяют универсальному критерию случайности. Эта теорема, доказанная Мартин-Лёфом в 1966 г., служит оправданием для нашего определения случайной последовательности как максимально сложной последовательности, поскольку ни один человек не сможет отличить новое определение от нашего старого. Наконец, Мартин-Лёф доказал, что почти все последовательности — максимально сложные и, следовательно, случайные. Из этого доказательства непосредственно следует, что почти все отдельные траектории уравнения (3) не только строго детерминированны, но и полностью случайны — вывод, который подробнее обсудим ниже.
Возвращаясь к гамильтоновой динамике, напомним, что хаотическая траектория по определению даёт последовательность номеров ячеек, будущее которой не определяется её прошлым. Очевидно, что хаотическая траектория даёт максимально сложную последовательность номеров 4. Таким образом, хаотическая орбита сама полностью случайна в том смысле, что её нельзя вычислить с помощью какого-либо конечного алгоритма, а содержащаяся в ней информация бесконечна и неуплотняема. Наконец, для хаотических траекторий ньютоновская динамика должна детерминированно вычислять случайные последовательности номеров ячеек. Но тогда законы Ньютона представляют собой не что иное, как формальные алгоритмы, превосходящие возможности человека-вычислителя. На протяжении столетий случайность имела права гражданства в детерминистской Вселенной лишь как нечто вспомогательное, ей отводилась лишь подсобная роль. Теория сложности алгоритмов и нелинейная динамика совместными усилиями установили, что в действительности детерминированность безраздельно господствует только в конечной области; за пределами же крохотного оазиса порядка лежат почти не нанесённые на карту бескрайние просторы хаоса, где эфемерная память о детерминированности сохраняется лишь в теоремах существования, а выживает только случайность.
В качестве дополнительного следствия из теории сложности алгоритмов отметим одно довольно удивительное обстоятельство: числа π и e не дают случайных строк цифр, так как их оба можно вычислять путём бесконечного повторения коротких алгоритмов, а это означает, что величина K [формула (6)] равна нулю. Кроме того, если мы назовём невычислимым 5 число с максимально сложной строкой двоичных цифр, то почти все действительные числа окажутся невычислимыми — их нельзя вычислить с помощью какого-либо конечного алгоритма. Как говорит М. Кац 6, почти все числа в континууме невозможно определить конечным числом слов. Следовательно, континуум обладает той отличительной особенностью, что представляет собой вполне определённое множество по большей части неопределённых объектов. Таким образом, вопреки иллюзиям наука реально может пользоваться в вычислениях не более чем плотным множеством вычислимых чисел с нулевой сложностью [вида (6)]. Парадоксально, что хотя это плотное множество вычислимых чисел имеет меру, равную нулю, оно, как легко доказать, несчётно.