\documentclass[12pt,a4paper]{article}
\usepackage[indentheadings]{russcorr}
%\makeatletter
%\renewcommand{\@makefnmark}{}
%\makeatother
\frenchspacing %%
\hfuzz=2pt
\tolerance=900


\begin{document}

\begin{center}
{\bf 40 YEARS OF THE ORIGIN OF KOLMOGOROV RANDOMNESS THEORY}

\vspace{5mm}
{\large\it A.L. Semenov, An.A. Muchnik}
\footnote{
Institute of New Technologies,
10 Nizhnyaya Radishevskaya,
Moscow, 109004, Russia.

Phone: +7(095)9156296.

Fax: +7(095)9156963.

E-mail: alsemenov@mtu-net.ru, muchnik@lpcs.math.msu.ru
}

\vspace{5mm}
{\large Institute of New Technologies}
\end{center}

\vspace{15mm}

\subsection*{Введение}

Разработка Колмогоровым того, что ныне
называется \glqq колмогоровской сложностью\grqq,
началась с его статьи~\cite{Kolm63}.
Мы развиваем этот подход; в частности,
мы решаем проблему нахождения точных оценок
сложности частотных тестов случайности.


Как писал Колмогоров (\cite{Kolm63}),\?
%% уточнить цитату по русскому переводу статьи
\glqq теоретико-множественная аксиоматика
теории вероятностей \ldots{}
разрешила большинство формальных трудностей \ldots{}
настолько успешно, что проблема поиска
обоснования практических применений \ldots{}
стала казаться второстепенной многим исследователям.\grqq

Мы рассматриваем простейшую ситуацию последовательности
испытаний с исходами $\{0,1\}$
и хотим проверить, что цифры появляются независимо
с вероятностями $1/2$.
В качестве критерия этого фон Мизес (\cite{mises})
предложил близость частоты нулей к $1/2$
в самой последовательности и во всех е\"е
подпоследовательностях, выбранных допустимыми правилами.
Понятие допустимого правила было уточнено
Ч\"ерчем (\cite{chur}).
И фон Мизес, и Ч\"ерч говорили
о бесконечных последовательностях.
Колмогоров в~\cite{Kolm63} предложил сво\"е понятие
допустимого правила для конечных последовательностей\footnote{
Естественный аналог этого понятия
для бесконечных последовательностей
инвариантен относительно вычислимых перестановок
цифр последовательности.}
and сформулировал такое (частотное) определение
случайности конечной последовательности:
частоты нулей нулей и единиц во всех достаточно длинных
подпоследовательностях, выбранных достаточно простыми
правилами близки к $1/2$.
Конечно, мы должны заменить слова
\glqq достаточно длинные\grqq,
\glqq достаточно простые\grqq,
\glqq близки\grqq{}
на конкретные оценки
(которые могут зависеть от длины исходной
последовательности).
Проблема из~\cite{Kolm63},
которая решена авторами (Теорема~4),
заключалась в нахождении точных оценок
для основных параметров, при которых
существуют случайные последовательности.

Обсудим язык, на котором мы будем ставить и решать
интересующие нас задачи.
Построение теории информации было начато Шенноном
на основе теории вероятностей.
Однако существуют разные ситуации,
когда разумно поставить вопрос о количестве информации
в конкретном объекте, но не видно, как эту информацию
можно связать с каким-нибудь распределением
вероятностей.
Другой (комбинаторный) подход состоит в рассмотрении
какого-то свойства объекта.
Пусть, например, нас интересует свойство объекта
$\mathbf t$ \glqq быть двоичной
последовательностью длины $L$, в которой доля нулей
заключена между числами $p$ и $q$\grqq.
Это свойство имеет смысл независимо от каких бы то
ни было вероятностных предположений.
Если $L$, $p$, $q$ известны заранее,
то неформально количеством информации в $\mathbf t$
можно назвать
$$
\left\lceil \log_2 \left(
C_{L}^{\lceil pL\rceil}+C_{L}^{\lceil pL\rceil+1}+
\ldots+C_{L}^{\lfloor qL\rfloor}
\right) \right\rceil
$$
(столько битов требуется для двоичной записи
номера элемента во множестве всех объектов,
удовлетворяющих указанному свойству).
Заметим, что один объект обладает разными свойствами.
К примеру, $\mathbf t$ имеет свойство
\glqq быть равным $\mathbf t$\grqq.
Поэтому фактически при комбинаторном подходе
количество информации приписывается не объектам,
а свойствам.

