\documentclass{article}
\makeatletter
\renewcommand{\@makefnmark}{}
\makeatother
\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*{Introduction}

Kolmogorov's work on what is called today
`Kolmogorov complexity' was originated
by his work~\cite{Kolm63}.
We follow it up; in particular,
we solve the problem on exact
bound of complexity of frequency tests of randomness.

As Kolmogorov wrote (\cite{Kolm63}),
``The set theoretic axioms of
the calculus of probability \ldots{}
had solved the majority of formal difficulties \ldots{}
so successfully that the problem of finding
the basis of real applications \ldots{}
became rather secondary to many investigators.''

We consider the simplest situation of a sequence
of trials with the outcomes $\{0,1\}$
and want to verify that digits appear independently
with probability $1/2$.
As a criterion for this,
von Mises (\cite{mises})
proposed the closeness of frequency
of zeros to $1/2$ in the sequence itself and
in all subsequences selected by ``admissible'' rules.
The notion of admissible rule was clarified by
Church (\cite{chur}).
Both von Mises and Church spoke about infinite sequences.
Kolmogorov in~\cite{Kolm63} gave his notion
of admissible rule for finite sequences\footnote{
A natural counterpart of this notion
for infinite sequences is invariant with respect to
computable permutations of digits of the sequence.}
and proposed the following (frequency) definition
of randomness of a finite sequence:
the frequencies of zeros and ones
in all long enough subsequences selected
by simple enough rules are close to $1/2$.
Certainly, we should specify an exact meaning
for `long enough', `simple enough', `close'
by concrete estimations
(which may depend on the length
of the original sequence).
The problem from~\cite{Kolm63} that
the authors have solved (Theorem~4)
was to find the exact estimations of basic parameters
for which random sequences exist.

Let us discuss now what is the language
in which we will set and solve problems
we are interested in.
Shannon began to build information theory
on the base of probability theory.
But in various situations it is reasonable to speak about
the quantity of information in a specific object,
but it is unclear how can this information be associated
with a probability distribution.

Another (combinatorial) approach consists in
considering some property of an object.
For instance, suppose a property of our interest
is the property of an object $\mathbf t$ ``being
binary sequence of length $L$ such that the fraction
of zeros in it is contained between the numbers $p$ and $q$.''
This property makes sense independent of any
probabilistic assumptions.
Informally speaking,
if $L$, $p$, $q$ are known beforehand,
then the quantity of information in $\mathbf t$
is
$$
\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
$$
(so many bits are needed for representing in binary
the number of an element in the set of all objects
with the mentioned property).
Note that one object has various properties.
For example, $\mathbf t$ has the property
``being equal to $\mathbf t$''.
Hence actually, under the combinatorial approach
the quantity of information is attributed not to
objects, but to properties.

A fundamental merit of the algorithmical approach
proposed by A.\,N.\,Kol\-mo\-go\-rov
is the fact that for each two separate
constructive objects $\mathbf t$, $\mathbf s$
it is defined the quantity of information
needed to find $\mathbf t$ if $\mathbf s$ is known.
If $\mathbf s$ is the empty word, we obtain
the quantity of information in $\mathbf t$
(denoted by $K(\mathbf t)$).
The basic relation for the Shannon entropy
(applied to probability distributions)
$$
H(\langle x,y\rangle)=H(x)+H(y|x)
$$
holds with high accuracy by the Kolmogorov--Levin theorem
for the function $K$ (Kolmogorov called it
the entropy of constructive objects):
\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}
Kolmogorov proved that the function $K$ is not computable.
It were studied also some ways of defining
computable entropy,

Kolmogorov noticed the following property
of the entropy as an important one.
Let $\mathbf t$ be a binary sequence of length $L$,
then
\begin{equation}\label{eq:impl}
\begin{array}{c}
\mbox{$K(\mathbf t|L)$
is not significantly less than $L$}\\[2ex]
\Downarrow\\[1ex]
\parbox{0.8\textwidth}{the frequencies of zeros and ones
in all long enough subsequences selected from $\mathbf t$
by simple enough rules are close to $1/2$.}
\end{array}
\end{equation}
(Certainly, it is necessary to change words
``not by far'', ``long enough'',
``simple enough'', ``close''
to concrete estimations.)
Remarkably, implication~(\ref{eq:impl})
can be reversed (Theorem~1$'$).
Thus, the stability of the frequencies
in subsequences is not only a necessary condition
of randomness, but also a sufficient one.
Let us underline that to obtain this result
we have to consider
subsequences such that their digits are selected
in an order that may be not the same as the order
in the original sequence (Theorem~3$'$).
Recall that the definition of nonmonotonic
place-selection rules
was introduced by Kolmogorov in~\cite{Kolm63}.

Kolmogorov wrote in~\cite{KolmU}:
``Information theory must precede probability theory,
and not be based on it.
By the very essence of this discipline,
the foundations of information theory
have a finite combinatorial character.
\dots{}
Naturally, this approach to the matter does not prevent
the development of probability theory
as a branch of mathematics
being a special case of general measure theory.''
The formulations of our theorems are strictly finitary.
Their proofs (published in~\cite{MS}),
being equally finitary in essence,
use probabilistic reasoning
(and so integrals and other notions of infinite mathematics)
for simplifying the presentation.

Our paper consists of two parts,
which corresponds to
combinatorial and algorithmical approaches
to information theory
(in sense of~\cite{Kolm65}).
For every theorem of the combinatorial part,
the algorithmical part contains a theorem
(that has the same number with prime)
that studies the same question
formulated in the language
of the other approach.


%%%% End of verified translation

\subsection*{Combinatorial approach}

We consider the problem of defining
the measure of randomness
for a finite binary sequence
with respect to Bernoully distribution.
Sometimes an intiutive concept
may be formalized in several ways.
(For example, in the combinatorial geometry
it is known very many definitions of
the symmetry measure of a convex body,
and some of which are not equivalent.)
Intuitively, a sequence $\mathbf t$ of length $L$
may be called non-random
if someone, who knows $L$, but who does not know $\mathbf t$,
appears to be able to point out a set $U$
consisting of sequences of length $L$
such that $U$ contains $\mathbf t$
and the measure of $U$ is a small enough.
Such sets are called tests.
For $\epsilon > 0$,
the law of large numbers can be associated
with the test that consists of all sequences
such that the fraction of zeros differs from $1/2$
by more than $\epsilon$.
Speaking in terms of these tests,
we see that intuitively non-random sequence $01010101\ldots$
turns out to be maximally random.
To overcome this difficulty,
Kolmogorov define the notion of
a place-selection rule that selects a subsequence
from a given sequence,
and to every pair
$\langle\mbox{\it rule, }\epsilon\rangle$
he assigned
a test corresponding to the law of large numbers.


\emph{A (place-selection) rule on sequences of length $L$}
is a pair of functions
$\langle r^1, r^2\rangle$
that are defined on binary sequences
of lengths from $0$ to $L-1$
The range of $r^1$ is the set $\{1,\ldots,L\}$,
and values of the function on
a sequence and its proper extension are always different.
The range of $r^2$ is the set
$\{\mbox{``S''}, \mbox{``N''}\}$.
Suppose $\mathbf t=t_1\ldots t_L$ is a sequence.
For each $i$ from $0$ to $L$,
by induction on $i$ we construct
binary sequences $\mathbf u_i$ and $\mathbf s_i$.
Let $\mathbf u_0=\mathbf s_0=\Lambda$,
$\mathbf u_{i+1}=\mathbf u_i t_{r^1(\mathbf u_i)}$;
if $r^2(\mathbf u_i)=\mbox{``N''}$,
then $\mathbf s_{i+1}=\mathbf s_i$,
and if $r^2(\mathbf u_i)=\mbox{``S''}$,
then $\mathbf s_{i+1}=\mathbf s_i t_{r^1(\mathbf u_i)}$.

We say that the rule $r$ selects
the subsequence $\mathbf s_L$ from $\mathbf t$,
and this subsequence is denoted by $r[\mathbf t]$.

Sometimes it is useful to consider more restricted
classes of rules.
In \emph{monotonic rules}
$r^1(\mathbf u_i)$ is always equal to $i+1$.
\emph{Non-adaptive rules} are monotonic rules
such that $r^2(\mathbf u_i)$
depends on $i$ only.

To every length $L$, rule $r$, and number $\epsilon>0$
assign a \emph{frequency} test
consisting of sequences $\mathbf t$
of length $L$
such that
the fraction of zeros in $r[\mathbf t]$
differs from $1/2$ by more than $\epsilon$.
A frequency test generated by monotonic
(non-adaptive) rule
is called monotonic (non-adaptive) test.

In the strongest formulation,
the reducibility of any probability-theoretic law
to the law of large numbers
would mean that an arbitraty test
can be included in a frequency test
of not too larger size.
Consider a simple example.
Every binary sequence of even length $L$
we may consider as a sequence of length $L/2$
consisting of pairs of binary digits.
Suppose $\epsilon<1/4$;
the test $V$ we will consider
consists of all sequences
such that
in the corresponding sequence of pairs
the fraction of occurences
$00$ differs from $1/4$
by more than $\epsilon$.
In other word, here we speak about
the same law of large numbers,
but for other distribution
(Bernoully distribution with four
equiprobable outcomes).
As Ville proved,
this test cannot be included
in any monotonic test
generated by a rule
such that for every sequence
the length of selected subsequence
is greater than $1/\epsilon$.
It is natural to require that
selected subsequences are sufficiently long:
the name of the law of large numbers
speaks for itself
(for example, in a sequence of length one
the fraction of zeros always differs from $1/2$ by $1/2$).

Let us prove the statement about $V$.
Let $r$ be a monotonic rule.
Let us choose digits of a sequence
$\mathbf t=t_1\ldots t_L$ one by one.
We will use the notation
$\mathbf u_i$ and $\mathbf s_i$
from the definition of $r[\mathbf t]$.
Assume that $\mathbf u_i$ has already been constructed.
If $r^2(\mathbf u_i)=\mbox{``N''}$,
then $t_{i+1}=1$.
If $r^2(\mathbf u_i)=\mbox{``S''}$,
then $t_{i+1}$ should differ from the last digit of
$\mathbf s_i$,
and $t_{i+1}=1$, when $\mathbf s_i=\Lambda$.

On the one hand,
the sequence of pairs corresponding to
$\mathbf t$ constructed
contains no occerences of $00$
(i.\,e., from the law of large numbers for
four outcomes point of view
the sequence $\mathbf t$ is maximally non-random).
On the other hand,
the subsequence $r[\mathbf t]$
has the form $101010\ldots$
(and it is maximally random
from the law of large numbers for
two outcomes point of view).

However it is sufficient
two monotonic tests (that are not too large)
for covering $V$.
In the following construction
these tests are denoted by $F_1$ and $F_2$.
The test $F_1$ is even non-adaptive.
The rule $r_1$ that generates it
selects all digits on odd places
(that is,
$r_1^2(\mathbf u_i)=\mbox{``S''}
\:\Leftrightarrow\:
i$ is even).
A monotonic rule $r_2$
selects digits on even places such that
the previous digit equals zero
(that is
$r_2^2(\mathbf u_i)=\mbox{``S''}
\:\Leftrightarrow\:
[i$ is odd and $t_i=0]$).
To provide a sufficient length of selected subsequnces
let us consider the following monotonic rule
$\bar r_2$.
Let $\nu(\mathbf u)$ be the number of zeros
on odd places in the word $\mathbf u$.
Then
$\bar r_2^2(\mathbf u_i)=\mbox{``S''}
\:\Leftrightarrow\:
\bigl[ r_2^2(\mathbf u_i)=\mbox{``S''}$ or
[$i$ is odd and
 $\nu(\mathbf u_i)+(L-i)/2\le L/5]\bigr]$).

It can easily be verified that
the test $F_1$ is assigned the pair
 $\langle r_1,\epsilon(1-\epsilon)\rangle$
and the test $F_2$ is assigned the pair
 $\langle \bar r_2,\epsilon(1-\epsilon)\rangle$,
then $V\subseteq F_1\cup F_2$.
And in this case
for $L > 34/\epsilon^3$, we have
$$
| F_1\cup F_2| <
   2^L\cdot\mathrm e^{-L\epsilon^2/5}\,.
$$

������ ����ந� ����� ������⮭�� ��� $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}\,.
$$

�०�� 祬 �� ��ᬮ�७���� �ਬ��
��३� � �ந������ ��⠬
�� ������ ����� 㤮���� 誠�� ��� ����७��
``������'' ���.
(�롮� ���室�饩 誠�� ����� ������ ��⥬���᪨�
�⢥ত���� ����� ����來묨, � ������ � �����
���ଠ⨢�묨.
���ਬ��, ��� �����뢠�� 業�ࠫ쭠� �।��쭠� ⥮६�,
����⢥���� ������ ����७�� ��� �⪫������ �����
�� ����⭮��~--- �� ��७� �� ������⢠
���⠭��.)

\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$.
����� ����ந� �ਬ�� (���\"���� ��ਠ�� ���ண�
�� ࠧ��࠭ ���� ���), �����뢠�騩, ��
⥮६�~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)$-��⠬�
� ������⢥
$$
\mathrm{e}^{2n\epsilon^2(1+\epsilon)/(1-n/(L-1))}\,.
$$
}

������ �⬥���, �� �������஢ ��� ᢮�� ������ �業��
� ����ந� ����뢠�饥 ᥬ���⢮ ��⮢.
��� �� ������⥫��⢮ ����⭮�⭮�.
������, ����� ����⭮�⭮� ������⥫��⢮
��\"�� ������ �業��, 祬 �� ������� � ����஥���,
������ �� � ���� ࠧ ����砥��� � ⥮ਨ ���ଠ樨
(���ਬ��, ⥮६� ������� � �������⮩稢�� ����஢����).

����� �� ���襬 � ᠬ�� ��饬 ���� ������� � ⥮ਨ ���ଠ樨
��\"��, �ਬ��\"���� � ⥮६�~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*{�����⬨�᪨� ���室}

� �����⬨�᪮� ���室� ������ ���
$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$).

�᫨ �� �� �� ����� � �����⨨ ��᫥�������
��� (�� �����⬨�᪨�) ������ ��⮢,
� �� ��� ������� ����� �⢥� �������� �� ����⥫��.
����⢨⥫쭮, ���� �᫠ $L$, $\sigma$ � ������⢮ ���
������ ��⮢, ᮯ��⠢������ ��ࠬ, ����騬 ���ய��
����� $\log_2 R$, ����� ���� ��᫥����⥫쭮���
$\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*{�����祭��}

It is well known that Andrei Kolmogorov in Russia and R. Solomonoff in
the USA discovered the basic notion and facts on complexity of finite
objects independently in mid-60s. In 60s and 70s the research of the area
was conducted mostly by students of Kolmogorov and members of
the Moscow mathematical community based on Moscow State (Lomonosov)
University: L. Levin, V. Vyugin, A. Zvonkin, N. Petri, P. G\'acs.
Chaitin considerably contributed to popularity of the theory in the West;
Solovay's manuscript influenced research in Russia as well.
From the end of 70s till his death in 1987 Kolmogorov was
the Chair of Department of Mathematical Logic. Now his former
student Vladimir Uspensky, who also works in the field of
Kolmogorov complexity, heads it.
In the first steps of his work as the chair of our department Professor
Kolmogorov proposed to the first author of this paper to start a seminar on
complexity.
(The seminar is called Kolmogorov Seminar now.) Starting from
the very beginning the seminar included research reports and
surveys on practical programming and computational complexity as well.
In his first talks at the seminar Kolmogorov introduced a program
of research of frequency approach to randomness and some other topics.
This program was implemented in works
of V. Vovk, A. Shen, N. Vereshagin, An. Muchnik and others.
In the following
years A. Shen and N. Vereshagin joined the leadership of the seminar and,
after the death of Kolmogorov, became the major moving force of it.
Professor Uspensky contributed a lot to its development.
In Kolmogorov and Uspensky
lecture at Bernoulli congress the results obtained by the Moscow
group in the period of Kolmogorov presence are summarized.
�᭮���� ᮤ�ঠ��� ���� �뫮 ��������
�� �������஢᪮� ᥬ���� ��᭮� 2002 ����.

\subsection*{Acknowledgments}

���ࠬ �祭� ����� ��饭�� � ���⭨����
�������஢᪮�� ᥬ����.
�ᮡ�� �ਧ��⥫쭮��� �� ��ࠦ���
������� ����⠭⨭����� ���頣���,
������ ���㦤���� � �����
����ᮢ �������஢᪮� ⥮ਨ
���㦨�� ��� ��� ����� �� �⨬㫮�
����� �������� ࠡ���.
%������� ������ ������ ����ᥩ ���᫠����� ��୮�
%�� �����⮢�� ⥪�� � �㡫���樨,
%�� �� ����� ��� �祭� ���������.


\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} A.\,N.\,Kolmogorov.
Combinatorial foundations of information theory
and the calculus of probabilities.
\emph{Russian Mathematical Surveys},
1983, vol.~38, no.~4, p.~29--40.

\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}