\documentclass[12pt,a4paper%,draft
]{article}

%\usepackage{amsmath,amssymb,russcorr}
\usepackage[TS1,T2A]{fontenc}
\usepackage{russcorr}
\usepackage{russlh}
\usepackage{myrusadd}
\usepackage{xspace}
%\usepackage{pageborders}
%\usepackage{compress}
\usepackage{soul}

\usepackage{Defs}

\tolerance=1000

\let\�\tire
\let\�\Tire
\let\�\cherta
\let\�\defis
\let\�\Defis

\def\epsilon{\varepsilon}


\begin{document}

%\vspace*{3cm}

\begin{center}
\bf\large ����� ����������� �.\,�.~���\"����� � ��.\,�.~�������,
����������� � �������������� ������ ���������

\vspace{1cm}
I

\medskip

\end{center}


� ������ ����� ������ ������������ ����������, �����������
�~���������, ������������ ���������� ������� ������������
������������.

� ������ <<On tables of random numbers>>, ��������������
�~1963~���� (��.~\cite{kolm}), ���������� ������ ���� ���������
�~����������� ������������������� �� ���������� ������� ��������
������������������ ������� �����������, ��������������� ���
������������� ������� ����������� �� ����� ������.

��� ����������� ������������������� ������ ������� �������
����������� (���������� �� ������� ���������) ��� ���������
�\"����� �~1940~���� (��.~\cite{Church}). �~����������� �\"����
����� �������� ������������������ ��������� �� ���� ���������
(����������� {\it �������� ������}) �~���~�� �������, �~�������
��� ����������� �~������������������. ����� ������������ ���������
����� �������� ������ (��������� ���������� � ��������������
������), ������ �� ��������� ����� ���� �������� �
���������������������, ����������� �� ������ ���������. ����� ���
����������� ������� ������������������ $T$ ��������������, ���
�\"� ����� ����������� ���������� �~�������������~$p$ ��� �������
�~$1-p$ ��� ����. ����� ����������� ������� ����������:
\begin{gather*}
 \parbox{.93\textwidth}{\small ��� ������� ������� ������, �������
������� �� ����~$T$, �� ������ ��������� �����������
���������������������~$S$, ����� ������� ����� ����������� �~$S$
(�� ���� ���� ������ ����� ������ $n$ ����~$S$ ��������� �~$p$ ���
$n\to\infty$).} \tag*{($\ast$)}
\end{gather*}
���������� ������ ������������, ��� ����������� ���������
��������~($\ast$) ����� ����. ����� ������� ���������� ������
�������� ���������� ������ ����������� ��������
�������������������, ������� ����� ���� �� ������� ����������
������������ ���� �������� �~����������~$p$.

����\"���� � ���������� ������ �����������~\cite{kolm}.

� ���, {\it ��-������}, ���������� ������� ������� ������� ������.
��� ����� �� ���������� ���������, ������� ���� ���������� �����
��~������� ������������������ ��������� ���������� �����. ��� ����
��������� ���������� ���������� �~������ �������
������������������, ��������� �����. ����� (��~�������
������������������) ��������� ���������� ����� ����� ���� ���
������, ��� �~������ ������ ���������� �����, �� ���������, �����
���� ����� �� ��������� ������ �~�������� ������ ���������. ���
�~�~����������� �\"����, ����� ������������ ��������� �����
�������� ��������� �������, ������ �� ��� ���� ��������
�~���������������������, ����������� �� ������. ���� �������
������ �������� �� �����������, �� ��-�������� �����������
��������� ��������~($\ast$) ����� ����.

{\it ��-������}, ���������� ���������� �� �����������, �~��������
������� ������������������. �~���� ������ ������� ������ �����
���������� �� ���������� ���������, �~��������� ��������. �\"�
������� ����������� �~������� �������� ���������� ����������� ��
����� ������� ������������������. ��� ����� ��� �����
��������������� ������� � �������� ������������������� ����� ����
���������� �~����� ������ ���������� �� ���� �������������.