Принципиальным достоинством алгоритмического подхода,
предложенного А.\,Н.\,Колмогоровым,
является определение для каждых отдельно взятых
конструктивных объектов $\mathbf t$, $\mathbf s$
количества информации $K(\mathbf t|\mathbf s)$,
необходимой для нахождения $\mathbf t$ при известном
$\mathbf s$.
Если $\mathbf s$~--- пустое слово, мы получаем количество
информации в $\mathbf t$ (обозначаемое $K(\mathbf t)$).
Основное соотношение для энтропии Шеннона
(применяемой к распределениям вероятностей)
$$
H(\langle x,y\rangle)=H(x)+H(y|x)
$$
выполнено по теореме Колмогорова--Левина с очень большой
точностью и для функции $K$ (названной Колмогоровым
энтропией конструктивных объектов):
\begin{equation}\label{eq:main}
K(\langle \mathbf t, \mathbf s\rangle)=
 K(\mathbf t)+K(\mathbf s|\mathbf t)+
 O(\log_2(K(\langle \mathbf t, \mathbf s\rangle)))\,.
\end{equation}
Колмогоров доказал невычислимость функции $K$.
Изучались и некоторые способы определения вычислимой
энтропии, но для них не удалось доказать
основное соотношение~(\ref{eq:main}).

