некоторую последовательность TZi, Tl, ] таким образом, алгоритм W задает [О.. 1)-последовательность, случайную в смысле определения R5.

Это приводит к возникновению в некоторой степени парадоксальной ситуации. Как уже упоминалось, не существует эффективного алгоритма для задания последовательности, удовлетворяющей определению R4. По тем же соображениям неэффективен алгоритм, который задает последовательность, удовлетворяющую определению R5. Доказательство существования такой случайной последовательности неизбежно неконструктивно. Как тогда алгоритм W может построить такую последовательность?

Здесь нет противоречия, есть только заминка, связанная с тем фактом, что множество всех эффективных алгоритмов не может быть пронумеровано эффективным алгоритмом. Другими словами, не существует эффективного алгоритма выбора j-ro исчислимого правила подпоследовательности 11 j, поскольку нет эффективного алгоритма определения того, заканчивается ли данный вычислительный метод. Но важные большие классы алгоритмов можно систематически перенумеровывать. Так, например, в алгоритме W показано, что с помощью эффективного алгоритма можно построить последовательность, удовлетворяющую определению R5, если ограничиться рассмотрением "примитивных рекуррентных" правил подпоследовательностей.

Преобразовав шаг W6 алгоритма W (присвоив f/„ 4- Vjt+t вместо Vk, где t - любое неотрицательное целое число, зависящее от а\, Ог), можно показать, что существует несчетное множество [О.. 1)-последовательностей, удовлетворяющих определению R5.

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

Теорема М. Пусть действительное число х, О < х < 1, соответствует двоичной последовательности {Хп), если {O.XqXi ... )2 является двоичным представлением х. При этом почти все х соответствуют случайным в смысле определения R6 последовательностям. (Другим словами, множество всех действительных чисел х, соответствующих неслучайным по определению R6 двоичным последовательностям, имеет меру нуль.)

Доказательство. Пусть S - эффективный алгоритм, определяющий бесконечную последовательность различных неотрицательных чисел (s„), где выбор s„ зависит только от n и Xs для О < /с < п, и пусть TZ - исчислимое правило подпоследовательности. Тогда любая двоичная последовательность (Х„) приводит к подпоследовательности {Xs„)TZ и по определению R6 эта подпоследовательность должна быть либо конечной, либо 1-распределенной. Достаточно доказать, что для фиксированных TZ и5 множество N{TZ, S) всех действительных х, соответствующих {Х„), такое, что {Xs)TZ бесконечна и не 1-распределена, имеет меру нуль. Для X существует неслучайное двоичное представление тогда и только тогда, когда х принадлежит [) N{TZ,S), взятому по счетному множеству выборов TZ и5.

Следовательно, пусть TZ,S фиксированы. Рассмотрим множество T{aia2.. Ог), определенное для всех двоичных чисел 002... Ог как множество всех х, соответству-

ющих (Хп), такое, что {Xs„)TZ имеет > г элементов, из которых первые г элементов равны ai, 02, ..., йг соответственно. Первым результатом будет неравенство

T(aia2-. йг) имеет меру < 2". (32)

Доказательство начнем с замечания, что T{aia2... йг) является измеримым множеством: каждый элемент T{aia2. ..йг) - действительное число х = {O.XoXi... )2, для которого существует такое целое число т, что алгоритм S определяет.различные значения sq, si, Sm, и правило TZ определяет подпоследовательность Xg, Xsi, Xs,„, такую, что Xs„ является г-м элементом этой подпоследовательности. Множество всех действительных у = (O.FqFi ... )2,

таких, что yj - Xsk для

О < к < т, также принадлежит T{aia2. йг) и является измеримым множеством, состоящим из конечного объединения двоичных подынтервалов 1ь...ь,- Поскольку существует только счетное множество таких двоичных интервалов, то T{aia2. . йг) - счетное объединение двоичных интервалов, и оно, следовательно, измеримо. Более того, данный довод может быть распространен, чтобы показать, что мера Г(а1... a-i 0) равна мере Г(а1... a-i 1), так как последнее множество является объединением двоичных интервалов, полученных из предшествующей рекуррентной формулы Ys = Xs, для О < к < ТП И Ys Ф Xs. Поскольку