�������� ���������� ������ �����������~\cite{kolm} �������
�~���������.

����� $T$~--- �������� ������������������ �����~$N$; $R$~---
������� ������ (�~������ �����������) �� ������������������� �����
$N$; $A$~--- ��������� ������� ���� ��~$T$, ������� ���������
�~�������� ��������������������� ��� ���������� $R$ �~$T$ (�����
$A=R(T)\subset\{1,\dots,N\}$). ���������� ��������� ���������
������ ������ �� ������������������� ����� $N$ � ��������� ���
$\mathcal{R}_N$. �������� ������������������ $T=\langle
t_1,\dots,t_n\rangle$ ���������� �������� $(n,\varepsilon,p)$\�
��������� ������������ $\mathcal{R}_N$, ����� ��� ������� �������
$R\in\mathcal{R}_N$ ���������
\[
|R(T)|\geqslant n \;\Rightarrow\;
\bigg|\dfrac1{|R(T)|}\sum\limits_{k\in
R(T)}t_k-p\,\bigg|\leqslant\varepsilon.
\]


�������� ������, ������� ����������� �����������: ����� ������
����� ���� �������� $\mathcal{R}_N$ ��� ����, ����� ��������������
������������ $(n,\varepsilon,p)$\� ��������� ������������
$\mathcal{R}_N$ �������� ������������������~$T$ �����~$N$
(���������� ���������� � ��������� $T$ ������ <<������� ���������
�����>>). ��������� ����� $\tau(n,\varepsilon,N,p)$ ������� �����
����� $\rho$, ��� ��� ������� ��������� ������ $\mathcal{R}_N$
�������� $\rho$ ���������� ���� �� ���� ������� ��������� �����.
�������
\[
l(n,\varepsilon)=\inf\limits_{p,N}\,
\log_2\tau(n,\varepsilon,N,p).
\]
���������� �������, ��� ��� ���������� ����� $\varepsilon>0$
�~$n$, ���������� ������� ������������ $1/\varepsilon$, ���������
\[
2(\log_2e) \,n\varepsilon^2(1-\varepsilon)-1\leqslant
l(n,\varepsilon)\leqslant 4n\varepsilon(1+O(\varepsilon)).
\]
���������� ����� � \cite{kolm}, ��� ��� ��~������� ���������� ��
�������� �~����������� ��������, �~�������� $\varepsilon$ ������
�~������ �~������� ������ ��~$l(n,\varepsilon)$. ����� 20 ���
�~����������� �~��������~\cite{kolm} �� ������� ����,
��������������� �~\cite{trans_kolm}, ���������� ����������, ���
��������� �������� ��\"�� ������ �������. �������� ����������
�������� ����� 40~���.

������� �������� ����������� ���� ������� ���\"������ �~��������
�~������������ �~\cite{SM-DAN,MS-prob} (\cite{MS-prob}~---
����������� ������ ������� <<�������� �������� ����������>> �
100\� ����� �.\,�.~�����������). ���������, ��� ������ ������,
���������� ������������, ����������� �����. �~������, ���
���������� ����� $\varepsilon>0$ �~$n$, ���������� �������
������������~$1/\varepsilon$, ���������
\[
l(n,\varepsilon)\leqslant
2(\log_2e)\,n\varepsilon^2(1+2\varepsilon)
\]
(�������������� � ������� 3 �� \cite{SM-DAN,MS-prob}). �������,
��� ������\"����� ������� ������ �� $l(n,\varepsilon)$
�����������, ��������, ����� ����������� ��������� ������� $p=1/2$
�~��� ������� ��~$\mathcal{R}_N$ �����������. ����� ������������
������ ������ �������� ���� ����� �����, ��� �~�\"����.
�~������������ �������� ������ ��������� ������� ���� �������
������������������, ������� ���������� �~��������
���������������������, ����������� ������� (��~������ ���������
������� ������������������).

