плюс 01010101010 и все последовательности с девятью или более нулями, плюс все последовательности, полученные из предшествующих последовательностей, если единицы и нули поменять местами.

Подобным образом можно сформулировать определение, аналогичное определению R6, для конечной последовательности. Пусть А - множество алгоритмов, каждый из которых является процедурой выделения и выбора, дающей подпоследовательность {Xs„)TZ, как в доказательстве теоремы М.

Определение Q2. Ь-ичная последовательность Хо, Xi, Xn-i является {п,е)-случайной относительно множества алгоритмов А, если для каждой подпоследовательности Xti, Xt2, , Xt, определенной алгоритмом А, мы имеем либо т <п, либо

-ta{Xti,- ,Xt) - -m о

< б для О < а <Ь.

Здесь j/o(xi,..., Хт) - количество чисел а в последовательности xi, ..., Хт-

(Другими словами, каждая достаточно длинная подпоследовательность, определенная алгоритмом из множества А, должна быть приближенно равнораспределенной.) Основной идеей в этом случае является предположение, что А - множество "простых" алгоритмов и количество (и сложность) алгоритмов в А может увеличиваться при росте N.

В качестве примера определения Q2 рассмотрим двоичную последовательность. Пусть А состоит из следующих четырех алгоритмов.

a) Взять всю последовательность.

b) Взять нечетные члены последовательности, начиная с первого.

c) Взять члены последовательности, следующие за нулем.

d) Взять члены последовательности, следующие за единицей.

Сейчас последовательность Хо, Xi, Ху является (4, )-случайной относительно А, если:

по (а)

по (Ь)

g(Xo -Ь Xl -I-----1- Ху) - I < g, т. е. если последовательность содержит 3, 4

или 5 единиц;

\{Хо -\- Х2 -\- Xi -\- Хб) - II < gi т. е. если последовательность содержит точно 2 единицы на четной позиции;

по (с) существуют три возможности в зависимости от того, как много нулей занимают позиции Хо, Хе: если здесь 2 или 3 нуля, то нет необходимости в проверке (так как п = 4); если 4 нуля, то за ними должны следовать 2 нуля и 2 единицы; если 5 нулей, то за ними должны следовать 2 единицы и 3 нуля;

по (d) мы получим условия, подобные условиям в (с).

Оказывается, что только следующие двоичные последовательности длины 8 являются (4, )-случайными в соответствии с этими правилами,

00001011 00101001 01001110 01101000

00011010 00101100 01011011 01101100

00011011 00110010 01011110 01101101 00100011 00110011 01100010 01110010

00100110 00110110 01100011 01110110

00100111 00111001 01100110

плюс те, которые получены из этих, если единицы и нули поменять местами.

Ясно, что множество алгоритмов можно сделать таким большим, что не будет последовательностей, не удовлетворяющих определению, когда п и е малы. А. Н. Колмогоров доказал, что (п, €)-случайная двоичная последовательность всегда будет существовать для любого заданного Л, если число алгоритмов в А не превышает

ie2-(i-). (37)

Этот результат не достаточно строгий, чтобы показать, что последовательности, удовлетворяющие определению Q1, существуют, но последние могут быть эффективно построены с использованием процедуры Риса (Rees) из упр. 3.2.2-21. Обобщенный спектральный критерий, основанный на дискретном преобразовании Фурье, можно использовать для проверки, насколько последовательность соответствует определению Q1 [см. А. Compagner, РЬу81ся1 Rev. Е52 (1995), 5634-5645].

Другие интересные подходы к определению случайности приведены Пером Мар-тин-Лёфом (Per Martin-Lof, Information and Control 9 (1966), 602-619). Пусть задана конечная Ь-ичная последовательность Al, Хг, (Xi,..., АГдт) - длина самой короткой программы Тьюринга, которая генерирует эту последовательность. (Вместо этого можно использовать другие классы эффективных алгоритмов, например такие, которые обсуждались в разделе 1.1.) Тогда /(ATi,..., АГдт) - мера "хаотичности" последовательности и это понятие можно отождествить со случайностью. Последовательности длины N, максимизирующие /(ATi,..., Адг), можно называть случайными. (С практической точки зрения генерирование случайного числа компьютером - это, конечно, наихудшее определение "случайности", какое можно себе представить!)