r(ai... йг-х 0) и r(ai... a-i 1) С Т{ах... a-i),

мера Т{а\а2.. .йт) равна самое большее половине меры Г(а1... Or-i). Неравенство (32) теперь легко получить индукцией по г.

Сейчас, когда (32) установлено, осталось, по существу, показать, что двоичное представление почти всех действительных чисел равнораспределено. Пусть для О < € < 1 В(г, е) - это и Т{а\. ..йг), где объединение берется по всем двоичным строкам ai... Or, для которых число единиц р{г) среди ai... удовлетворяет неравенству

р{7-) - г > ег.

Число таких двоичных строк равно С(г, е) = X] () > " суммирование выполняется по всем значениям к с \к - > ег. В упр. 1.2.10-21 доказано, что С{г,е) < 2+е~ отсюда" согласно (32)

В{г, е) имеет меру < 2-С{г, е) < 2е-\ (33)

На следующем шаге определим

В*{г,е)=В{г,€)иВ{г+1,е)иВ(г + 2,е)и---.

Мера В*{г,е) равна самое большее i.>r~ является остатком сходящегося ряда, так что

lim (мера Б*(г, е)) =0. (34)

Теперь, если х - действительное число, двоичное разложение (O.XqAi ..:)2 которого приводит к бесконечной не 1-распределенной последовательности (Xs„)7, и если v{r) обозначает число 1 в первых г элементах последней последовательности, то

v{r)jr - I > €

для некоторого е > О и бесконечного множества г. Это означает, что х принадлежит В{г,е) для всех г. И наконец, находим, что

N{n,S) = \J f]B{r,l/t).

t>2 г>1

Согласно (34) Пг>1 В*{г, 1/t) имеет меру нуль для всех t. Следовательно, N{TZ,S) имеет меру нуль.

Основываясь на факте существования двоичных последовательностей, удовлетворяющих определению R6, можно показать существование [0..1) случайных в этом смысле последовательностей (подробности - в упр. 36). Состоятельность определения R6 в связи с этим установлена.

Е. Случайные конечные последовательности. Доводы, приведенные выше, показывают, что невозможно определить понятие случайности конечной последовательности: заданная конечная последовательность так же вероятна, как и любая другая. До сих пор почти каждый согласен, что последовательность 011101001 "более случайна", чем 101010101, и последняя последовательность "более случайна", чем 000000000. Хотя верно, что истинно случайные последовательности проявляют локально неслучайное поведение, мы предполагаем такое поведение только у длинной конечной последовательности, а не у короткой.

Предлагались различные способы определения случайности конечной последовательности, но здесь будут сделаны только наброски нескольких идей. Для простоты ограничимся рассмотрением 6-ичных последовательностей.

Пусть задана 6-ичная последовательность Ао, Al, Xn-i- Можно сказать,

Pr(5(n))«p, если z/(A)/A-p < 1/V, (35)

где и{п) - величина, появившаяся в определении А в начале раздела. Приведенную выше последовательность можно назвать /с-распределенной, если

Pr(X„X„+i...X„+fc i =XiX2...Xi)«l/6= (36)

для всех 6-ичных чисел xiX2---Xk- (Ср. с определением D. К сожалению, последовательность может быть /с-распределенной согласно этому новому определению, когда она не {к - 1)-распределена.)

Сейчас можно дать следующее аналогичное определению R1 определение случайности.

Определение Q1. Ь-ичная последовательность длины N случайна, если она к-распределена (в вышеприведенном смысле) для всех положительных целых чисел k<\ogbN.

Например, согласно этому определению существует 178 неслучайных двоичных последовательностей длины 11,

00000001111 10000000111 11000000011 11100000001 11110000000

00000001110 10000000110 11000000010 11100000000 11010000000

00000001101 10000000101 11000000001 10100000001 10110000000,

00000001011 10000000011 01000000011 01100000001 01110000000 00000000111