\bigskip
\begin{center}
\bf\large II
\end{center}
\medskip

�� ������ ����� ���������� ������ ��������������� ��� ������
����������� �������, ��������� � �������� �.\,�.~�����������.

������� ������, ��� �������� ����������� � ��������� �����������
����� ������ ������������ �~�������� ������������� ����������, ���
����������� ����� �������, ��� <<\emph{���� ����� �����������
������� ����\textup{,} ������� ����� ������� ������������
��������� ��������~$1$\textup{?}}>>, <<\emph{������ �����������
���������� ����� ��������~$1$\textup{,} �������� ����� �������
������������ ��������� ��������~$1$\textup{?}}>>.

� �������� ����������� ������������ ����� ��������� ��������� ����
�������� ������������������� �����~$N$ �~�������� ��~�\"��
����������� �������������� ������������. ������� ������� �������
����� ��� ��������� ����������� ����� ������������. (����������
����� ����� ������ �������������� ����������� ����� ����������, �
������ � ����� ��������������. ��������, � ����������� ����������
������� ������������ ������� ��������� ��� ���������� ������� ��
�����������~--- ��� $1/\sqrt{N}$.)

\emph{�������� ��������} ��������� $U$, ���������� ��
������������������� ���\-�� $N$, ���������� ��������
$1-\frac{\log_2 |U|}{N}$. (������� �������, �������� ������
��������� ����� $\delta$, ����� ��� �������� �����
$2^{N(1-\delta)}$.) �������, ��� ��� �� ������� ���������
������������ �� ������ ����������� ������ �����������.

������� ������� ������ $R$ �� ������������������� �����~$N$,
������������ �����~$n$ �~�����~$\varepsilon>0$ ��������������
������������ $\{0,1\}^N$, ���������� {\it ��������� ������}. ���
������� �� ��� �������� ������������������� $T$ ����� $N$, ���
������� $|R(T)|\geqslant n$ �~���� ������ �~��������
��������������������� ���������� ��~$1/2$ ��~����� ���
��~$\varepsilon$. (���� ����� $n$ �~$\varepsilon$ �����������,
��~��������������� ��������� ����� ����� ��������
\emph{$(n,\varepsilon)$\� �������}.)

�������� ����������� �� ����� ��������� ������ ������������� ���:
{\it ����� ����������� $(n,\epsilon)$\� ������ ����� �������
��������� ���� �������� ������������������� ����� $N$\textup{?}}

���������� �������, ��� ��� ������������ ������������ ��
$N,\epsilon,n$ {\it ��������� $\{0,1\}^N$ ���������� �������
$(n,\epsilon)$\� ������� � ���������� ������
$e^{2n\varepsilon^2(1-\varepsilon)}$.}

���\"���� � ������ ��������, ��� ��� ������������ ������������
��~$N,\epsilon,n$ {\it ��������� $\{0,1\}^N$ ����� �������
$(n,\epsilon)$\� ������� � ���������� ������
$e^{2n\varepsilon^2\frac{1+\varepsilon}{1-n/(N-1)}}$.}

������\"�� � ������ �������� ���������� ������� �������������
��������� $U\subset\{0,1\}^N$, �������� �������� ������ ������
$\delta$. ���\"���� � ������ �~\cite[�������~4,~5]{MS-prob}
��������� ��� ������� ���������� ������ �������������� $\delta$
����������� ����� $\rho(\delta)$, ��� �������� ���������
���������. ����� $N$ ���������� ������ ������������~$1/\delta$.

\begin{itemize}
\item[I.]
��� ������ $U\subset\{0,1\}^N$ � �������� �������� ������ $\delta$
���������� $\rho(\delta)$ ��������� ������, ����������� �������
��������� $U$ � ����� �������� ������ ������
$\frac{\delta}{2\ln(1/\delta)}$.