Как важное свойство энтропии
Колмогоров отметил следующее.
Пусть $\mathbf t$~--- двоичная последовательность длины $L$,
тогда
\begin{equation}\label{eq:impl}
\begin{array}{c}
\mbox{$K(\mathbf t|L)$ не намного меньше $L$}\\[2ex]
\Downarrow\\[1ex]
\parbox{0.8\textwidth}{част\'оты нулей и единиц во
всех достаточно длинных
подпоследовательностях, выбранных из $\mathbf t$ достаточно
простыми правилами, близки к $1/2$.}
\end{array}
\end{equation}
(Конечно, следует заменить выражения
``не намного меньше'', ``достаточно длинные'',
``достаточно простые'', ``близки'' на конкретные оценки.)
Замечательно, что импликацию~(\ref{eq:impl})
можно обратить (см. теорема~1$'$).
Таким образом, устойчивость частот при переходе
к подпоследовательностям является не только необходимым,
но и достаточным признаком случайности.
Подчеркн\"ем, что для получения этого результата
нужно рассматривать подпоследовательности,
цифры которых выбирались не обязательно в том порядке,
в котором они стояли в исходной последовательности
(см. теорема~3$'$).
Использованное нами определение немонотонных правил выбора
было введено Колмогоровым в~\cite{Kolm63}.

Колмогоров писал в~\cite{KolmU}:
\glqq Теория информации должна предшествовать
теории вероятностей, а не опираться на не\"е.
Основы теории информации имеют по самому существу
этой дисциплины финитный комбинаторный характер.
\ldots{}
Естественно, что такой подход к делу не мешает тому,
чтобы теория вероятностей как часть математики развивалась
как специализация общей теории меры.\grqq{}
Формулировки всех теорем нашей работы строго финитны,
но их доказательства (которые опубликованы в~\cite{MS}),
будучи столь же финитными по сути,
используют для упрощения изложения вероятностные рассуждения
(так же, как интегралы и другие понятия бесконечной математики).

Наша статья разделена на две части,
соответствующие комбинаторному и алгоритмическому подходам
к теории информации (в смысле~\cite{Kolm65}).
Для каждой теоремы комбинаторной части в алгоритмической
части есть теорема (имеющая тот же номер со штрихом),
в которой изучается близкий вопрос,
сформулированный на языке другого подхода.

\subsection*{Комбинаторный подход}

Мы рассматриваем проблему определения меры случайности
конечной двоичной последовательности
относительно бернуллиевского распределения.
Иногда некоторое интуитивное понятие
может быть формализовано разными способами.
(Например, есть различные неэквивалентные
определения размерности компакта.)
Интуитивно, последовательность
$\mathbf t$ длины $L$
можно назвать неслучайной, если кто-нибудь,
кому известно $L$, но неизвестно $\mathbf t$,
укажет множество последовательностей длины $L$,
содержащее $\mathbf t$ и имеющее достаточно малую меру.
Такие множества называются тестами.
При $\epsilon > 0$
закону больших чисел соответствует тест,
состоящий из последовательностей,
в которых доля нулей отстоит от $1/2$
более чем на $\epsilon$.
С точки зрения таких тестов
интуитивно неслучайная последовательность $01010101\ldots$
оказывается максимально случайной.
Чтобы уйти от этой трудности,
Колмогоров определил понятие правила выбора
подпоследовательности
и каждой паре
$\langle\mbox{\it правило, }\epsilon\rangle$
сопоставил тест, соответствующий закону больших чисел.

\emph{Правилом выбора $r$ на последовательностях длины $L$}
называется пара функций $\langle r^1, r^2\rangle$,
определ\"енных на двоичных последовательностях
длины от $0$ до $L-1$.
Значения $r^1$ принадлежат $\{1,\ldots,L\}$,
прич\"ем на последовательности и
на е\"е собственном продолжении
значения всегда различны.
Значения $r^2$ принадлежат
$\{\mbox{``S''}, \mbox{``N''}\}$.
Пусть фиксирована последовательность
$\mathbf t=t_1\ldots t_L$.
Для каждого $i$ от $0$ до $L$ построим индукцией по $i$
последовательности $\mathbf u_i$ и $\mathbf s_i$.
Положим $\mathbf u_0=\mathbf s_0=\Lambda$,
$\mathbf u_{i+1}=\mathbf u_i t_{r^1(\mathbf u_i)}$,
и если $r^2(\mathbf u_i)=\mbox{``N''}$,
то $\mathbf s_{i+1}=\mathbf s_i$,
а если $r^2(\mathbf u_i)=\mbox{``S''}$,
то $\mathbf s_{i+1}=\mathbf s_i t_{r^1(\mathbf u_i)}$.

Говорим, что правило $r$ выбрало из $\mathbf t$
подпоследовательность $\mathbf s_L$,
обозначаемую $r[\mathbf t]$.

Иногда полезно рассматривать более узкие классы правил.
В \emph{монотонных правилах} $r^1(\mathbf u_i)$
всегда равно $i+1$.
\emph{Неадаптивные правила}~--- такие монотонные правила,
в которых $r^2(\mathbf u_i)$ зависит только от $i$.

Каждой длине $L$, правилу $r$ и числу $\epsilon>0$
сопоставляется \emph{частотный} тест,
состоящий из последовательностей $\mathbf t$
длины $L$,
у которых доля нулей в $r[\mathbf t]$
отстоит от $1/2$ не менее чем на $\epsilon$.
Частотный тест, порожд\"енный монотонным
(неадаптивным) правилом,
сам будет называться монотонным (неадаптивным).

Сводимость всякого закона теории вероятностей
к закону больших чисел в самой сильной форме
означала бы,
что произвольный тест можно вложить
в частотный тест не слишком б\'ольшего размера.
Рассмотрим простой пример.
Каждую двоичную последовательность
ч\"етной длины $L$ будем также представлять
как последовательность пар двоичных цифр
длины $L/2$.
Пусть $\epsilon<1/4$;
интересующий нас тест $V$
состоит из тех последовательностей,
для которых в соответствующей последовательности пар
доля вхождений $00$
отстоит от $1/4$ не менее чем на $\epsilon$.
То есть мы имеем дело с законом больших чисел,
но для другого распределения вероятностей
(бернуллиевского с четырьмя равновероятными исходами).
Как доказал Вилль,
этот тест не вкладывается ни в какой
монотонный тест,
порожд\"енный правилом,
у которого длины выборок всегда больше
$1/\epsilon$.
Естественность требования,
чтобы выборки были не слишком короткими,
видна из самого названия закона больших чисел
(например, в выборке длины единица отклонение
доли нулей от $1/2$ всегда равно $1/2$).

Докажем сделанное про тест $V$ утверждение.
Пусть дано монотонное правило $r$.
Построим по очереди цифры последовательности
$\mathbf t=t_1\ldots t_L$.
Мы используем обозначения $\mathbf u_i$
и $\mathbf s_i$ из определения $r[\mathbf t]$.
Предположим, что $\mathbf u_i$ уже построено.
Если $r^2(\mathbf u_i)=\mbox{``N''}$,
то $t_{i+1}=1$.
Если $r^2(\mathbf u_i)=\mbox{``S''}$,
то $t_{i+1}$ отличается от последней цифры
$\mathbf s_i$ и
$t_{i+1}=1$, когда $\mathbf s_i=\Lambda$.

С одной стороны, в последовательности пар,
соответствующей построенному $\mathbf t$,
нет ни одного вхождения $00$
(то есть с точки зрения закона больших чисел
для четыр\"ех исходов $\mathbf t$
очень неслучайна).
С другой стороны,
выборка $r[\mathbf t]$ имеет вид $1010101\ldots$
(то есть случайна с точки зрения
закона больших чисел для двух исходов).

Однако уже двух монотонных тестов
(не слишком больших по размеру)
достаточно, чтобы вложить $V$ в их объединение.
В дальнейшем построении обозначим эти тесты $F_1$ и $F_2$.
Тест $F_1$ является даже неадаптивным.
Порождающее его правило $r_1$
включает в выборку все цифры, стоящие на неч\"етных местах
(то есть
$r_1^2(\mathbf u_i)=\mbox{``S''}
\:\Leftrightarrow\:
i$ ч\"етно).
Монотонное правило $r_2$
включает в выборку цифры, стоящие на ч\"етных местах,
у которых предшествующая цифра равна нулю
(то есть
$r_2^2(\mathbf u_i)=\mbox{``S''}
\:\Leftrightarrow\:
[i$~неч\"етно и $t_i=0]$).
Для того, чтобы обеспечить достаточно большую длину
всех выборок, рассмотрим следующее монотонное правило
$\bar r_2$.
Пусть $\nu(\mathbf u)$~--- количество нулей,
стоящих на неч\"етных местах в слове $\mathbf u$.
Тогда
${\bar r_2^2(\mathbf u_i)=\mbox{``S''}}
\:\Leftrightarrow\:
\bigl[ {r_2^2(\mathbf u_i)=\mbox{``S''}}$ или
[$i$ неч\"етно и
 $\nu(\mathbf u_i)+(L-i)/2\le L/5]\bigr]$.

Как показывает простая проверка,
если паре
 $\langle r_1,\epsilon(1-\epsilon)\rangle$
сопоставить тест $F_1$,
а  паре
 $\langle \bar r_2,\epsilon(1-\epsilon)\rangle$
  сопоставить тест $F_2$,
то $V\subseteq F_1\cup F_2$.
При этом
для $L > 34/\epsilon^3$
$$
| F_1\cup F_2| <
   2^L\cdot\mathrm e^{-L\epsilon^2/5}\,.
$$
Отметим, что тест, соответствующий закону
больших чисел для последовательности длины $L$,
тоже имеет размер порядка $2^{(1-\delta)L}$.


Теперь построим один немонотонный тест $G$,
небольшой по размеру и содержащий $V$.
Неформально говоря,
правило $r$, порождающее тест $G$,
состоит в последовательном
применении правил $r_1$ и $r_2$.
Первая компонента правила $r$
зависит только от длины аргумента.
А именно,
$$
r^1(\mathbf u)=\left\{
\begin{array}{ll}
 2\ell(\mathbf u)+1   & \mbox{ при } \ell(\mathbf u) < L/2\,,\\
 2\ell(\mathbf u)-L+2  & \mbox{ при } \ell(\mathbf u) \ge L/2\,.
\end{array}
\right.
$$
При $\ell(\mathbf u)<L/2$ всегда
$r^2(\mathbf u)=\mbox{``S''}$.
Пусть $\ell(\mathbf u) \ge L/2$.
Обозначим через $\mathbf w$ начало длины $L/2$
слова $\mathbf u$.
Если доля нулей в $\mathbf w$ отклоняется от $1/2$
более чем на $\epsilon/8$,
то $r^2(\mathbf u)=\mbox{``N''}$.
Иначе полагаем
$r^2(\mathbf u)=\mbox{``S''}
\:\Leftrightarrow\:$
цифра $\mathbf u$ с номером
$(\ell(\mathbf u)-L/2+1)$
равна нулю.

Ясно, что длина $r[\mathbf t]$ всегда
не меньше $L/2$.
Просто проверить, что
если тест $G$ сопоставить паре
 $\langle r,\epsilon/8\rangle$,
то $V\subseteq G$.
При этом
для $L > 256/\epsilon^3$
$$
|G| < 2^L\cdot\mathrm e^{-L\epsilon^2/128}\,.
$$

Прежде чем от рассмотренного примера
перейти к произвольным тестам
мы должны выбрать удобную шкалу для измерения
``малости'' теста.
(Выбор подходящей шкалы может делать математические
утверждения более наглядными, а иногда и более
информативными.
Например, в центральной предельной теореме
естественной единицей измерения для отклонения частоты
от вероятности является
$[\mbox{количество испытаний}]^{-1/2}$.)

\emph{Удельным дефектом} теста $U$, состоящего
из последовательностей дли\-ны $L$,
называется величина $1-\frac{\log_2 |U|}{L}$.

Заметим, что эта же единица измерения используется
во многих результатах теории кодирования.

В новых терминах можно сказать, что для больших $L$
тест $V$ из примера Вилля имеет удельный дефект
приблизительно $\frac{4}{3\ln 2}\epsilon^2$,
а покрывающий его частотный тест $G$
имеет удельный дефект больше
$\frac{1}{128\ln 2}\epsilon^2$.

Постановка разбираемых далее задач естественно
вписывается в контекст комбинаторной математики,
где исследуются такие вопросы, как
``\emph{Чему равен минимальный диаметр шара, которым можно
покрыть произвольное множество диаметра $1$?}'',
``\emph{Каково минимальное количество шаров диаметра $1$,
которыми можно покрыть произвольное множество
диаметра $1$?}''
и т.\,д.

Авторами доказан следующий результат
(см.~\cite[теорема~4]{MS}).

\par\smallskip\noindent
\textbf{Теорема 1. }{\it
Для каждого достаточно малого положительного
$\delta$
можно указать натуральное число $R(\delta)$,
для которого выполнено следующее.
Для любого теста $U$ из последовательностей длины
$L > (1/\delta)^5$
если удельный дефект $U$ больше $\delta$,
то существует $R(\delta)$
монотонных частотных тестов,
объединение которых покрывает $U$
и имеет удельный дефект больше
$$
\frac{\delta}{\ln(1/\delta)}(1-\beta(\delta))\,,
$$
где $\beta(\delta)\to 0$ при $\delta\to 0$.
}
\par\smallskip

Как видно из формулировки,
количество тестов в покрытии не зависит от $L$.
Конструкция Вилля
из~\cite{ville} (упрощ\"енный вариант которой
был разобран нами выше)
показывает, что теорему~1 нельзя усилить, заменив
$R(\delta)$
на константу.

\noindent
\textbf{Открытая проблема:}
сохранится ли утверждение теоремы~1,
если заменить $R(\delta)$ на константу
и убрать требование монотонности частотных тестов?

Авторы доказали, что оценка на удельный дефект покрытия
в теореме~1 близка к точной (см.~\cite[теорема~5]{MS}).

\par\smallskip\noindent
\textbf{Теорема 2. }{\it
Для каждого достаточно малого положительного
$\delta$
можно указать натуральное число $R(\delta)$,
для которого выполнено следующее.
Для любого $L > (1/\delta)^5$
существует такой тест $U$
из последовательностей длины $L$, что
удельный дефект $U$ больше $\delta$ и
всякое покрытие $U$ частотными тестами
с удельным дефектом больше
$$
\frac{2\delta}{\ln(1/\delta)}
$$
состоит более чем из
$\mathrm{e}^{L/R(\delta)}$
тестов.
}
\par\smallskip

Отметим, что в теореме~2 даже нет требования
монотонности частотных тестов.

Авторами доказано, что теорему~1 нельзя усилить,
заменив требование монотонности частотных тестов
на требование неадаптивности (см.~\cite[теорема~6]{MS}).

\par\smallskip\noindent
\textbf{Теорема 3. }{\it
Для любого $\sigma > 0$ и для любого
$L > 12+6\log_2(1/\sigma)$
существует такой тест $U$
из последовательностей длины $L$, что
удельный дефект $U$ не меньше $1/3$
и
всякое покрытие $U$
неадаптивными частотными тестами
с удельным дефектом не меньше $\sigma$
состоит не менее чем из
$2^{\sigma L/2}$
тестов.
}
\par\smallskip

Обратимся теперь к вопросу о датчиках
(таблицах) случайных чисел,
который был поставлен в статье Колмогорова~\cite{Kolm63}.

Пусть $\mathcal{R}_L$~--- некоторое
множество правил на последовательностях дли\-ны $L$.
Последовательность $\mathbf t$ длины $L$ называется
\emph{$(n,\epsilon)$-датчиком случайных чисел для
$\mathcal{R}_L$}, если
каждое правило из $\mathcal{R}_L$
выбирает в $\mathbf t$ подпоследовательность
$r[\mathbf t]$ с таким свойством:
\begin{itemize}
\item
при условии, что длина подпоследовательности не меньше $n$,\\
доля нулей в ней отличается от
$1/2$ менее чем на $\epsilon$.
\end{itemize}

Каждой длине $L$ и правилу $r$
сопоставляется \emph{$(n,\epsilon)$-тест},
состоящий из последовательностей $\mathbf t$
длины $L$,
у которых $\ell(r[\mathbf t])\ge n$ и
доля нулей в $r[\mathbf t]$
отстоит от $1/2$ не менее чем на $\epsilon$.

Колмогорова интересовало, для какого количества правил
заведомо существует $(n,\epsilon)$-датчик.
Перевед\"ем это на язык покрытий:
каким количеством $(n,\epsilon)$-тестов
можно покрыть множество всех последовательностей
длины $L$?
Колмогоров доказал в~\cite{Kolm63},
что при естественных ограничениях на $n$, $\epsilon$
это количество меньше
$\mathrm{e}^{2n\epsilon^2(1-\epsilon)}$
и больше
$2^{4n\epsilon(1+5\epsilon)}$
(точные формулировки и полные доказательства
см.~\cite[теоремы~1,2]{MS}).
Поставленная Колмогоровым проблема состояла в устранении
разрыва между степенями $\epsilon$ в привед\"енных оценках.
Авторы доказали, что верхняя оценка Колмогорова
близка к точной (см.~\cite[теорема~3]{MS}).

\par\smallskip\noindent
\textbf{Теорема 4. }{\it
Пусть $n$~--- целое положительное число
и $\epsilon\in(0,1/3)$.
Если $2n\le L\le 2^{n\epsilon^3/2}$,
то множество всех последовательностей длины $L$
можно покрыть $(n,\epsilon)$-тестами
в количестве
\begin{equation}\label{eq:th4}
\mathrm{e}^{2n\epsilon^2(1+\epsilon)/(1-n/(L-1))}\,.
\end{equation}
}

Наличие в последней теореме условия
$L\ge 2n$ и члена ${(1-n/(L-1))}$
в формуле~(\ref{eq:th4})
неудивительно, так как всякая последовательность
с одинаковым количеством нулей и единиц
не принадлежит ни одному \mbox{$(n,\epsilon)$-тесту}
при $L< n(1+2\epsilon)$.

Следует заметить, что Колмогоров для своей нижней оценки
явно построил покрывающее семейство тестов.
Наше же доказательство вероятностное.
Ситуация, когда вероятностное доказательство
да\"ет лучшую оценку, чем все известные явные построения,
далеко не в первый раз встречается в теории информации
(например, теорема Шеннона о помехоустойчивом кодировании).

Сейчас мы опишем в самом общем виде полезный в теории информации
при\"ем, примен\"енный в теореме~4.
Рассмотрим конечное множество $A$ и
семейство $B$ подмножеств $A$
(обозначим $a=|A|$, $b=|B|$).
Пусть каждый элемент из $A$ принадлежит по крайней мере
$c>0$
множествам из $B$. Тогда в $B$ существует подсемейство
мощности $\lceil(b/c)\ln a\rceil$, покрывающее вс\"е $A$.
Выберем случайно
(относительно равномерного на $B$ распределения)
элемент из $B$, и повторим эту операцию независимо
$\lceil(b/c)\ln a\rceil$ раз
(в выборке могут оказаться повторения).
Фиксируем $x\in A$.
Вероятность того, что один случайный элемент из $B$
покроет $x$, не меньше $c/b$.
Вероятность противоположного события не больше $1-c/b$.
Вероятность того, что ни один из элементов выборки
не покроет $x$, не больше
$(1-c/b)^{\lceil(b/c)\ln a\rceil}$.
Вероятность того, что хотя бы один элемент из $A$
не покрыт множествами из выборки не больше
$a\cdot(1-c/b)^{(b/c)\ln a} < 1$,
поскольку $(1-c/b)^{b/c} < \mathrm{e}^{-1}$.
Тем самым вероятность того, что
выборка покроет вс\"е $A$, положительна,
и следовательно, искомое подсемейство в $B$ существует.


\subsection*{Алгоритмический подход}

В алгоритмическом подходе\footnote{
Переменные, которые в комбинаторном подходе
принимали вещественные значения,
в алгоритмическом подходе
принимают только рациональные значения.
}
каждой паре $L$, $\delta$ сопоставляется ровно один
(в отличие от комбинаторного подхода)
тест $U_{L,\delta}$ из последовательностей длины $L$,
имеющий удельный дефект больше $\delta$.
Он состоит из всех последовательностей длины $L$,
у которых при известном $L$ условная энтропия
меньше $L(1-\delta)$.
Неформально говоря, $U_{L,\delta}$ содержит
последовательности, которые могут быть сжаты
без потери информации в $(1-\delta)$ раз.

Мы должны ввести понятия
\emph{алгоритмического правила выбора}
и \emph{алгоритмического частотного теста},
которые являются алгоритмическими аналогами
для понятий правила выбора и частотного теста.
Необходимость этих новых понятий будет мотивирована ниже.
Алгоритмическим правилом выбора $r$ на
последовательностях длины $L$
называется программа, вычисляющая пару
частичных функций $\langle r^1, r^2\rangle$,
определ\"енных на двоичных последовательностях
длины от $0$ до $L-1$.
Значения $r^1$ принадлежат
$\{1,\ldots,L\}$, прич\"ем на последовательности и
на е\"е собственном продолжении значения всегда различны.
Значения $r^2$ принадлежат
$\{\mbox{``S''}, \mbox{``N''}\}$.
Пусть фиксирована последовательность
$\mathbf t=t_1\ldots t_L$.
Последовательности $\mathbf u_i$ и $\mathbf s_i$
строятся так же, как и в определении
(не алгоритмического) правила выбора.
Если для какого-нибудь $i$ значение
$r^1(\mathbf u_i)$ или $r^2(\mathbf u_i)$
неопределено, то подпоследовательность
$r[\mathbf t]$ тоже неопределена,
иначе $r[\mathbf t]=\mathbf s_L$.

Каждой длине $L$, алгоритмическому правилу $r$
и $\epsilon>0$
сопоставляется алгоритмический частотный тест,
состоящий из последовательностей $\mathbf t$
длины $L$, для которых $r[\mathbf t]$ определено
и доля нулей в $r[\mathbf t]$
отстоит от $1/2$ не менее чем на $\epsilon$.

В алгоритмическом подходе для каждой пары
$R$, $\sigma$
исследуется вопрос о том, покрывается ли
$U_{L,\delta}$
фиксированным (в отличие от комбинаторного подхода) семейством
$\mathcal{F}_{L,R,\sigma}$.
Это семейство состоит из всех алгоритмических частотных
тестов с удельным дефектом больше $\sigma$,
порожд\"енных алгоритмическими правилами,
у которых при известном $L$
условная энтропия меньше $\log_2 R$
(количество таких правил меньше $R$).

Если бы тот же вопрос о покрытии исследовался
для (не алгоритмических) частотных тестов,
то во всех интересных случаях
ответ оказался бы отрицательным.
Действительно, частотные тесты~---
это конструктивные объекты.
Рассмотрим частотные тесты $G$,
которые состоят из последовательностей длины $L$,
имеют удельный дефект больше $\sigma$
и $K(G|L)< \log_2 R$.
Пусть даны числа $L$, $R$, $\sigma$
и известно количество соответствующих
частотных тестов $G$.
Если существует последовательность
$\mathbf t$ длины $L$,
не принадлежащая объединению этих частотных тестов,
то е\"е можно найти перебором.
Условная энтропия $\mathbf t$ при известном $L$ не зависит
от $L$, следовательно, при больших $L$ тест $U_{L,\delta}$
содержит $\mathbf t$.

Доказательства следующих двух наших результатов
см.~\cite[теоремы~4$'$,\,5$'$\,]{MS}.

\par\smallskip\noindent
\textbf{Теорема 1$'$. }{\it
Для каждого достаточно малого $\delta > 0$
существует такое $L_0$, что для любого натурального
$L > L_0$,
$R=(1/\delta)^{4\ln 2/\delta}$ и
\mbox{$\sigma=\frac{\delta}{\ln(1/\delta)}(1-\beta(\delta))$},
где $\beta(\delta)$~--- фиксированная функция,
стремящаяся к $0$ при $\delta\to 0$,
выполнено
$$
U_{L,\delta}\subseteq
  \bigcup\mathcal{F}_{L,R,\sigma}\,.
$$
}

\par\smallskip\noindent
\textbf{Теорема 2$'$. }{\it
Для каждого достаточно малого $\delta>0$,
натурального \mbox{$L > (1/\delta)^5$},
$R=2^{L\delta^4/70}$ и
$\sigma=\frac{2\delta}{\ln(1/\delta)}(1+3\delta)$
выполнено
$$
U_{L,\delta}\not\subset
  \bigcup\mathcal{F}_{L,R,\sigma}\,.
$$
}

Обратим внимание, что в теореме~1$'$,
в отличие от теоремы~1, частотные тесты
из покрывающего семейства порождаются
не только монотонными правилами.
Это обстоятельство неустранимо,
как показывает следующий доказанный авторами
результат (см.~\cite[теорема~6$'$]{MS}).

Обозначим через $\mathcal{M}_{L,R,\sigma}$
семейство всех алгоритмических частотных
тестов с удельным дефектом больше $\sigma$,
порожд\"енных алгоритмическими
монотонными правилами,
у которых при известном $L$
условная энтропия меньше $\log_2 R$.

\par\smallskip\noindent
\textbf{Теорема 3$'$. }{\it
Для каждого достаточно большого натурального $L$,
числа ${\delta = 1/\sqrt{L}}$ и
$R=2^{\sqrt{L}/4}$
выполнено
$$
U_{L,1/2}\not\subset
  \bigcup\mathcal{M}_{L,R,\delta}\,.
$$
}\par\smallskip

Проблема Колмогорова из~\cite{Kolm63}
при алгоритмическом подходе решается так
(см.~\cite[теорема~3$'$]{MS}).
\par\smallskip\noindent
\textbf{Теорема 4$'$. }{\it
Пусть $n$~--- целое положительное число
и рациональное  \mbox{$\epsilon\in(0,1/3)$}.
Если $2n\le L\le 2^{n\epsilon^3/2}$,
то множество всех последовательностей длины $L$
можно покрыть $(n,\epsilon)$-тестами,
порожд\"енными неадаптивными правилами,
у которых
при известных $L$, $n$, $\epsilon$
условная энтропия меньше
$$
(2/\ln 2)\,n\epsilon^2\frac{1+\epsilon}{1-n/L}+C\,,
$$
где $C$~--- константа, зависящая только
от выбора оптимального языка программирования.
}

\subsection*{Заключение}

Как известно, Андрей Николаевич Колмогоров в России
и Рэй Соломонофф в США независимо
пришли к основным понятиям и фактам,
касающимся сложности конечных объектов,
в середине 60-тых годов.
В 60-е и 70-е годы исследования в этой области
велись в основном учениками Колмогорова и
членами московского математического сообщества,
обосновавшегося в
Московском государственном университете (им.~Ломоносова):
Л.\,Левиным, В.\,Вьюгиным, А.\,Звонкиным,
Н.\,Петри, П.\,Гачем.
Г.\,Чэйтин вн\"ес существенный вклад в популяризацию
этой теории на западе;
повлияла на исследования в России и рукопись Соловэя.

С конца 70-х годов до своей смерти в 1987 году
Колмогоров был заведующим кафедрой математической логики.
Сейчас е\"е возглавляет его бывший студент
Владимир Андреевич Успенский,
который также работает в области колмогоровской сложности.
В самом начале своей работы в качестве заведующего нашей кафедрой
профессор Колмогоров предложил первому из авторов настоящей статьи
начать семинар по сложности.
(Сейчас он называется колмогоровским семинаром по сложности
определений и вычислений.)
С первых шагов работы семинара сложилась традиция
заслушивать на н\"ем иссследовательские сообщения
и обзоры ещ\"е и по практическому программированию
и сложности алгоритмов.
В своих первых докладах на семинаре Колмогоров
представил программу исследований по частотному подходу
к случайности и другим темам.
Эта программа реализовывалась в работах
В.\,Вовка, А.\,Шеня, Н.\,Верещагина, Ан.\,Мучника и других.
В последующие годы к руководству семинаром
присоединились А.\,Шень и Н.\,Верещагин,
ставшие его основной движущей силой
после смерти Колмогорова.
Большой вклад в развитие семинара вн\"ес
профессор Успенский.
В пленарном докладе Колмогорова и Успенского
на бернуллиевском конгрессе
были подведены итоги работы московской группы
за вс\"е то время,
что е\"е возглавлял Колмогоров.

Основное содержание настоящей статьи было доложено
на колмогоровском семинаре весной 2002 года.

\subsection*{Acknowledgments}

Авторам очень важно общение с участниками
Колмогоровского семинара.
Особую признательность мы выражаем
Николаю Константиновичу Верещагину,
интересные обсуждения с которым
вопросов колмогоровской теории
послужили для нас одним из стимулов
начать настоящую работу.
%Большую помощь оказал Алексей Вячеславович Чернов
%при подготовке текста к публикации,
%за что авторы ему очень благодарны.


\newpage
\begin{thebibliography}{9}

\bibitem{Kolm63} A.\,N.\,Kolmogorov.
On tables of random numbers.
\emph{Sankhy\~a: The Indian Journal of Statistics},
Series~A, 1963, v.~25, part~4.
(Reprinted in \emph{Theoretical Computer Science},
1998, vol.~207, pp.~387--395).

\bibitem{Kolm65} А.\,Н.\,Колмогоров.
Три подхода к определению
понятия ``количество информации''.
\emph{Проблемы передачи информации},
1965, т.~1, N~1, с.~3--11.

\bibitem{KolmU} А.\,Н.\,Колмогоров.
Комбинаторные основания теории информации
и исчисления вероятностей.
\emph{Успехи математических наук},
1983, т.~38, N~4, с.~27--36.

\bibitem{MS} Ан.\,А.\,Мучник, А.\,Л.\,Семенов.
О роли закона больших чисел в теории случайности.
\emph{Проблемы передачи информации},
2003, т.~39, N~1, сс.~134--165.

\bibitem{mises} R.\,von\,Mises.
Grundlagen der Wahrscheinlichkeitsrechnung.
\emph{Mathematische Zeitschrift},
1919, v.~5, pp.~52--99.

\bibitem{chur} A.\,Church.
On the concept of a random sequence.
\emph{Bulletin of American Mathematical Society},
1940, v.~46, pp.~130--135.

\bibitem{ville} J.\,Ville.
\emph{\'Etude Critique de la Notion de Collectif}.
Gauthier-Villars, 1939.

\end{thebibliography}
\end{document}