\input style
of a Random Sequence" ({\sl BIT,\/} {\bf 5} (1965), 246--250). 
пОСЛЕДОВАТЕЛЬНОСТЬ, ПОСТРОЕННАЯ В ЭТОЙ СТАТЬЕ, ЦЕЛИКОМ СОСТОИТ ИЗ 
РАЦИОНАЛЬНЫХ ЧИСЕЛ. кАЖДОЕ ЧИСЛО~$U_n$ ИМЕЕТ КОНЕЧНОЕ ПРЕДСТАВЛЕНИЕ В 
ДВОИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ. нЕСКОЛЬКО БОЛЕЕ СЛОЖНЫЙ ЯВНЫЙ СПОСОБ 
ПОСТРОЕНИЯ $\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$ ПОСЛЕДОВАТЕЛЬНОСТИ МОЖНО ПОЛУЧИТЬ ИЗ 
ПРИВЕДЕННОЙ НИЖЕ ТЕОРЕМЫ~W.

\qsection{C. эКВИВАЛЕНТНЫ ЛИ ПОНЯТИЯ $\infty\hbox{-РАСПРЕДЕЛЕННОСТИ}$ И 
СЛУЧАЙНОСТИ}?
иЗ ВСЕГО СКАЗАННОГО ВЫШЕ ПРО $\infty\hbox{-РАСПРЕДЕЛЕННЫЕ}$ 
ПОСЛЕДОВАТЕЛЬНОСТИ СЛЕДУЕТ, ЧТО ПОНЯТИЕ $\infty\hbox{-РАСПРЕДЕЛЕННОСТИ}$ 
ВАЖНО САМО ПО СЕБЕ. мОЖНО ТАКЖЕ С ДОСТАТОЧНЫМ ОСНОВАНИЕМ СЧИТАТЬ, ЧТО 
СЛЕДУЮЩЕЕ ОПРЕДЕЛЕНИЕ ХОРОШО ОПИСЫВАЕТ ИНТУИТИВНОЕ ПОНЯТИЕ СЛУЧАЙНОСТИ.

\proclaim оПРЕДЕЛЕНИЕ R1. пОСЛЕДОВАТЕЛЬНОСТЬ НА~$[0, 1)$ НАЗЫВАЕТСЯ 
"СЛУЧАЙНОЙ", ЕСЛИ ОНА $\infty\hbox{-РАСПРЕДЕЛЕНА}$.

мЫ ВИДЕЛИ, ЧТО ТАКИЕ ПОСЛЕДОВАТЕЛЬНОСТИ УДОВЛЕТВОРЯЮТ ВСЕМ ТЕСТАМ П.~3.3.2 
И ЕЩЕ МНОГИМ ДРУГИМ.

пОПРОБУЕМ КРИТИЧЕСКИ ПОДОЙТИ К ЭТОМУ ОПРЕДЕЛЕНИЮ. пРЕЖДЕ ВСЕГО, ЯВЛЯЕТСЯ 
ЛИ ЛЮБАЯ "ИСТИННО СЛУЧАЙНАЯ" ПОСЛЕДОВАТЕЛЬНОСТЬ 
$\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$? сУЩЕСТВУЕТ НЕСЧЕТНОЕ КОЛИЧЕСТВО 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$U_0$, $U_1$,~\dots{} ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ, 
ЗАКЛЮЧЕННЫХ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ. еСЛИ ЗНАЧЕНИЯ~$U_0$, $U_1$,~\dots{} 
ПОЛУЧАЮТСЯ С ПОМОЩЬЮ ДАТЧИКА ИСТИННО СЛУЧАЙНЫХ ЧИСЕЛ, ЛЮБУЮ ИЗ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ МОЖНО СЧИТАТЬ РАВНОЦЕННОЙ. пРИ ЭТОМ НЕКОТОРЫЕ ИЗ 
ЭТИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ (В ДЕЙСТВИТЕЛЬНОСТИ БЕСКОНЕЧНО БОЛЬШОЕ ИХ ЧИСЛО) 
НЕ БУДУТ ДАЖЕ РАВНОМЕРНО РАСПРЕДЕЛЕНЫ. с ДРУГОЙ СТОРОНЫ, ПРИ ЛЮБОМ 
РАЗУМНОМ ОПРЕДЕЛЕНИИ ВЕРОЯТНОСТИ НА ЭТОМ ПРОСТРАНСТВЕ ВСЕХ ВОЗМОЖНЫХ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ МЫ ДОЛЖНЫ ЗАКЛЮЧИТЬ, ЧТО СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ 
$\infty\hbox{-РАСПРЕДЕЛЕНА}$ С \emph{ВЕРОЯТНОСТЬЮ}~$1$. тАКИМ ОБРАЗОМ, МЫ 
ПРИХОДИМ К ФОРМАЛИЗАЦИИ ОПРЕДЕЛЕНИЯ СЛУЧАЙНОСТИ, ДАННОГО фРЭНКЛИНОМ 
(СМ.\ НАЧАЛО ПАРАГРАФА).

\proclaim оПРЕДЕЛЕНИЕ R2. пОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>$ НА~$[0, 1)$ НАЗЫВАЕТСЯ 
"СЛУЧАЙНОЙ", ЕСЛИ ДЛЯ ЛЮБОГО СВОЙСТВА~$P$, ТАКОГО, ЧТО~$P(\<V_n>)$ 
СПРАВЕДЛИВО С ВЕРОЯТНОСТЬЮ~1 ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ~$\<V_n>$ НЕЗАВИСИМЫХ 
ВЫБОРОК СЛУЧАЙНЫХ ВЕЛИЧИН ИЗ РАВНОМЕРНОГО РАСПРЕДЕЛЕНИЯ, СПРАВЕДЛИВО~$P(\<U_n>)$.

вОЗМОЖНО ЛИ, ЧТО ОПРЕДЕЛЕНИЕ~R1 ЭКВИВАЛЕНТНО ОПРЕДЕЛЕНИЮ~R2? пОПРОБУЕМ 
ВЫДВИНУТЬ ПРОТИВ ОПРЕДЕЛЕНИЯ~R1 НЕКОТОРЫЕ ВОЗРАЖЕНИЯ.

пРЕЖДЕ ВСЕГО ОПРЕДЕЛЕНИЕ~R1 ИМЕЕТ ДЕЛО ТОЛЬКО С ПРЕДЕЛЬНЫМИ СВОЙСТВАМИ 
ПОСЛЕДОВАТЕЛЬНОСТИ ПРИ~$n\to\infty$. сУЩЕСТВУЮТ $\infty\hbox{-РАСПРЕДЕЛЕННЫЕ}$ 
ПОСЛЕДОВАТЕЛЬНОСТИ, НАЧИНАЮЩИЕСЯ ОТРЕЗКОМ
%% 172
ИЗ МИЛЛИОНА НУЛЕЙ. сЛЕДУЕТ ЛИ СЧИТАТЬ ТАКУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ СЛУЧАЙНОЙ?

эТО ВОЗРАЖЕНИЕ НЕ ОЧЕНЬ СЕРЬЕЗНО. пУСТЬ~$\varepsilon$---ЛЮБОЕ 
ПОЛОЖИТЕЛЬНОЕ ЧИСЛО, ТОГДА ВПОЛНЕ ВОЗМОЖНО, ЧТО КАЖДЫЙ ИЗ 
ПЕРВОГО МИЛЛИОНА ЧЛЕНОВ ПОСЛЕДОВАТЕЛЬНОСТИ МЕНЬШЕ~$\varepsilon$. кАК МЫ 
УЖЕ ОТМЕЧАЛИ РАНЕЕ, НЕТ СПОСОБА, ПОЗВОЛЯЮЩЕГО СУДИТЬ О ТОМ, СЛУЧАЙНА ИЛИ 
НЕТ КОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ. иСТИННО СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ С 
ВЕРОЯТНОСТЬЮ ЕДИНИЦА СОДЕРЖИТ БЕСКОНЕЧНО МНОГО ОТРЕЗКОВ ПО МИЛЛИОНУ 
ПОСЛЕДОВАТЕЛЬНЫХ ЧЛЕНОВ, КАЖДЫЙ ИЗ КОТОРЫХ МЕНЬШЕ~$\varepsilon$. пОЧЕМУ ЖЕ 
ТАКОЙ ОТРЕЗОК НЕ МОЖЕТ ОКАЗАТЬСЯ В НАЧАЛЕ ПОСЛЕДОВАТЕЛЬНОСТИ?