По существу, почти в то же время такое определение случайности независимо предложил Г. Чайтин (G. Chaitin, JACM 16 (1969), 145-159.) Интересно отметить, что хотя в данных определениях не упоминается о свойствах равнораспределенности, как в наших определениях, Мартин-Лёф и Чайтин доказали, что случайные последовательности этого вида также имеют ожидаемые свойства равнораспределенности. На самом деле Мартин-Лёф продемонстрировал, что такие последовательности удовлетворяют всем вычислимым статистическим критериям случайности в соответствующем смысле.

Дополнительную информацию об определении случайной конечной последовательности можно найти в следующих работах: Звонкий А. К. и Левин Л. А. Успехи маг. наук 25,6 (Ноябрь, 1970), 85-127; Левин Л. А. Докл. Акад. наук СССР 212 (1973), 548-550; Левин Л. А. Информация и контроль 61 (1984), 15-37.

F. Псевдослучайные числа. С теоретической точки зрения утешительно знать, что существуют случайные конечные последовательности с разными особенностями, но такие теоремы не дают ответов на вопросы, с которыми сталкиваются в действительности программисты. Недавние исследования привели к более практичной теории, основанной на изучении множеств конечных последовательностей. Точнее, рассмотрим мультимножества, в которых последовательности могут появляться более одного раза.

Пусть S - мультимножество, содержащее двоичные строки длины N; назовем S N-источником. Пусть означает определенный Л-источник, содержащий все 2- возможных Л-двоичных строк. Каждый элемент S представляет последовательность, которую можно использовать в качестве источника псевдослучайных двоичных разрядов, выбор различных "начальных" значений приводит к различным элементам S. Например, возможно такое множество S

{В1В2... Bjf I Bj старший значащий двоичный разряд Xj} (38)

в линейной конгруэнтной последовательности, определенной равенством Xj+i = {aXj -\- с) mod 2, в котором существует одна строка В1В2 . .Bs для каждого из 2 начальных значений Xq.

Основной идеей псевдослучайных последовательностей, как будет показано в этой главе, является получение двоичных разрядов, появляющихся случайно, несмотря на то что мы используем лишь несколько "истинно случайных" двоичных разрядов, когда выбираем начальное значение. В только что рассмотренном примере понадобилось е истинно случайных двоичных разрядов для выбора Aq. Вообще, для использования отбирается Ig 5 из 5 истинно случайных двоичных разрядов, после чего процедура становится детерминированной. Если = 10 и 5 = 2, получаем более 30 ООО "кажущихся случайными" двоичных разрядов из выбранного истинно случайного двоичного разряда. При $лг вместо 5 мы не получим такого большого числа "случайных разрядов", поскольку lg$Af = N.

Что означает "кажущихся случайными"? Э. Ч. Яо (А. С. Yao) в 1982 году предложил хорошее определение: рассмотрим любой алгоритм А, который при применении к строке двоичных разрядов В = Bi... В выдает значение А{В) - О или 1. Можно рассматривать А как критерий случайности, например алгоритм А может вычислить распределение серий последовательных нулей и единиц, выдавая на выходе единицу, если длины серий значительно отличаются для ожидаемого распределения. Что бы ни делал А, вероятность P(A,S) можно рассматривать как вероятность того, что А{В) = 1, когда В - случайно выбранный элемент из 5, и можно сравнивать с вероятностью Р{А,$г) того, что А{В) = 1, когда В - истинно случайная строка двоичных разрядов длины N. Если Р{А, S) будет очень близким к Р{А, $лг) для всех статистических критериев А, то мы ничего не сможем сказать о различии между последовательностями S и истинно случайными двоичными последовательностями.

Определение Р. Мы говорим, что N-источник S проходит статистический критерий А с допустимым отклонением е, если \P{A,S) - Р{А,$)\ < е. Критерий "проваливается", если Р{А, S) - Р{А, Sr) >е.