Случайность по Ламберту и по Колмогорову
Мир случайностей на самом деле оказался устроен хитрее, чем он выглядит в алгоритмической ТВ, о которой шла речь в главе 2. Бесконечную непериодическую (т.е. случайную по Ламберту) последовательность легко получить самым простым алгоритмом – например, извлекая квадратный корень. Налицо парадокс: алгоритмически неслучайное оказывается случайным статистически.
Неужели никто из авторов алгоритмической ТВ этого не заметил? Нет, конечно заметили и провели соответствующее исследование, итог которого изложил почти популярно немецкий математик Конрад Якобс [1972].
Случайность по Ламберту означает всего лишь отсутствие периодичности в последовательности знаков числа, что не исключает квази-периодичности (наличия длинных закономерных участков, достаточно регулярно повторяющихся). Так вот, все числа, полученные с помощью алгоритмов, либо периодичны, либо квази-периодичны, тогда как числа, подлинно случайные по Колмогорову – Мартин-Лёфу, невычислимы.
Встает вопрос: каких чисел больше? Мартин-Лёф [1975, c. 117–120] дал ответ – вычислимые (конструктивные) числа являют нулевую часть вещественных (на отрезке [0, 1] покрываются отрезками бесконечно малой суммарной длины). Наоборот, типичны числа со случайным чередованием знаков или, другими словами, хаотичность по Колмогорову эквивалентна типичности по Мартин-Лёфу [Шень, 1992, c. 126].
Алгоритмическая ТВ разработана в 1960-е годы, а в 1980-е наступило разочарование. Как писал теоретик статистики Ю.П. Адлер, подход Колмогорова – Мартин-Лёфа приводит "к критериям случайности, бракующим практически все известные генераторы (случайных чисел – Ю.Ч.), что, впрочем, неудивительно" [Иванова, 1984, c. 7]. Встал вопрос о пользе такого подхода. Установилось мнение, что "абсолютное определение случайности (randomness), которое представляется осуществлением главной цели фон Мизеса", Колмогоровым и Мартин-Лёфом в принципе достигнуто, но их результат "настолько неэффективен... что конкретное использование последовательностей, случайных по Мартин-Лёфу, невозможно" [Philosophy..., 1993, с. 145, 160].
|
|
|
В частности, число "пи", вычисленное до 100 тыс. знаков, оказалось (в отличие даже от числа "е") вполне случайным с точки зрения всех использованных статистических критериев [Иванова, 1984, c. 30], а ведь оно вычисляется алгоритмически. Новый мощный компьютер дал совсем поразительный результат: число "пи" вполне случайно до 134 млн знаков [Шрёдер, 2001, c. 336-337]. Иными словами, конструктивизм попался в ту же ловушку, которую сам заметил у оппонентов и которой хотел избежать: "эффективная вычислимость" оказалась столь же абстрактна и далека от практической применимости, как и принципиальное существование, доказанное неэффективно, негативно (сведением к противоречию).
|
|
|
И школе Колмогорова вскоре пришлось признать, что случайность по Колмогорову – лишь частный случай практически интересной случайности: "Вообще говоря, некоторый объект может рассматриваться как алгоритмически случайный, поскольку:
а) он не имеет никакого короткого описания;
б) он имеет короткое описание, но процедура восстановления... требует огромных вычислительных ресурсов;
в) он имеет короткое описание, по которому быстро восстанавливается, но описание это нам неизвестно" [Шень, 1992, c. 130].
Добавлю, что сомнительна сама идея называть случайным конечный ряд знаков, который нельзя описать короче, нежели записав сам ряд — многие закономерности короче записать, чем описать. Например: ряд номеров дней (считая с начала года) двунадесятых праздников православной церкви.
Однако общий итог развития алгоритмической ТВ вполне положителен, как для самой ТВ, так и для алеатики в целом. Кроме отмеченной в главе 2 стохастичности неалгоритмической случайности, отмечу принципиальный характер факта эквивалентности хаотичности по Комогорову и типичности по Мартин-Лёфу – типичными оказались неалгоритмические (невычислимые) числа. Этот факт представляется мне тесно связанным с упомянутой в начале главы типичностью хаотичеcких траекторий.
|
|
|
Открытие динамического хаоса показало, как случайность возникает в неслучайной системе, а алгоритмическая ТВ открыла, что случайность лежит в основе чисел, которыми мы пользуемся, и что они случайны в разной мере. Далее, важное свойство чисел состоит в том, что почти каждое содержит бездонную кладезь информации.
Целая кладезь информации содержится в числе независимо от того, существует ли алгоритм для его вычисления и умеем ли мы сегодня его вычислять. Могут спросить: при чем тогда вообще алгоритмы? На это можно ответить, что они многое объясняют. Во-первых, алгоритм реализует ту информацию, на которое определение числа (например: число "пи" есть отношение длины окружности к диаметру) лишь указывает. Во-вторых, алгоритмы дают лишь псевдослучайность. Правда, иногда, как у числа "пи", она оказывается очень высокого качества (не удается найти закономерности), и причина этого пока неясна, но пониманием того факта, что в целом случайность по Ламберту – не вполне случайность в статистическом смысле, мы обязаны алгоритмической ТВ. А в-третьих, все наши теории только к алгоритмически вычислимым числам и относятся.
|
|
|
Иногда говорят, что в достаточно длинной последовательности знаков числа "пи" можно найти всё что угодно, вплоть до поэм Гомера (если читать ее как закодированный буквенный текст), но это неверно. Из того, что здесь возможно любое сочетание знаков, не следует, что оно тут в самом деле есть. Другое дело – неконструктивное (невычислимое) число: если знаки его действительно следуют независимо друг от друга, как исходы бросания монеты, то любая последовательность обязана встретиться. Гугол (10100) знаков вполне достаточен чтобы ожидать встретить данную строфу из Гомера, но нет никакой возможности ее реально встретить, поскольку рассматриваемое число невычислимо – по крайней мере до тех пор, пока действует нынешнее понимание вычислимости. Даже имея ЭВМ, способную выдать гугол случайных знаков, мы не смогли бы сказать, какое при этом число вычисляем.
Дата добавления: 2019-02-22; просмотров: 277; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!