вычисления, необходимое для определения статистического смещения, возрастает до 53.5 тераМ1Р-лет.

Простой псевдослучайный генератор 3.2.2-(16), который избегает случайной маски Z, что также можно показать, проходит все полиномиальные критерии случайности, если разложение на множители трудно осуществить (см. упр. 4.5.4-43). Но известные преобразования гарантируют для методов, которые отчасти слабее смешанно-квадратичного метода, порядок роста 0{N*R€~*log{NR€~)) по сравнению с 0{NRe~) теоремы Р.

Каждый думает, что не существует алгоритма разложения на множители для чисел, состоящих из R двоичных разрядов, время счета которых равно полиному в степени R. Если это предположение верно в строгом виде, то нельзя будет получить даже 1 /R для целого числа Блюма, состоящего из R двоичных разрядов, за полиномиальное время для любого фиксированного к. Теорема Р доказывает, что смешанно-квадратичный метод генерирует псевдослучайные числа, проходящие все полиномиальные критерии случайности.

Сформулируем это другим способом: если генерировать случайные двоичные разряды смешанно-квадратичным методом для подходящим образом выбранных N и R, можно также получить числа, проходящие все разумные статистические критерии, или открыть новый алгоритм разложения на множители.

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

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

Понятие "оо-распределение 6-ичной последовательности" было введено в 1909 году Эмилем Борелем (Emile Borel). Он, по существу, ввел понятие (т,/с)-рас-пределенной последовательности и показал, что Ь-ичное представление почти всех действительных чисел является (т,/с)-распределенным для всех тик. Борель назвал такие числа нормальными по отношению к основанию Ь. Превосходное обсуждение этой темы появилось в его хорошо известной книге Legons sur la Theorie des Fonctions, 2nd edition (1914), 182-216.

Понятие оо-распределенной последовательности действительных чисел, также носящее название полностью равнораспределенной последовательности, впервые появилось в заметке Н. М. Коробова {Доклады Акад. Наук СССР 62 (1948), 21-22). Коробов и несколько его коллег достаточно широко развили теорию таких последовательностей в ряде статей в течение 50-х годов. Полностью равно-распределенные последовательности независимо изучались Джоэлем Н. Франкли-ным (Joel N. Franklin, Math. Сотр. 17 (1963), 28-59) в статье, которая особенно заслуживает внимания, так как она была вдохновлена проблемой генерирования случайных чисел. Книга L. Kuipers and Н. Niederreiter, Uniform Distribution of Sequences (New York: Wiley, 1974) является чрезвычайно полным источником информации об огромной математической литературе, содержащей -распределенные последовательности всех видов.

Тем не менее мы увидели, что оо-распределенные последовательности не обладают достаточным количеством свойств, чтобы их можно было считать совершенно "случайными". Определения R4-R6, приведенные выше, предусматривают дополнительные условия; в частности, определение R6, видимо, было подходящим способом определения понятия бесконечной случайной последовательности. Это точное количественное утверждение, хорошо совпадающее с интуитивным понятием истинной случайности.