\item[II.]
��� ���������� $U\subset\{0,1\}^N$ � �������� �������� ������
$\delta$ ������ �������� ��������� $U$ ���������� �������,
�������� ������ ������� ������ $\frac{2\delta}{\ln(1/\delta)}$,
������� ����� ��� �� $e^{N/\rho(\delta)}$ ������.

\end{itemize}

� 1965 ���� � ������ ������� ������� <<�������� ��������
����������>> ���������� ����������� ���������� ������
\cite{kolm65}, �~������� ��� �����������, ��������� �� ����������
�������� �������� ������������������. ��� �������� ��������
�������������������~$y,z$ ���������~$z$ ��� ���������~$y$ �������
����������~$K(z\mid y)$. ����� $0<\delta<1$, $y$~--- ��������
������������������, ����������� �����~$N$ ���������� ������
�~���������~$U$ ������� ��~��� �������� �������������������~$z$
�����~$N$, ��� ������� $K(z\mid y)<N(1-\delta)$. ����� ��������
������~$U$ �������������� �����~$\delta$. ��� ��������
�������������� ��������� �������������� ������� ��������������
����������� �� ����� �������������� ���������
(��.~\cite[�������~1$'$, 3$'$, 4$'$, 5$'$]{kolm65}). ���
�������������� ��������� �� ���� �������� ��������� ��������������
���������, ��� ����� ��������� �� ���������� ��������������.
\textsl{��� ����������\"����� ������������� ���������� � ������
������� ����� ��� ������ ������ � ������ �\"���� � � ������
���\-��\-��\-��\-��. ��������� �� ��������������� ������� �����
��� ������ ������ �~������ �����������, �� �� �~������ �\"����
\textup{(}�������� ���\"������ � ��������
�~\textup{\cite[�������~4,~4$'$,~6$'$]{kolm65}}\textup{)}.} �����
�������, ��� � 1962 ���� ���������� ������������ ���������, ���
��� ��������� ������ ������ �\"���� � ���������� ��������
�����������.

��������� � ������������ ����������� �������� �������������������.
�����\"�� ����������� �������� ������������������, ���������
������������ ���� ������ ������ � ������ �\"����, ���������������
�� �\"����. �����\"�� ����������� �������� ������������������,
��������� ������������ ���� ������ ������ � ������ �����������,
��������������� �� �����������. �~1969~���� �~������~\cite{kolm69}
���������� �������, ��� �������������� �� �\"����
������������������ ����� ���� ����� ����������� ������������
�������������� ���������; �~������, ��������� �\"� ����� ����� $N$
����� ����� ��������� $\log^2 N$. �~��� �� ������ ����������
�������� ��������, ��� ��� �� ��������� �������� ���������
������������������, �������������� �� �����������. ��� ��������
���� ������������ ��������. ����� $\delta>0$. ���������, ���
������������������, ��������� ����� ������� ����� $N$ ����\"��
��������� $N(1-\delta)$, ��~����� ���� �������������� ��
�����������. �������� ��������� ��������� ��������������
������������ �~\cite{MSU}.


��������� �������� ��\"� ��� ����������, ���������� ��
�������������� �������� � �������������� � \cite{M98, M2002}. ���
��������� � �������� �������������������. ����\"�� � ������������
�����������. �������� ����� ����� ������������ ��� ��� ���������
����������. ����� ������������ ���� �������� ���� �������� ���-��
����� ������� �������\"����. ������, ��� ���������� ����� $z$
�������� �~���������� ����� $y$, ���� $K(z\mid y)\approx0$ (�����
$z\preceq y$). ��������, ��������� $\preceq$ �������� ���������
�������� �~�~������ ���� ���� ���� ������ ������� �����, �~������,
��� �� ����. ��������� ������������ �������:

\begin{itemize}

\item
����� �� � ���� �������\"���� ������ �����������?