с ДРУГОЙ СТОРОНЫ, РАССМОТРИМ ОПРЕДЕЛЕНИЕ~R2, И ПУСТЬ $P$---СВОЙСТВО 
ПОСЛЕДОВАТЕЛЬНОСТИ, СОСТОЯЩЕЕ В ТОМ, ЧТО ВСЕ ЕЕ ЭЛЕМЕНТЫ РАЗЛИЧНЫ. 
сВОЙСТВО~$P$ СПРАВЕДЛИВО С ВЕРОЯТНОСТЬЮ ЕДИНИЦА, ПОЭТОМУ ЛЮБАЯ 
ПОСЛЕДОВАТЕЛЬНОСТЬ С МИЛЛИОНОМ НУЛЕЙ ПО \emph{ЭТОМУ} КРИТЕРИЮ НЕ ЯВЛЯЕТСЯ 
СЛУЧАЙНОЙ.

пУСТЬ ТЕПЕРЬ СВОЙСТВО~$P$ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО \emph{НИ ОДИН} ЭЛЕМЕНТ 
ПОСЛЕДОВАТЕЛЬНОСТИ НЕ РАВЕН НУЛЮ. оНО СПРАВЕДЛИВО С ВЕРОЯТНОСТЬЮ ЕДИНИЦА, 
ПОЭТОМУ ПО ОПРЕДЕЛЕНИЮ~R2 ЛЮБАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ, У КОТОРОЙ ЕСТЬ 
НУЛЕВОЙ ЭЛЕМЕНТ, НЕ ЯВЛЯЕТСЯ СЛУЧАЙНОЙ. рАССМОТРИМ БОЛЕЕ ОБЩИЙ СЛУЧАЙ: 
ПУСТЬ~$x_0$---ЛЮБОЕ ЗАДАННОЕ ЧИСЛО, ЗАКЛЮЧЕННОЕ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ, 
И~$P$---СВОЙСТВО, СОСТОЯЩЕЕ В ТОМ, ЧТО НИ ОДИН ЭЛЕМЕНТ ПОСЛЕДОВАТЕЛЬНОСТИ 
НЕ РАВЕН~$x_0$. иЗ ОПРЕДЕЛЕНИЯ~R2 СЛЕДУЕТ, ЧТО НИКАКАЯ СЛУЧАЙНАЯ 
ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ МОЖЕТ СОДЕРЖАТЬ ЭЛЕМЕНТ, РАВНЫЙ~$x_0$! тЕПЕРЬ МОЖНО 
ДОКАЗАТЬ, ЧТО \emph{НИ ОДНА ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ МОЖЕТ УДОВЛЕТВОРЯТЬ 
УСЛОВИЯМ, СФОРМУЛИРОВАННЫМ В ОПРЕДЕЛЕНИИ}~R2. (в САМОМ ДЕЛЕ, ЕСЛИ~$U_0$, 
$U_1$,~\dots{} ЕСТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ, УДОВЛЕТВОРЯЮЩАЯ ЭТИМ УСЛОВИЯМ, 
ТО ПОЛОЖИМ~$x_0=U_0$.)