Исторически развитие этих определений было стимулировано, главным образом, поисками Р. фон Мизесом (R. von Mises) хорошего определения вероятности. В Math. Zeitsdirift 5 (1919), 52-99, фон Мизес предложил определение, по духу сходное с определением R5, хотя формулировка была слишком строга (подобно нашему определению R3), так что последовательностей, удовлетворяющих этим условиям, не существует. Многие исследователи отмечали это противоречие, и А. Г. Коуплэнд (А. Н. Copeland, Amer. J. Math. 50 (1928), 535-552) предлагал ослабить определение фон Мизеса заменой, которую он назвал допустимыми числами (или последовательностями Бернулли). Существует эквивалент оо-распределенных [О.. 1)-последовательностей, в которых все входные f/„ заменяются 1, если Un <Р или О и если Un > р для заданной вероятности р. Так, Коуплэнд, по существу, предложил вернуться к определению R1. Затем Абрахам Вальд (Abraham Wald) показал, что нет необходимости так решительно ослаблять определение фон Мизеса, и предложил заменить счетное множество правилами подпоследовательностей. В важной статье Ergebnisse eines math. Kolloquiums 8 (Vienna, 1937), 38-72, Вальд, по существу, доказал теорему W, хотя он сделал ошибочный вьшод, что последовательность, построенная алгоритмом W, также удовлетворяет сильным условиям - Рг({/„ € Л) = мера А для всех измеримых по Лебегу Л С [0.. 1). Заметим, что не существует последовательности, которая может удовлетворять этому условию.

Понятие "вычисляемость" играло большую роль на ранней стадии, когда Вальд написал статью и А. Черч (А. Church, Bull Amer. Math. Soc. 46 (1940), 130-135) показал, как точное понятие "эффективный алгоритм" можно присоединить к теории Вальда, делая его определение совершенно строгим. Практически тогда же дополнение к определению R6 было предложено А. Н. Колмогоровым [Sankhya А25 (1963), S69-376], как и определение Q2 для конечных последовательностей. Другое определение случайности для конечных последовательностей, находящееся где-то между определениями Q1 и Q2, намного раньше сформулировал А. С. Безикович (А. S. Besicovitch, Math. Zeitschrift 39 (1934), 146-156).

В публикациях Черча и Колмогорова рассматривались только двоичные последовательности, для которых Рг(А„ =. 1) = рс заданной вероятностью р. В этом разделе анализировалась более общая ситуация, поскольку [О.. 1)-последовательность, по существу, представляет все р сразу. Определение фон Мизеса-Вальда-Черча еще одним интересным способо.м усовершенствовал Дж. В. Говард (J. V. Howard, Zeitschr. fur math. Logik and Grundlagen der Math. 21 (1975), 215-224).

Следующий важный вклад был сделан Дональдом В. Лавлендом (Donald W. Loveland, Zeitschr. fit math. Logik und Grundlagen der Math. 12 (1966), 279-294), который обсудил определения R4-R6 и несколько других понятий. Лавленд доказал, что существуют R5-cлyчaйныe последовательности, не удовлетворяющие определению R4. В связи с этим он установил, что необходимо более строгое определение.

такое как R6. На самом деле Лавленд определил простую перестановку (/(п)) неотрицательных целых чисел и алгоритм W, сходный с алгоритмом W, такой, что

P?(f (n)>)-Pr(f (n)>)>

ДЛЯ каждой КЗ-случайной последовательности (f/„), выдаваемой алгоритмом W, когда он задан бесконечным множеством правил подпоследовательностей TZk

Хотя определение R6 интуитивно строже определения R4, очевидно, строго доказать это совсем не просто. В течение нескольких лет данный вопрос оставался открытым, поскольку R4 так или иначе включает в себя R6. В конце концов, Томас Герцог (Thomas Herzog) и Джеймс К. Оуингс (мл.) (James С. Owings, Jr.) сумели построить большое семейство последовательностей, удовлетворяющих R4, но не удовлетворяющих R6. [См. Zeitschr. fur math. Logik und Grundlagen der Math. 22 (1976), 385-389.]

Другую важную статью написал Колмогоров [Проблемы передачи информации 1 (1965), 3-11]. В ней он рассмотрел проблему определения "информационного содержимого" последовательности, и эта работа привела к интересному определению Чайтина (Chaitin) и Мартин-Лёфа (Martin-Lof) конечных случайных последовательностей через "хаотичность". [См. IEEE Trans. IT-14 (1968), 662-664.] Их идея может быть также прослежена в работах Р. Дж. Соломонова (R. J. Solomonoflf, Information and Control 7 (1964), 1-22, 224-254; IEEE Trans. IT-24 (1978), 422-432; J. Сотр. System Sci. 55 (1997), 73-88).

Обсуждение случайных последовательностей с философской точки зрения можно найти у К. Р. Поппера (К. R. Popper, The Logic of Scientific Discovery (London. 1959)); особенно интересно построение на с. 162-163, впервые опубликованное в 1934 году.

Дальнейшие связи между случайными последовательностями и теорией рекурсивных функций исследовались в работе D. W. Loveland, Trans. Amer. Math. Soc. 125 (1966), 497-510. См. также работу К.-П. Шнорр (С.-Р. Schnorr, Zeitschr. Wahr. verw. Geb. 14 (1969), 27-35), нашедшего сильные связи между случайными последовательностями и "категориями меры", которые были определены Л. Э. Я. Бро-уэром (L. Е. J. Brouwer) в 1919 году. В след>-ющей книге Шнорра, Zufalligkeit und Wahrscheinlichkeit [Lecture Notes in Math. 218 (Berhn: Springer, 1971)], дан подробный обзор всей темы случайности и превосходное вступление к новым публикациям по этой теме. Обзор важнейших усовершенствований в течение следующих двух десятилетий можно найти в книге An Introduction to Kolmogorov Complexity and Its Applications (Springer, 1993), Ming Li and Paul M. B. Vitanyi.

Основы теории псевдослучайных последовательностей и эффективной информации заложены Мануэлем Блюмом (Manuel Blum), Сильвио Микали (Silvio MicaH) и Эндре Яо (Andrew Yao) в работах [EOCS 23 (1982), 80-91, 112-117; SICOMP 13 (1984), 850-864], в которых построены первые явные последовательности, удовлетворяющие всем возможным статистическим критериям. Блюм и Микали ввели понятие жесткого ядра двоичного разряда, булевой функции /, такой, что f{x) и д{х) легко вычисляются, хотя функция f[g~\x)) не вычисляется. В их статье берет начало лемма Р4. Леонид Левин развил теорию в работе Combinatorica 7 (1987), 357-363. Затем он и Одед Голдрейч (Oded Goldreich) [STOC 21 (1989), 25-32] проанализировали такие алгоритмы, как смешанно-квадратичный метод, и