\item
����� �� � ���� �������\"���� ������ ��������?

\end{itemize}


� \cite{M98} ��������, ��� ����� �� ������ ������ �����������;
�~\cite{M2002} ��������, ��� ����� �� ������ ������ �����������.
������\"�� ������ �����������.

\bigskip

{\it ��� ������ ���������� �������� ����� $m$ ���������� �����
����� $x_1$, $x_2$, ��� $K(x_1)>m$, $K(x_2)>m$,
$K(x_1,x_2)<\frac43m$ �~��� ������� �����~$w$, ���� $K(w\mid
x_1)<\frac13m$, $K(w\mid x_2)<\frac13m$, �� $K(w)<\frac12m$. }

�� ���� ������ <<����� ����������, ������������ � $x_1$ � $x_2$>>
������ $\frac23m-o(m)$, �� ��� ����� ���������� ����������
����������� ������� �������� ������ $w$ (��������������
�~\cite{M98}).

\bigskip

{\it ��� ����� ���� $u$, $v$ ���������� ����� ����� $w$, ���
\begin{align*}
 K(w)&<K(u\mid v),\\
 K(w\mid u)&<O(\log K(u)),\\
 K(u\mid v,w)&<O(\log K(u)).
\end{align*}}
\vspace{-3mm}

�� ���� $w$ ����� ������������� ��� �������� $u$ � $v$.
�~\cite{M2002} ��������, ��� ��� �������� ���������� ������������.


\begin{thebibliography}{99}


\bibitem{kolm}
\so{Kolmogorov A\<.N\<.} On tables of random numbers \from The
Indian Journal of Statistics. Series\;A. 1963. V.\;25, part\;4.
(Reprinted in Theoretical Computer Science. 1998. V.\;207.
P.\;387--395.)

\bibitem{trans_kolm}
\so{���������� �\<.�\<.} � �������� ��������� ����� \from
��������� � �����������. 1982. ���.\;18. �.\;3--13.

\bibitem{kolm65}
\so{���������� �\<.�\<.} ��� ������� � ����������� �������
<<���������� ����������>> \from �������� �������� ����������.
1965. �.\;1, \textnumero\;1. �.\;3--11.

\bibitem{kolm69}
\so{���������� �\<.�\<.} � ���������� ������� ������ ����������
�~������ ������������ \from �������� �������� ����������. 1969.
�.\;5, \textnumero\;3. �.\;1--4.


\bibitem{Church}
\so{Church\<.} On the concept of a random sequence \from Bull.
Amer. Math. Soc. 1940. V.\;46. P.\;130--135.


\bibitem{M98}
\so{Muchnik A\<n\<.A\<.} On common information \from Theoretical
Computer Science. 1998. V.\;207. P.\:319--328.


\bibitem{M2002}
\so{Muchnik A\<n\<.A\<.} Conditional complexity and codes \from
Theoretical Computer Science. 2002. V.\;271, \textnumero\;1--2.
P.\;97--109.


\bibitem{MSU}
\so{Muchnik A\<n\<.A\<.\<, Semenov A\<.L\<.\<, Uspensky V\<.A\<.}
Mathe\-ma\-tical Metaphysics of Randomness \from Theoretical
Computer Science. 1998. V.\;207. P.\;263--317.


\bibitem{SM-DAN}
\so{���\"���� �\<.�\<.\<, ������ �\<�\<.�\<.} �� ��������� ������
�����������, ����������� � �������� ��������� ����� � ������������
����������� ����������� \from ������� �������� ����. 2003.
�.\;391. �.\;1--3.

\bibitem{MS-prob}
\so{������ �\<�\<.�\<.\<, ���\"���� �\<.�\<.} � ���� ������
������� ����� � ������ ����������� \from �������� ��������
����������. 2003. �.\;39, ���.\;1. �.\:134--165.






\end{thebibliography}




\end{document}