тАКИМ ОБРАЗОМ, ЕСЛИ~R1---СЛИШКОМ СЛАБОЕ ОПРЕДЕЛЕНИЕ, ТО R2---СЛИШКОМ СИЛЬНОЕ. 
"пРАВИЛЬНОЕ" ОПРЕДЕЛЕНИЕ ДОЛЖНО БЫТЬ МЕНЕЕ ОГРАНИЧИТЕЛЬНЫМ, ЧЕМ~R2. оДНАКО 
МЫ, ВООБЩЕ ГОВОРЯ, ЕЩЕ НЕ ДОКАЗАЛИ, ЧТО R1 СЛИШКОМ СЛАБО, ПОЭТОМУ 
ПРОДОЛЖИМ ЕГО ИЗУЧЕНИЕ. вЫШЕ ГОВОРИЛОСЬ О ТОМ, ЧТО МОЖНО 
ПОСТРОИТЬ $\infty\hbox{-РАСПРЕДЕЛЕННУЮ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ 
\emph{РАЦИОНАЛЬНЫХ} ЧИСЕЛ. (рАЗУМЕЕТСЯ, В ЭТОМ НЕТ НИЧЕГО ОСОБЕННО 
УДИВИТЕЛЬНОГО: СМ.\ УПР.~1.8.) пОЧТИ ВСЕ ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА 
ИРРАЦИОНАЛЬНЫ, ПОЭТОМУ МОЖНО ПОТРЕБОВАТЬ, ЧТОБЫ ДЛЯ СЛУЧАЙНОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ ИМЕЛО МЕСТО РАВЕНСТВО
\EQ{
 \Pr(U_n \hbox{ РАЦИОНАЛЬНО})=0.
}

зАМЕТИМ, ЧТО РАВНОМЕРНАЯ РАСПРЕДЕЛЕННОСТЬ, ПО ОПРЕДЕЛЕНИЮ ОЗНАЧАЕТ, 
ЧТО~$\Pr(u\le U_n<v)=v-u$. иСПОЛЬЗУЯ ТЕОРИЮ МЕРЫ, ЛЕГКО ОБОБЩИТЬ ЭТО 
ОПРЕДЕЛЕНИЕ: "еСЛИ МЕРА МНОЖЕСТВА~$S\subseteq [0,1)$
%% 173
РАВНА~$\mu$, ТО
\EQ[27]{
 \Pr(U_n \in S)=\mu
}
ДЛЯ ВСЕХ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$\<U_n>$". в ЧАСТНОСТИ, ЕСЛИ 
МНОЖЕСТВО~$S$ СОСТАВЛЕНО ИЗ РАЦИОНАЛЬНЫХ ЧИСЕЛ, ОНО ИМЕЕТ МЕРУ НУЛЬ, И, 
ТАКИМ ОБРАЗОМ, НИКАКАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ РАЦИОНАЛЬНЫХ ЧИСЕЛ НЕ ЯВЛЯЕТСЯ 
РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ В ЭТОМ ОБОБЩЕННОМ СМЫСЛЕ. мОЖНО ОЖИДАТЬ, ЧТО 
ТЕОРЕМА~B ОБОБЩАЕТСЯ НА СЛУЧАЙ ИНТЕГРИРОВАНИЯ В СМЫСЛЕ лЕБЕГА, ЕСЛИ 
ПОТРЕБОВАТЬ ВЫПОЛНЕНИЯ СВОЙСТВА~\eqref[27]. оДНАКО МЫ ОПЯТЬ ПРИХОДИМ К 
ВЫВОДУ, ЧТО ОПРЕДЕЛЕНИЕ~\eqref[27] ЯВЛЯЕТСЯ СЛИШКОМ ЖЕСТКИМ, ПОСКОЛЬКУ НИ 
ОДНА ПОСЛЕДОВАТЕЛЬНОСТЬ \emph{НЕ} ОБЛАДАЕТ ЭТИМ СВОЙСТВОМ! еСЛИ $U_0$,  
$U_1$,~\dots---НЕКОТОРАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ, ТО МЕРА 
МНОЖЕСТВА~$S=\set{U_0, U_1,~\ldots}$ РАВНА НУЛЮ, ОДНАКО~$\Pr(U_n\in S)=1$.
тАКИМ ОБРАЗОМ, ПУТЕМ ТЕХ ЖЕ РАССУЖДЕНИЙ, С ПОМОЩЬЮ КОТОРЫХ МЫ ИСКЛЮЧИЛИ ИЗ 
СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ РАЦИОНАЛЬНЫЕ ЧИСЛА, МОЖНО ИСКЛЮЧИТЬ ВСЕ 
СЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ.

пОКА ВСЕ ЕЩЕ НЕ ПОКАЗАНО, ЧТО ОПРЕДЕЛЕНИЕ~R1 НЕПРИГОДНО. пРОТИВ НЕГО, 
ОДНАКО, СУЩЕСТВУЮТ ВЕСКИЕ ВОЗРАЖЕНИЯ. еСЛИ, НАПРИМЕР, ИМЕЕТСЯ СЛУЧАЙНАЯ В 
ИНТУИТИВНОМ СМЫСЛЕ ПОСЛЕДОВАТЕЛЬНОСТЬ, БЕСКОНЕЧНАЯ ЕЕ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ
\EQ[28]{
 U_0, U_1, U_4, U_9,~\ldots, U_{n^2},~\ldots
}
ДОЛЖНА ТАКЖЕ БЫТЬ СЛУЧАЙНОЙ. дЛЯ $\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$ 
ПОСЛЕДОВАТЕЛЬНОСТИ ЭТО НЕ ВСЕГДА СПРАВЕДЛИВО. (дЕЙСТВИТЕЛЬНО, ЕСЛИ ВЗЯТЬ 
ЛЮБУЮ $\infty\hbox{-РАСПРЕДЕЛЕННУЮ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ И 
ПОЛОЖИТЬ~$U_{n^2}\leftarrow 0$ ДЛЯ ВСЕХ~$n$, ВЕЛИЧИНЫ~$\nu_k(n)$, КОТОРЫЕ 
ПОЯВЛЯЮТСЯ ПРИ ПРОВЕРКЕ $k\hbox{-РАСПРЕДЕЛЕННОСТИ}$, ИЗМЕНЯТСЯ НЕ БОЛЬШЕ, 
ЧЕМ НА ВЕЛИЧИНУ ПОРЯДКА~$\sqrt{n}$, ТАК ЧТО ПРЕДЕЛЫ ОТНОШЕНИЙ~$\nu_k(n)/n$ 
НЕ ИЗМЕНЯТСЯ.) оТСЮДА СЛЕДУЕТ, ЧТО~R1 НЕ ОБЛАДАЕТ ЭТИМ СВОЙСТВОМ СЛУЧАЙНОСТИ.

пОПРОБУЕМ УСИЛИТЬ~R1 СЛЕДУЮЩИМ ОБРАЗОМ.

\proclaim оПРЕДЕЛЕНИЕ~R3. пОСЛЕДОВАТЕЛЬНОСТЬ НА~$[0, 1)$ НАЗЫВАЕТСЯ 
"СЛУЧАЙНОЙ", ЕСЛИ КАЖДАЯ ЕЕ БЕСКОНЕЧНАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ 
$\infty\hbox{-РАСПРЕДЕЛЕНА}$.

оДНАКО И ЭТО ОПРЕДЕЛЕНИЕ ОКАЗЫВАЕТСЯ СЛИШКОМ ОГРАНИЧИТЕЛЬНЫМ, ПОСКОЛЬКУ 
ИЗ ЛЮБОЙ РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ~$\<U_n>$ МОЖНО 
ВЫДЕЛИТЬ МОНОТОННУЮ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$U_{s_0}<U_{s_1}<U_{s_2}<\ldots\,$.

сЛЕДУЕТ ТАК ОГРАНИЧИТЬ КЛАСС РАССМАТРИВАЕМЫХ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ, 
ЧТОБЫ КАЖДЫЙ ЧЛЕН ПОСЛЕДОВАТЕЛЬНОСТИ, ЗАРАНЕЕ НЕИЗВЕСТНЫЙ, МОЖНО БЫЛО БЫ 
ВЫБИРАТЬ ПО НЕКОТОРОМУ ПРАВИЛУ. тАКИМ ОБРАЗОМ, ПОЛУЧАЕМ

%% 174

\proclaim оПРЕДЕЛЕНИЕ~R4. пОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>$ НА~$[0, 1)$ 
НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ КАКОВ БЫ НИ БЫЛ ЭФФЕКТИВНЫЙ АЛГОРИТМ, 
С ПОМОЩЬЮ КОТОРОГО ПОЛУЧАЕТСЯ БЕСКОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ РАЗЛИЧНЫХ 
НЕОТРИЦАТЕЛЬНЫХ ЦЕЛЫХ ЧИСЕЛ~$s_n$, ГДЕ~$n\ge0$, 
ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$U_{s_0}$, $U_{s_1}$,~\dots,  СООТВЕТСТВУЮЩАЯ 
ЭТОМУ АЛГОРИТМУ, ЯВЛЯЕТСЯ $\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$.

аЛГОРИТМЫ, О КОТОРЫХ ИДЕТ РЕЧЬ,---ЭТО ПРОЦЕДУРЫ, ВЫЧИСЛЯЮЩИЕ~$s_n$ ПО 
ЗАДАННОМУ~$n$. в ЭТОМ ОПРЕДЕЛЕНИИ ГОВОРИТСЯ ОБО ВСЕХ БЕСКОНЕЧНЫХ 
"РЕКУРСИВНО ПЕРЕЧИСЛИМЫХ" ПОДПОСЛЕДОВАТЕЛЬНОСТЯХ В СООТВЕТСТВИИ С ОБЫЧНЫМ 
ОПРЕДЕЛЕНИЕМ РЕКУРСИВНОЙ ПЕРЕЧИСЛИМОСТИ (СМ.~ГЛ.~11).

оТНОСИТЕЛЬНО ДАННОГО ОПРЕДЕЛЕНИЯ СЛЕДУЕТ СДЕЛАТЬ НЕСКОЛЬКО ЗАМЕЧАНИЙ. 
пОСЛЕДОВАТЕЛЬНОСТЬ~$\<\pi^n\bmod 1>$ НАВЕРНЯКА \emph{НЕ} БУДЕТ 
УДОВЛЕТВОРЯТЬ ОПРЕДЕЛЕНИЮ~R4, ПОСКОЛЬКУ ИЛИ ОНА НЕ ЯВЛЯЕТСЯ РАВНОМЕРНО 
РАСПРЕДЕЛЕННОЙ, ИЛИ СУЩЕСТВУЕТ ЭФФЕКТИВНЫЙ АЛГОРИТМ, ОПРЕДЕЛЯЮЩИЙ 
БЕСКОНЕЧНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ~$s_n$, ТАКУЮ, 
ЧТО~$(\pi^{s_0}\bmod 1) < (\pi^{s_1}\bmod 1) < \ldots\,$. мОЖНО ПОЭТОМУ 
УТВЕРЖДАТЬ, ЧТО \emph{НИ ОДНА ЯВНЫМ ОБРАЗОМ ОПРЕДЕЛЕННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ 
НЕ МОЖЕТ УДОВЛЕТВОРЯТЬ ОПРЕДЕЛЕНИЮ}~R4. с ЭТИМ СЛЕДУЕТ СОГЛАСИТЬСЯ, ЕСЛИ 
СЧИТАТЬ, ЧТО ЯВНЫМ ОБРАЗОМ ОПРЕДЕЛЕННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ МОЖЕТ БЫТЬ 
ДЕЙСТВИТЕЛЬНО СЛУЧАЙНОЙ. вПОЛНЕ ВОЗМОЖНО, ОДНАКО, ЧТО 
ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<\theta^n\bmod 1>$ БУДЕТ УДОВЛЕТВОРЯТЬ ОПРЕДЕЛЕНИЮ~R4 
ДЛЯ ПОЧТИ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ~$\theta>1$. зДЕСЬ НЕТ ПРОТИВОРЕЧИЯ, 
ПОСКОЛЬКУ ПОЧТИ ВСЕ~$\theta$ НЕВОЗМОЖНО ВЫЧИСЛИТЬ С ПОМОЩЬЮ АЛГОРИТМА. 
иЗВЕСТНЫ, НАПРИМЕР, СЛЕДУЮЩИЕ ФАКТЫ. 
(i)~пОСЛЕДОВАТЕЛЬНОСТЬ~$\<\theta^m\bmod 1>$ УДОВЛЕТВОРЯЕТ ОПРЕДЕЛЕНИЮ~R4 
ДЛЯ ПОЧТИ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ~$\theta>1$, ЕСЛИ УСЛОВИЕ 
$\infty\hbox{-РАСПРЕДЕЛЕННОСТИ}$ ЗАМЕНИТЬ НА 
УСЛОВИЕ $1\hbox{-РАСПРЕДЕЛЕННОСТИ}$. эТА ТЕОРЕМА БЫЛА ДОКАЗАНА ю.~кОКСМОЙ 
({\sl Compositio Mathematica,\/} {\bf 2} (1935), 250--258). 
(ii)~пОСЛЕДОВАТЕЛЬНОСТЬ~$\<\theta^{s(n)}\bmod 1>$ 
$\infty\hbox{-РАСПРЕДЕЛЕНА}$ ДЛЯ ПОЧТИ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ~$\theta>1$, 
ЕСЛИ~$\<s(n)>$ ЕСТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ ЦЕЛЫХ ЧИСЕЛ, ТАКИХ, 
ЧТО~$s(n+1)-s(n)\to\infty$ ПРИ~$n\to\infty$. мОЖНО, НАПРИМЕР, 
ПОЛОЖИТЬ~$s(n)=n^2$, ИЛИ~$s(n)=\floor{n\log n}$.

оПРЕДЕЛЕНИЕ~R4 НАМНОГО СИЛЬНЕЕ ОПРЕДЕЛЕНИЯ~R1, ОДНАКО И ОНО ВСЕ ЕЩЕ 
СЛИШКОМ СЛАБО. пУСТЬ, НАПРИМЕР, ИМЕЕТСЯ ИСТИННО СЛУЧАЙНАЯ 
ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>$. оПРЕДЕЛИМ 
ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_{s_n}>$ СЛЕДУЮЩИМ ОБРАЗОМ: $s_0=0$, И 
ДЛЯ~$n>0$ ЧИСЛО~$s_n$---НАИМЕНЬШЕЕ ПОЛОЖИТЕЛЬНОЕ ЦЕЛОЕ, ТАКОЕ, ЧТО ВСЕ 
ЧИСЛА~$U_{s_n-1}$, $U_{s_n-2}$,~\dots, $U_{s_n-n}$ МЕНЬШЕ ПОЛОВИНЫ. тЕМ 
САМЫМ МЫ РАССМАТРИВАЕМ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ ВЕЛИЧИН, СЛЕДУЮЩИХ СРАЗУ ЖЕ 
ЗА СЕРИЕЙ ИЗ $n$~ЧЛЕНОВ, КАЖДЫЙ ИЗ КОТОРЫХ МЕНЬШЕ~$1/2$. пРЕДПОЛОЖИМ, 
ЧТО "$U_n<1/2$" СООТВЕТСТВУЕТ ВЫПАДЕНИЮ "РЕШЕТКИ" ПРИ БРОСАНИИ МОНЕТЫ. 
иГРОКИ ОБЫЧНО СЧИТАЮТ, ЧТО ЕСЛИ МОНЕТА БРОСАЕТСЯ ЧЕСТНО, ТО ДЛИННАЯ 
СЕРИЯ ВЫПАДЕНИЯ "РЕШЕТОК" УВЕЛИЧИВАЕТ
%% 175
ВЕРОЯТНОСТЬ ПОСЛЕДУЮЩЕГО ВЫПАДЕНИЯ "ОРЛА", И ОПРЕДЕЛЕННАЯ НАМИ 
ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_{s_n}>$ СООТВЕТСТВУЕТ СТРАТЕГИИ ИГРОКА, ПРИ 
КОТОРОЙ ОН ДЕЛАЕТ $n\hbox{-Ю}$~СТАВКУ ПРИ БРОСАНИИ МОНЕТЫ, СЛЕДУЮЩЕМ 
ВСЛЕД ЗА ПЕРВЫМ ПОСЛЕДОВАТЕЛЬНЫМ ВЫПАДЕНИЕМ $n$~"РЕШЕТОК". иГРОК МОЖЕТ 
СЧИТАТЬ, ЧТО~$\Pr(U_{s_n}\ge 1/2)$ ПРЕВОСХОДИТ ПОЛОВИНУ, НО, РАЗУМЕЕТСЯ, В 
ИСТИННО СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ЗНАЧЕНИЯ~$\<U_{s_n}>$ БУДУТ 
СОВЕРШЕННО СЛУЧАЙНЫМИ. нЕТ ТАКОЙ СТРАТЕГИИ, КОТОРАЯ ОБЕСПЕЧИВАЛА БЫ 
ПРЕИМУЩЕСТВО В ИГРЕ. в ОПРЕДЕЛЕНИИ~R4 НИЧЕГО НЕ ГОВОРИТСЯ О 
ПОДПОСЛЕДОВАТЕЛЬНОСТЯХ, СОСТАВЛЕННЫХ СОГЛАСНО ТАКОЙ СТРАТЕГИИ, ПОЭТОМУ 
НУЖНО ПРЕДЛОЖИТЬ НЕЧТО БОЛЬШЕЕ.

оПРЕДЕЛИМ "ПРАВИЛО ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ"~$\cR$ КАК БЕСКОНЕЧНУЮ 
ПОСЛЕДОВАТЕЛЬНОСТЬ ФУНКЦИЙ~$\<f_n(x_1,~\ldots, x_n)>$, ГДЕ~$n\ge0$, 
$f_n$---ФУНКЦИЯ $n$~ПЕРЕМЕННЫХ, И~$f_n(x_1,~\ldots, x_n)$ МОЖЕТ ПРИНИМАТЬ 
ЗНАЧЕНИЕ~$0$ ИЛИ~$1$. зДЕСЬ $x_1$,~\dots, $x_n$ ЯВЛЯЮТСЯ ЭЛЕМЕНТАМИ 
НЕКОТОРОГО МНОЖЕСТВА~$S$. (тАКИМ ОБРАЗОМ, $f_0$~ЕСТЬ ПОСТОЯННАЯ ФУНКЦИЯ, 
РАВНАЯ~$0$ ИЛИ~$1$.) пРАВИЛО~$\cR$ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ 
ОПРЕДЕЛЯЕТ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ ЛЮБОЙ БЕСКОНЕЧНОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ~$\<X_n>$ ЭЛЕМЕНТОВ~$S$ СЛЕДУЮЩИМ ОБРАЗОМ: 
\dfn{$n\hbox{-Й}$ ЧЛЕН~$X_n$ СОДЕРЖИТСЯ В 
ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\<X_n>\cR$ В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ, 
КОГДА~$f_n(X_0, X_1,~\dots, X_{n-1})=1$.} зАМЕТИМ, ЧТО ОПРЕДЕЛЕННАЯ ТАКИМ 
ОБРАЗОМ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\<X_n>\cR$ НЕ ОБЯЗАТЕЛЬНО ЯВЛЯЕТСЯ 
БЕСКОНЕЧНОЙ И МОЖЕТ ДАЖЕ БЫТЬ ПУСТОЙ.

"пОДПОСЛЕДОВАТЕЛЬНОСТЬ ИГРОКА", ОПИСАННАЯ ВЫШЕ, СООТВЕТСТВУЕТ СЛЕДУЮЩЕМУ 
ПРАВИЛУ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ: "$f_0=1$; 
$f_n(x_1,~\ldots, x_n)=1$ ПРИ~$n>0$ В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ, 
КОГДА СУЩЕСТВУЕТ НЕКОТОРОЕ~$k$, $0<k\le n$,  ТАКОЕ,   ЧТО~$x_m<1/2$, 
$x_{m-1}<1/2$,~\dots, $x_{m-k+1}<1/2$,~\dots, $x_{m-k+1}<1/2$ ПРИ~$m=n$, 
НО НЕ В СЛУЧАЕ, КОГДА~$k\le m < n$".

пРАВИЛО ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\cR$ 
НАЗЫВАЕТСЯ \emph{"ВЫЧИСЛИМЫМ",} ЕСЛИ СУЩЕСТВУЕТ ЭФФЕКТИВНЫЙ АЛГОРИТМ, 
ПОЗВОЛЯЮЩИЙ ОПРЕДЕЛИТЬ ЗНАЧЕНИЕ~$f_n(x_1,~\ldots, x_n)$ ПО ВХОДНЫМ 
ДАННЫМ~$n$, $x_1$,~\dots, $x_n$. сТРЕМЯСЬ ОПРЕДЕЛИТЬ ПОНЯТИЕ СЛУЧАЙНОСТИ, 
НУЖНО ОГРАНИЧИВАТЬСЯ ВЫЧИСЛИМЫМИ ПРАВИЛАМИ ПОСТРОЕНИЯ 
ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ, В ПРОТИВНОМ СЛУЧАЕ МЫ ПОЛУЧИМ СЛИШКОМ 
СИЛЬНОЕ ОПРЕДЕЛЕНИЕ, ПОДОБНОЕ~R3. пРОИЗВОЛЬНЫЕ ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА НЕ 
МОГУТ СЛУЖИТЬ ВХОДНЫМИ ДАННЫМИ ЭФФЕКТИВНЫХ АЛГОРИТМОВ, ПОТОМУ ЧТО ЕСЛИ, 
НАПРИМЕР, ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО~$x$ В ДЕСЯТИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ 
ОПРЕДЕЛЯЕТСЯ БЕСКОНЕЧНОЙ ПОСЛЕДОВАТЕЛЬНОСТЬЮ ЦИФР, ТО НЕ СУЩЕСТВУЕТ 
АЛГОРИТМА, ПО КОТОРОМУ МОЖНО БЫЛО БЫ ОПРЕДЕЛИТЬ, СПРАВЕДЛИВО ЛИ 
НЕРАВЕНСТВО~$x<1/3$, ПОСКОЛЬКУ ПРИШЛОСЬ БЫ ИССЛЕДОВАТЬ ВСЕ ЗНАКИ 
ЧИСЛА~$0,333\ldots\,$. в СВЯЗИ С ЭТИМ ВЫЧИСЛИМЫЕ ПРАВИЛА ПОСТРОЕНИЯ 
ПОДПОСЛЕДОВАТЕЛЬНОСТИ НЕ ПРИЛОЖИМЫ КО ВСЕМ ПОСЛЕДОВАТЕЛЬНОСТЯМ "НА~$[0, 1)$", 
И СЛЕДУЮЩЕЕ
%% 176
ОПРЕДЕЛЕНИЕ БУДЕТ УДОБНО ОСНОВЫВАТЬ НА $b\hbox{-ИЧНЫХ}$ ПОСЛЕДОВАТЕЛЬНОСТЯХ.

\proclaim оПРЕДЕЛЕНИЕ~R5. {$b\hbox{-ИЧНАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ НАЗЫВАЕТСЯ 
"СЛУЧАЙНОЙ", ЕСЛИ КАЖДАЯ ЕЕ БЕСКОНЕЧНАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ, 
ОПРЕДЕЛЕННАЯ С ПОМОЩЬЮ ВЫЧИСЛИМОГО ПРАВИЛА ПОСТРОЕНИЯ 
ПОДПОСЛЕДОВАТЕЛЬНОСТИ, 1-РАСПРЕДЕЛЕНА.
 \hiddenpar
пОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>$ НА~$[0, 1)$ НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ 
$b\hbox{-ИЧНАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<\floor{bU_n}>$ "СЛУЧАЙНА" ДЛЯ 
ВСЕХ ЦЕЛЫХ ЧИСЕЛ~$b\ge2$.
}

зАМЕТИМ, ЧТО В ОПРЕДЕЛЕНИИ~R5 ПОДПОСЛЕДОВАТЕЛЬНОСТЬ 
"$1\hbox{-РАСПРЕДЕЛЕНА}$", А НЕ "$\infty\hbox{-РАСПРЕДЕЛЕНА}$". иНТЕРЕСНО 
ЗАМЕТИТЬ, ЧТО ОБЩНОСТЬ ПРИ ЭТОМ НЕ ТЕРЯЕТСЯ. в САМОМ ДЕЛЕ, ДЛЯ 
ЛЮБОГО $b\hbox{-ИЧНОГО}$ ЧИСЛА~$a_1\ldots a_k$ МОЖНО ТАК ОПРЕДЕЛИТЬ 
ОЧЕВИДНЫМ ОБРАЗОМ ВЫЧИСЛИМОЕ ПРАВИЛО~$\cR(a_1{}\ldots{}a_k)$ ПОСТРОЕНИЯ 
ПОДПОСЛЕДОВАТЕЛЬНОСТИ. пОЛОЖИМ~$f_n(x_1,~\dots, x_n)=1$ В ТОМ И ТОЛЬКО ТОМ 
СЛУЧАЕ КОГДА~$n\ge k-1$ И~$x_{n-k+1}=a_1$,~\dots, $x_{n-1}=a_{k-1}$,  
$x_n=a_k$. еСЛИ $\<X_n>$ ЯВЛЯЕТСЯ $k\hbox{-РАСПРЕДЕЛЕННОЙ}$ 
$b\hbox{-ИЧНОЙ}$ ПОСЛЕДОВАТЕЛЬНОСТЬЮ, ТО УПОМЯНУТОЕ 
ПРАВИЛО~$\cR(a_1\ldots{}a_k)$, КОТОРОЕ ОТБИРАЕТ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ, 
СОСТОЯЩУЮ ИЗ ЧЛЕНОВ, СЛЕДУЮЩИХ СРАЗУ ЗА ПОЯВЛЕНИЕМ~$a_1{}\ldots{}a_k$,  
ОПРЕДЕЛЯЕТ БЕСКОНЕЧНУЮ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ, И ЕСЛИ ЭТА 
ПОДПОСЛЕДОВАТЕЛЬНОСТЬ $1\hbox{-РАСПРЕДЕЛЕНА}$, ТО КАЖДЫЙ ИЗ НАБОРОВ, 
СОСТОЯЩИХ ИЗ $k+1$~ЭЛЕМЕНТОВ $a_1\ldots{}a_k{}a_{k+1}$, ПРИ УСЛОВИИ, 
ЧТО~$0\le a_{k+1}<b$, ПОЯВЛЯЕТСЯ В~$\<X_n>$ С ВЕРОЯТНОСТЬЮ~$1/b^{k+1}$. 
тАКИМ ОБРАЗОМ, ИНДУКЦИЕЙ ПО~$k$ МОЖНО ДОКАЗАТЬ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ, 
УДОВЛЕТВОРЯЮЩАЯ ОПРЕДЕЛЕНИЮ~R5, $k\hbox{-pacПРЕДЕЛЕНА}$ ДЛЯ ВСЕХ~$k$. 
аНАЛОГИЧНЫМ ОБРАЗОМ, РАССМАТРИВАЯ "КОМПОЗИЦИЮ" ПРАВИЛ ПОСТРОЕНИЯ 
ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ (ЕСЛИ $\cR_1$~ОПРЕДЕЛЯЕТ БЕСКОНЕЧНУЮ 
ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\<X_n>\cR_1$, МОЖНО ОПРЕДЕЛИТЬ~$\cR_1\cR_2$ КАК 
ПРАВИЛО ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ, ТАКОЕ, 
ЧТО~$\<X_n>\cR_1\cR_2=((\<X_n>\cR_1) \cR_2)$, МЫ ПРИХОДИМ К ВЫВОДУ, ЧТО 
ВСЕ ПОДПОСЛЕДОВАТЕЛЬНОСТИ, ОПИСАННЫЕ В ОПРЕДЕЛЕНИИ~R5, 
$\infty\hbox{-РАСПРЕДЕЛЕНЫ}$ (СМ.\ УПР.~32).

пОСКОЛЬКУ $\infty\hbox{-РАСПРЕДЕЛЕННОСТЬ}$ СЛЕДУЕТ ИЗ ОПРЕДЕЛЕНИЯ~R5 КАК 
ОЧЕНЬ ЧАСТНЫЙ СЛУЧАЙ, МОЖНО НАДЕЯТЬСЯ НА ТО, ЧТО МЫ, НАКОНЕЦ, 
СФОРМУЛИРОВАЛИ ИСКОМОЕ ОПРЕДЕЛЕНИЕ СЛУЧАЙНОСТИ. нО, УВЫ, ОСТАЕТСЯ ЕЩЕ ОДНА 
ПРОБЛЕМА! вОВСЕ НЕ ОЧЕВИДНО, ЧТО ПОСЛЕДОВАТЕЛЬНОСТИ, УДОВЛЕТВОРЯЮЩИЕ 
ОПРЕДЕЛЕНИЮ~R4, ДОЛЖНЫ ТАКЖЕ УДОВЛЕТВОРЯТЬ ОПРЕДЕЛЕНИЮ~R5. "вЫЧИСЛИМЫЕ 
ПРАВИЛА ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ", КОТОРЫЕ МЫ ВВЕЛИ, 
ВСЕГДА ПЕРЕЧИСЛЯЮТ ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\<X_{s_n}>$, ДЛЯ 
КОТОРЫХ~$s_0<s_1<\ldots\,$, И ЭТО ПРИВОДИТ К ТАК НАЗЫВАЕМЫМ 
"РЕКУРСИВНЫМ ПОСЛЕДОВАТЕЛЬНОСТЯМ". оНИ НЕ ВКЛЮЧАЮТ В СЕБЯ ВСЕ 
РЕКУРСИВНО ПЕРЕЧИСЛИМЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ, ДОПУСКАЕМЫЕ ОПРЕДЕЛЕНИЕМ~R4,
%% 177
ГДЕ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<s_n>$ НЕ ОБЯЗАНА БЫТЬ МОНОТОННОЙ; ДОЛЖНО ЛИШЬ 
СОБЛЮДАТЬСЯ УСЛОВИЕ~$s_n\ne s_m$, ПРИ~$n=m$.

сТОЛКНУВШИСЬ С ТАКИМ ПРЕПЯТСТВИЕМ, МЫ ПРИХОДИМ К КОМБИНАЦИИ 
ОПРЕДЕЛЕНИЙ~R4 И~R5.

\proclaim оПРЕДЕЛЕНИЕ~R6. {$b\hbox{-ИЧНАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<X_n>$ 
НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ ДЛЯ ЛЮБОГО ЭФФЕКТИВНОГО АЛГОРИТМА, 
ОПРЕДЕЛЯЮЩЕГО БЕСКОНЕЧНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ РАЗЛИЧНЫХ НЕОТРИЦАТЕЛЬНЫХ 
ЦЕЛЫХ ЧИСЕЛ~$\<s_n>$ КАК ФУНКЦИЮ ОТ~$n$ И ЗНАЧЕНИЙ~$X_{s_0}$,~\dots, 
$X_{s_{n-1}}$, СООТВЕТСТВУЮЩАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\<X_{s_n}>$ 
"СЛУЧАЙНА" В СМЫСЛЕ ОПРЕДЕЛЕНИЯ~R5.
  \hiddenpar
пОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>$ НА~$[0, 1)$ НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ 
$b\hbox{-ИЧНАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<\floor{bU_n}>$ "СЛУЧАЙНА" ПРИ ВСЕХ 
ЦЕЛЫХ ЧИСЛАХ~$b\ge 2$.
}

аВТОР УТВЕРЖДАЕТ, ЧТО ЭТО ОПРЕДЕЛЕНИЕ, НЕСОМНЕННО, ОТВЕЧАЕТ ВСЕМ РАЗУМНЫМ 
ФИЛОСОФСКИМ ТРЕБОВАНИЯМ, ПРЕД®ЯВЛЯЕМЫМ К ПОНЯТИЮ СЛУЧАЙНОСТИ, И, ТАКИМ 
ОБРАЗОМ, ДАЕТ ОТВЕТ НА ГЛАВНЫЙ ВОПРОС, ПОСТАВЛЕННЫЙ ЗДЕСЬ.

\section{D.~сУЩЕСТВОВАНИЕ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ}. мЫ ВИДЕЛИ, ЧТО 
ОПРЕДЕЛЕНИЕ~R3 ПОТОМУ ОКАЗАЛОСЬ СЛИШКОМ СИЛЬНЫМ, ЧТО НИ ОДНА 
ПОСЛЕДОВАТЕЛЬНОСТЬ ЕМУ НЕ УДОВЛЕТВОРЯЛА, И ВВОДЯ ОПРЕДЕЛЕНИЯ~R4, R5 И~R6, 
МЫ СТАРАЛИСЬ СОХРАНИТЬ ОСНОВНЫЕ СВОЙСТВА ОПРЕДЕЛЕНИЯ~R3. дЛЯ ТОГО ЧТОБЫ 
ПОКАЗАТЬ, ЧТО ОПРЕДЕЛЕНИЕ~R6 НЕ ЯВЛЯЕТСЯ СЛИШКОМ ОГРАНИЧИТЕЛЬНЫМ, 
СЛЕДУЕТ ДОКАЗАТЬ ФАКТ СУЩЕСТВОВАНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, 
УДОВЛЕТВОРЯЮЩИХ СООТВЕТСТВУЮЩИМ ТРЕБОВАНИЯМ. иСХОДЯ ИЗ ИНТУИТИВНЫХ 
СООБРАЖЕНИЙ, НИКТО НЕ СОМНЕВАЕТСЯ В ИХ СУЩЕСТВОВАНИИ, ПОСКОЛЬКУ КАЖДЫЙ 
ВЕРИТ В ТО, ЧТО ИСТИННО СЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ СУЩЕСТВУЮТ И 
УДОВЛЕТВОРЯЮТ ОПРЕДЕЛЕНИЮ~R6. оДНАКО ЧТОБЫ УБЕДИТЬСЯ В СОСТОЯТЕЛЬНОСТИ 
ОПРЕДЕЛЕНИЯ, НЕОБХОДИМО ДОКАЗАТЕЛЬСТВО.

иНТЕРЕСНЫЙ МЕТОД ПОСТРОЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, УДОВЛЕТВОРЯЮЩИХ 
ОПРЕДЕЛЕНИЮ~R5, ПРЕДЛОЖИЛ а.~вАЛЬД. сНАЧАЛА СТРОИТСЯ ОЧЕНЬ ПРОСТАЯ 
$1\hbox{-РАСПРЕДЕЛЕННАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ.

\proclaim лЕММА~T. пУСТЬ В ДВОИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ ОПРЕДЕЛЕНА 
ПОСЛЕДОВАТЕЛЬНОСТЬ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ~$\<V_n>$:
\EQ[29]{
 V_0=0, V_1=.1, V_2=.01, V_3=.11, V_4=.001,~\ldots,
 V_n=.c_r\ldots{}c_1 1, \rem{ЕСЛИ~$n=2^r+c_12^{r-1}+\cdots+c_r$.}
}
пУСТЬ $I_{b_1\ldots{}b_r}$~ОБОЗНАЧАЕТ МНОЖЕСТВО ТАКИХ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ 
НА ОТРЕЗКЕ~$[0, 1)$, ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ КОТОРЫХ 
НАЧИНАЕТСЯ С~$0.b_1\ldots{}b_r$. тАКИМ ОБРАЗОМ,
\EQ[30]{
 I_{b_1\ldots{}b_r}=[0.b_1\ldots{} b_r, 0.b_1\ldots{}b_r+2^{-r}).
}
%%178
тОГДА, ЕСЛИ $\nu(n)$~ОБОЗНАЧАЕТ КОЛИЧЕСТВО ЧИСЕЛ~$V_k$, 
СОДЕРЖАЩИХСЯ В~$I_{b_1\ldots{}b_r}$ ПРИ~$0\le k < n$, ИМЕЕТ МЕСТО НЕРАВЕНСТВО
\EQ[31]{
 \abs{\nu(n)/n-2^{-r}}\le 1/n.
}

\proof пОСКОЛЬКУ $\nu(n)$~ЕСТЬ ЧИСЛО ТЕХ~$k$, ДЛЯ 
КОТОРЫХ~$k\bmod 2^r=b_r\ldots{}b_1$, МЫ ИМЕЕМ~$\nu(n)=t$ ИЛИ~$t+1$, 
КОГДА~$\floor{n/2^r}=t$. тАКИМ ОБРАЗОМ, $\abs{\nu(n)-n/2^r}\le 1$.
\proofend

иЗ ФОРМУЛЫ~\eqref[31] СЛЕДУЕТ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<\floor{2^rV_n}>$ 
ЯВЛЯЕТСЯ РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ $2^r\hbox{-ИЧНОЙ}$ 
ПОСЛЕДОВАТЕЛЬНОСТЬЮ; ОТСЮДА И ИЗ ТЕОРЕМЫ~A ЗАКЛЮЧАЕМ, 
ЧТО~$\<V_n>$---РАВНОМЕРНО РАСПРЕДЕЛЕННАЯ НА~$[0, 1)$ ПОСЛЕДОВАТЕЛЬНОСТЬ. в 
САМОМ ДЕЛЕ, ЯСНО, ЧТО~$\<V_n>$ НАСТОЛЬКО РАВНОМЕРНО РАСПРЕДЕЛЕНА, 
НАСКОЛЬКО МОЖЕТ БЫТЬ РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТЬ 
НА~$[0, 1)$! (дАЛЬНЕЙШЕЕ ОБСУЖДЕНИЕ СВОЙСТВ ЭТОЙ И СВЯЗАННЫХ С НЕЙ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИМЕЕТСЯ В СТАТЬЯХ и.~ВАН~ДЕР~кОРПУТА ({\sl Proc. 
Koninklijke Nederlandse Akademie van Wetenschappen,\/} {\bf 38} (1935), 
813--821, 1058--1066) И дЖ.~хОЛТОНА ({\sl Numerische Mathematik,\/} {\bf 2} 
(1960), 84--90, 196).

пУСТЬ ТЕПЕРЬ~$\cR_1$, $\cR_2$,~\dots---БЕСКОНЕЧНОЕ МНОЖЕСТВО 
ПРАВИЛ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ. мЫ ХОТИМ НАЙТИ 
ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>$, ВСЕ БЕСКОНЕЧНЫЕ 
ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\<U_n>\cR_j$ КОТОРОЙ РАВНОМЕРНО РАСПРЕДЕЛЕНЫ.

\alg W.(пОСЛЕДОВАТЕЛЬНОСТЬ вАЛЬДА.) эТА ПРОЦЕДУРА ОПРЕДЕЛЯЕТ 
ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>$ НА~$[0, 1)$, ЕСЛИ ЗАДАНО БЕСКОНЕЧНОЕ МНОЖЕСТВО 
ПРАВИЛ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ~$\cR_1$, $\cR_2$,~\dots, 
ОПРЕДЕЛЯЮЩИХ ПОДПОСЛЕДОВАТЕЛЬНОСТИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ \emph{РАЦИОНАЛЬНЫХ} 
ЧИСЕЛ НА~$[0, 1)$. пРИ ВЫЧИСЛЕНИИ ТРЕБУЕТСЯ БЕСКОНЕЧНО БОЛЬШОЕ КОЛИЧЕСТВО 
ВСПОМОГАТЕЛЬНЫХ ПЕРЕМЕННЫХ~$C[a_1,~\ldots,a_r]$, ГДЕ~$r\ge 1$ И~$a_j=0$ 
ИЛИ~$1$, $1\le j \le r$. в НАЧАЛЬНЫЙ МОМЕНТ ВРЕМЕНИ ВСЕ ЭТИ ПЕРЕМЕННЫЕ 
РАВНЫ НУЛЮ.

\st[нАЧАЛЬНАЯ УСТАНОВКА~$n$.] уСТАНОВИТЬ~$n\asg 0$.

\st[нАЧАЛЬНАЯ УСТАНОВКА~$r$.] уСТАНОВИТЬ~$r\asg 1$.

\st[пРОВЕРИТЬ~$\cR_r$.] еСЛИ ЭЛЕМЕНТ~$U_n$, ДОЛЖЕН ПОПАСТЬ В 
ПОДПОСЛЕДОВАТЕЛЬНОСТЬ, ОПРЕДЕЛЯЕМУЮ~$\cR_r$, НА ОСНОВАНИИ 
ЗНАЧЕНИЙ~$U_k$, ГДЕ~$0\le k < n$, ТО НУЖНО ПРИСВОИТЬ~$a_r\asg 1$, В 
ПРОТИВНОМ СЛУЧАЕ---ПРИСВОИТЬ~$a_r\asg 0$. 

\st[$B[a_1,~\ldots, a_r]$ ПОЛНО?] еСЛИ~$C[a_1,~\ldots, a_r]<3\cdot 4^{r-1}$, 
ПЕРЕЙТИ К~\stp{6}.

\st[уВЕЛИЧИТЬ~$r$.] уСТАНОВИТЬ~$r\asg r+1$ И ВОЗВРАТИТЬСЯ К~\stp{3}.

\st[уСТАНОВИТЬ~$U_n$.] уВЕЛИЧИТЬ~$C[a_1,~\ldots, a_r]$ НА~$1$. пУСТЬ 
$k$~ЕСТЬ НОВОЕ ЗНАЧЕНИЕ~$C[a_1,~\ldots, a_r]$. уСТАНОВИТЬ~$U_n\asg V_k$, 
ГДЕ ВЕЛИЧИНА~$V_k$ ОПРЕДЕЛЕНА ВЫШЕ В ЛЕММЕ~T.

\st[уВЕЛИЧИТЬ~$n$.] уВЕЛИЧИТЬ~$n$ НА~$1$ И ВОЗВРАТИТЬСЯ К~\stp{2}.
\algend

%% 179

сТРОГО ГОВОРЯ, ЭТО НЕ ЕСТЬ АЛГОРИТМ, ПОСКОЛЬКУ ОН НЕ КОНЕЧЕН. лЕГКО, 
ОДНАКО, ИЗМЕНИТЬ ЕГО ТАК, ЧТОБЫ ОН ЗАКАНЧИВАЛСЯ, КОГДА $n$~ДОСТИГАЕТ 
ЗАДАННОЙ ВЕЛИЧИНЫ. чИТАТЕЛЮ ЛЕГЧЕ БУДЕТ ПОЧУВСТВОВАТЬ ИДЕЮ ПРИВЕДЕННОГО 
ПОСТРОЕНИЯ, ЕСЛИ ОН ПОПРОБУЕТ "ПРОКРУТИТЬ" ЕГО ВРУЧНУЮ, ЗАМЕНИВ ПРИ ЭТОМ 
ЧИСЛО~$3\cdot 4^{r-1}$ НА ШАГЕ~W4 НА~$2^r$.

аЛГОРИТМ~W НЕ ПРЕДНАЗНАЧЕН ДЛЯ ПРИМЕНЕНИЯ В КАЧЕСТВЕ ДАТЧИКА СЛУЧАЙНЫХ 
ЧИСЕЛ, ОН СЛУЖИТ ЛИШЬ ТЕОРЕТИЧЕСКИМ ЦЕЛЯМ.

\proclaim тЕОРЕМА~W. пУСТЬ~$U_n$---ПОСЛЕДОВАТЕЛЬНОСТЬ РАЦИОНАЛЬНЫХ ЧИСЕЛ, 
ОПРЕДЕЛЕННАЯ С ПОМОЩЬЮ АЛГОРИТМА~W, И~$k$---ПОЛОЖИТЕЛЬНОЕ ЦЕЛОЕ ЧИСЛО. еСЛИ 
ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>\cR_k$ БЕСКОНЕЧНА, ТО ОНА $1\hbox{-РАСПРЕДЕЛЕНА}$.

\proof пУСТЬ $A[a_1,~\ldots, a_r]$ ОБОЗНАЧАЕТ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ 
(МОЖЕТ БЫТЬ, ПУСТУЮ) ПОСЛЕДОВАТЕЛЬНОСТИ~$\<U_n>$, СОДЕРЖАЩУЮ ТЕ И ТОЛЬКО 
ТЕ ЭЛЕМЕНТЫ~$U_n$, КОТОРЫЕ ДЛЯ ВСЕХ~$j$, ТАКИХ, ЧТО~$1\le j \le r$, 
ПРИНАДЛЕЖАТ ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\<U_n>\cR_j$, ЕСЛИ~$a_j=1$, И НЕ 
ПРИНАДЛЕЖАТ ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\<U_n>\cR_j$, ЕСЛИ~$a_j=0$.

дОСТАТОЧНО ДОКАЗАТЬ, ЧТО ДЛЯ ВСЕХ~$r\ge 1$ И ВСЕХ ПАР ДВОИЧНЫХ 
ЧИСЕЛ~$a_1\ldots{}a_r$ И~$b_1\ldots{}b_r$ ИМЕЕТ МЕСТО 
РАВЕНСТВО~$\Pr(U_n \in I_{b_1\ldots{}b_r})=2^{-r}$ ПО ОТНОШЕНИЮ К 
ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$A[a_1\ldots{}a_r]$ В ТОМ СЛУЧАЕ, КОГДА ПОСЛЕДНЯЯ 
БЕСКОНЕЧНА [СМ.~\eqref[30]]. в САМОМ ДЕЛЕ, ЕСЛИ~$r\ge k$, ТО БЕСКОНЕЧНАЯ 
ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>\cR_k$ ПРЕДСТАВЛЯЕТ СОБОЙ КОНЕЧНОЕ ОБ®ЕДИНЕНИЕ 
НЕПЕРЕСЕКАЮЩИХСЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ~$A[a_1,~\ldots, a_r]$ 
ДЛЯ~$a_k=1$ И~$a_j=0$ ИЛИ~$1$ ПРИ~$1\le j \le r$, $j\ne k$; СЛЕДОВАТЕЛЬНО, 
$\Pr(U_n\in I_{b_1\ldots{}b_r})=2^{-r}$ ПО ОТНОШЕНИЮ К~$\<U_n>\cR_k$ 
(СМ.~УПР.~33). дОСТАТОЧНО ВОСПОЛЬЗОВАТЬСЯ ЕЩЕ ТЕОРЕМОЙ~A, ЧТОБЫ ПОКАЗАТЬ, 
ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ $1\hbox{-РАСПРЕДЕЛЕНА}$.

пУСТЬ $B[a_1,~\ldots, a_r]$ ОБОЗНАЧАЕТ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ 
ЭЛЕМЕНТОВ~$\<U_n>$, ДЛЯ КОТОРЫХ~$C[a_1,~\ldots, a_r]$ УВЕЛИЧИВАЕТСЯ НА 
ЕДИНИЦУ НА ШАГЕ~W6 АЛГОРИТМА. кАК ВИДНО ИЗ АЛГОРИТМА, 
$B[a_1,~\ldots, a_r]$---КОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ, МАКСИМАЛЬНОЕ ЧИСЛО 
ЭЛЕМЕНТОВ КОТОРОЙ РАВНО~$3\cdot4^{r-1}$. вСЕ ЧЛЕНЫ~$A[a_1,~\ldots, a_r]$, 
КРОМЕ КОНЕЧНОГО ИХ  ЧИСЛА,  БЕРУТСЯ  ИЗ  
ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ~$B[a_1,~\ldots, a_r,~\ldots, a_t]$, ГДЕ~$a_j=0$ 
ИЛИ~$1$ ПРИ~$r<j\le t$.

пРЕДПОЛОЖИМ ТЕПЕРЬ, ЧТО  $A[a_1,~\ldots, a_r]$ БЕСКОНЕЧНА 
И~$A[a_1,~\ldots, a_r]=\<U_{s_n}>$, ГДЕ~$s_0<s_1<s_2<\ldots{}\,$. 
еСЛИ~$N$---БОЛЬШОЕ ЦЕЛОЕ ЧИСЛО, ТАКОЕ, ЧТО~$4^r\le 4^q<N\le 4^{q+1}$, 
КОЛИЧЕСТВО ЗНАЧЕНИЙ~$k<N$, ПРИ КОТОРЫХ $U_{s_k}$~СОДЕРЖИТСЯ 
В~$I_{b_1\ldots{}b_r}$, РАВНО (ЗА ИСКЛЮЧЕНИЕМ КОНЕЧНОГО ЧИСЛА ЭЛЕМЕНТОВ В 
НАЧАЛЕ ПОДПОСЛЕДОВАТЕЛЬНОСТИ)
\EQ{
 \nu(N)=\nu(N_1)+\cdots+\nu(N_m).
}
%% 180
зДЕСЬ~$m$---КОЛИЧЕСТВО ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ~$B[a_1,~\ldots, a_t]$, 
ПЕРЕЧИСЛЕННЫХ ВЫШЕ, В КОТОРЫХ $U_s$~ПОЯВЛЯЕТСЯ ПРИ НЕКОТОРОМ~$k<N$, 
$N_j$---КОЛИЧЕСТВО ЗНАЧЕНИЙ~$k$, ПРИ КОТОРЫХ $U_{s_k}$~НАХОДИТСЯ В 
СООТВЕТСТВУЮЩЕЙ ПОДПОСЛЕДОВАТЕЛЬНОСТИ, И~$\nu(N_j)$---КОЛИЧЕСТВО ТАКИХ 
ЗНАЧЕНИЙ, КОТОРЫЕ ТАКЖЕ НАХОДЯТСЯ В~$I_{b_1\ldots{}b_r}$. тАКИМ ОБРАЗОМ, 
ИЗ ЛЕММЫ~T СЛЕДУЕТ, ЧТО
\EQ{
 \eqalign{
  \abs{\nu(N)-2^{-r}N}&=\abs{\nu(N_1)-2^{-r}N_1+\cdots+\nu(N_m)-2^{-r}N_m}\le\cr
  &\le\abs{\nu(N_1)-2^{-r}N_1}+\cdots+\abs{\nu(N_m)-2^{-r}N_m}\le\cr
  &\le m \le 1+2+4+\cdots+2^{q-r+1}<2^{q+1}.\cr
 }
}
нЕРАВЕНСТВО ОТНОСИТЕЛЬНО~$m$ СЛЕДУЕТ ИЗ ТОГО ФАКТА, ЧТО~$U_{s_N}$ 
ПРИ НАШЕМ ВЫБОРЕ~$N$ НАХОДИТСЯ В~$B[a_1,~\ldots, a_t]$ ДЛЯ 
НЕКОТОРОГО~$t\le q+1$. 

тАКИМ ОБРАЗОМ,
\EQ{
 \abs{\nu(N)/N-2^{-r}}\le 2^{q+1}/N<2/\sqrt{N}.
}
\proofend

дЛЯ ТОГО ЧТОБЫ НАКОНЕЦ ПОКАЗАТЬ СУЩЕСТВОВАНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, 
УДОВЛЕТВОРЯЮЩИХ ОПРЕДЕЛЕНИЮ~R5, ЗАМЕТИМ ПРЕЖДЕ ВСЕГО, ЧТО 
ЕСЛИ~$\<U_n>$---ПОСЛЕДОВАТЕЛЬНОСТЬ РАЦИОНАЛЬНЫХ ЧИСЕЛ НА~$[0, 1)$ И 
ЕСЛИ~$\cR$---ВЫЧИСЛИМОЕ ПРАВИЛО ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ ЧЛЕНОВ 
$b\hbox{-ИЧНОЙ}$ ПОСЛЕДОВАТЕЛЬНОСТИ, МЫ МОЖЕМ ПРЕВРАТИТЬ~$\cR$ В 
ВЫЧИСЛИМОЕ ПРАВИЛО~$\cR'$ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТИ 
ЧЛЕНОВ~$\<U_n>$, ПОЛОЖИВ~$f'_n(x_1,~\ldots, x_n)$ В~$\cR'$ 
РАВНЫМ~$f_n(\floor{bx_1},~\ldots, \floor{bx_n})$ В~$\cR$. еСЛИ 
ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>\cR'$ РАВНОМЕРНО РАСПРЕДЕЛЕНА, ТО ЭТИМ ЖЕ 
СВОЙСТВОМ ОБЛАДАЕТ И~$\<\floor{bU_n}>\cR$. мНОЖЕСТВО ВСЕХ ВЫЧИСЛИМЫХ 
ПРАВИЛ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ $b\hbox{-ИЧНЫХ}$ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПРИ ВСЕХ ЗНАЧЕНИЯХ~$b$ СЧЕТНО (ПОСКОЛЬКУ СУЩЕСТВУЕТ 
ЛИШЬ СЧЕТНОЕ КОЛИЧЕСТВО ЭФФЕКТИВНЫХ АЛГОРИТМОВ), ПОЭТОМУ ЕГО ЭЛЕМЕНТЫ 
МОЖНО ПЕРЕЧИСЛИТЬ В ВИДЕ НЕКОТОРОЙ ПОСЛЕДОВАТЕЛЬНОСТИ~$\cR_1$, 
$\cR_2$,~$\ldots\,$. оТСЮДА СЛЕДУЕТ, ЧТО АЛГОРИТМ~W ОПРЕДЕЛЯЕТ 
ПОСЛЕДОВАТЕЛЬНОСТЬ НА~$[0, 1)$, КОТОРАЯ ЯВЛЯЕТСЯ СЛУЧАЙНОЙ В СМЫСЛЕ 
ОПРЕДЕЛЕНИЯ~R5.

тЕПЕРЬ МЫ ОКАЗАЛИСЬ В НЕСКОЛЬКО ПАРАДОКСАЛЬНОМ ПОЛОЖЕНИИ. кАК ОТМЕЧАЛОСЬ 
РАНЬШЕ, ЭФФЕКТИВНЫЙ АЛГОРИТМ, КОТОРЫЙ ОПРЕДЕЛЯЛ БЫ ПОСЛЕДОВАТЕЛЬНОСТЬ, 
УДОВЛЕТВОРЯЮЩУЮ ОПРЕДЕЛЕНИЮ~R4, СУЩЕСТВОВАТЬ НЕ МОЖЕТ, И ПО ТОЙ ЖЕ 
ПРИЧИНЕ НЕ МОЖЕТ СУЩЕСТВОВАТЬ ЭФФЕКТИВНЫЙ АЛГОРИТМ, ОПРЕДЕЛЯЮЩИЙ 
ПОСЛЕДОВАТЕЛЬНОСТЬ, УДОВЛЕТВОРЯЮЩУЮ ОПРЕДЕЛЕНИЮ~R5. дОКАЗАТЕЛЬСТВО 
СУЩЕСТВОВАНИЯ ТАКОЙ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ПО НЕОБХОДИМОСТИ ДОЛЖНО 
БЫТЬ НЕКОНСТРУКТИВНЫМ. кАКИМ ЖЕ ОБРАЗОМ ЭТА ПОСЛЕДОВАТЕЛЬНОСТЬ 
ПОЛУЧАЕТСЯ ПО АЛГОРИТМУ~W?

пРОТИВОРЕЧИЯ ЗДЕСЬ НЕТ. дЕЛО В ТОМ, ЧТО НЕВОЗМОЖНО С ПОМОЩЬЮ 
ЭФФЕКТИВНОГО АЛГОРИТМА ПРОНУМЕРОВАТЬ МНОЖЕСТВО ВСЕХ АЛГОРИТМОВ. дРУГИМИ 
СЛОВАМИ, ЭФФЕКТИВНЫЙ АЛГОРИТМ, КОТОРЫЙ
%% 181
\bye