\documentclass[12pt,draft]{article}

\usepackage{amsmath,amsthm}
\usepackage[indentheadings]{russcorr}
%% babel staff
%\usepackage[T2A]{fontenc}
%\usepackage[koi8-r]{inputenc}
%\usepackage[russian]{babel}

\hfuzz=0.5pt
\tolerance=600


\newtheorem{thm}{Теорема}
\newtheorem*{lem}{Лемма}
\theoremstyle{definition} \newtheorem{defn}{Определение}
\renewcommand{\proofname}{Доказательство}

\newcommand*{\pair}[1]{\langle #1\rangle}

\newcommand{\KS}{{KS}}

\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}


\author{Андрей Мучник\thanks{
        Институт новых технологий,
        109004, Москва, ул. Нижняя Радищевская, 10.
        \mbox{E-mail}:~muchnik@lpcs.math.msu.ru,
        fax:~(095)9156963.
        Работа выполнена при поддержке
        Российского Фонда Фундаментальных Исследований,
        гранты N~01-01-00505, N~02-01-22001.}
       }

\title{О взаимной информации
двоичного слова и его энтропии}

\date{}

\begin{document}
\maketitle

Наши рассмотрения будут относиться
к двум типам энтропии (и условной энтропии)
двоичных слов.
А именно, простая энтропия (определ\"енная
Колмогоровым), которую мы будем обозначать $\KS$,
и префиксная энтропия (определ\"енная
Левиным), которую мы будем обозначать $KP$.
Когда какое-то утверждение может быть
отнесено одновременно к обоим типам энтропии,
мы будем писать $K$ вместо $\KS$ и $KP$.
Мы предполагаем фиксированными
вычислимые изоморфизмы между множеством
двоичных слов и множеством натуральных чисел,
множеством пар двоичных слов и так далее.
Все логарифмы будут браться по основанию $2$.
Через $\ell(x)$ будет обозначаться
длина слова $x$.

Как известно, обе рассматриваемые
энтропии перечислимы сверху
и очень близки по величине:
\begin{gather*}
\KS(x|y)\le KP(x|y)+O(1)\,,\\
KP(x|y)\le \KS(x|y)+O(\log \KS(x|y))\,.
\end{gather*}
Неудивительно, что $\KS$  и $KP$
обладают многими одинаковыми свойствами.
Однако в некоторых случаях они ведут
себя по-разному. Пример свойства
из общей теории алгоритмов,
%recursion theory
существенно различающего $\KS$ и $KP$,
привед\"ен в~\cite{MuchPos}.
В настоящей работе исследуются
количественные свойства,
относительно которых $\KS$ и $KP$
ведут себя противоположным образом.
Нас будут интересовать следующие вопросы:
помогает ли знание слова найти его энтропию
и помогает ли знание энтропии слова
найти само слово?
Более точно, мы хотим описать
поведение функций
$I(x:K(x))=K(K(x))-K(K(x)|x)$
и $I(K(x):x)=K(x)-K(x|K(x))$
(вместо $I$ будем писать $IS$,
когда $K=\KS$, и $IP$,
когда $K=KP$).
По теореме Колмогорова--Левина
о симметрии взаимной информации
$K(x)-K(x|y)\approx K(y)-K(y|x)\approx
 K(x)+K(y)-K(\pair{x,y})$.
Если $y=K(x)$, то, как показал Гач,
$$
K(\pair{x,y})=K(\pair{x,K(x)})=K(x)+O(1)
$$
(минимальный код слова $x$ да\"ет $x$,
а его длина да\"ет $K(x)$).
Однако взаимная информация симметрична
только с точностью до
$O\bigl(\log K(x)+\log K(y)\bigr)$
(для $\KS$ это доказано Колмогоровым и Левиным,
а для $KP$~--- Гачем).
Поскольку $K(K(x))\le O(\log K(x))$,
логарифмическая точность оказывается недостаточной.


Основные результаты,
доказательства которых приведены
в теоремах~\ref{thm:1}--\ref{thm:4},
можно изобразить в виде
таблицы.

\begin{center}
\newlength{\mycellwidth}
\setlength{\mycellwidth}{0.33\textwidth}
\begin{tabular}{|c|c|c|}
\hline
&$\KS$&$KP$\\
\hline
$I(K(x):x)$
&\parbox{\mycellwidth}
 {\strut
  \raggedright
  Взаимная информация ограничена
  \strut}
&\parbox{\mycellwidth}
 {\strut
  \raggedright
  Взаимная информация стремится к $\infty$
  \strut}\\
\hline
$I(x:K(x))$
&\parbox{\mycellwidth}
 {\strut
  \raggedright
  Взаимная информация не ограничена,
  но не стремится к $\infty$
  \strut}
&\parbox{\mycellwidth}
 {\strut
  \raggedright
  Взаимная информация стремится к $\infty$
  \strut}\\
\hline
\end{tabular}
\end{center}

Мы видим, что для $KP$ знание слова
помогает найти его энтропию и
знание энтропии слова помогает найти
само слово.
Для $\KS$ знание энтропии слова не помогает
найти само слово,
а знание слова иногда помогает найти его
энтропию, а иногда~--- нет.

\begin{thm}\label{thm:1}
 Функция $IS(\KS(x):x)$ ограничена.
\end{thm}
\begin{proof}
Рассмотрим достаточно большое
натуральное число $D$.
Предположим, что $\KS(x|\KS(x))<\KS(x)-D$.
Пусть $y$~--- минимальный код $x$
при известном $\KS(x)$.
Обозначим через $n$ двоичную запись
числа $N=\KS(x)-\ell(y)$,
в которой каждая цифра повторена дважды.
По слову $n01y$ можно эффективно найти $x$.
Действительно, первое слева вхождение $01$
отделяет $y$ от $n$;
по $n$ находим $\KS(x)-\ell(y)$;
зная $y$, находим $\KS(x)$;
по $y$ и $\KS(x)$ находим $x$.
Следовательно, $\KS(x)\le \ell(n01y)+C
\le 2\log N + 4 + \ell(y) + C$,
где $C$ зависит только от выбора
оптимального языка программирования.
То есть, $N=\KS(x)-\ell(y)\le 2\log N + C+4$.
Поскольку $N>D$, при больших $D$ получается
противоречие.
Таким образом, при достаточно большом $D$
имеем
$\KS(x) \le \KS(x|\KS(x))+D$.
\end{proof}

Возможно, читатель удивится,
почему то же самое рассуждение
нельзя применить к функции $IP(KP(x):x)$.
В этом случае $y$~--- минимальный
\emph{префиксный} код $x$ при известном $KP(x)$,
$n01$~--- \emph{префиксный} код $N$.
Казалось бы, $n01y$~--- префиксный код $x$,
и получается аналогичный результат.
В действительности $y$ является префиксным
кодом $x$ только при фиксированном условии.
Совокупность же всех кодов, соответствующих
функции $KP(\cdot|\cdot)$ при всех условиях,
не является префиксным множеством.


\begin{thm}\label{thm:2}
Функция $IP(KP(x):x)$ стремится к бесконечности.
\end{thm}
\begin{proof}

Как известно, перечислимая снизу функция
$\mu(x|y)=2^{-KP(x|y)}$
для каждого $y$ зада\"ет полумеру
на области определения $x$
и является наибольшей среди таких функций
с точностью до мультипликативной константы.
Соответственно $\mu(x)=2^{-KP(x)}$.
Через $\mu^t$ обозначим результат
шага $t$ перечисления снизу функции $\mu$.
При каждом $t$ область, на которой $\mu^t\ne 0$,
конечна.

Определим вычислимую функцию $\nu^t_k(x|n)$
от натуральных аргументов
$x$, $n$, $t$ и $k>0$
с рациональными значениями.
Для $t=0$ функция $\nu$ тождественно равна нулю,
при увеличении $t$ она не убывает и
для всех $t$, $n$, $k$ выполнено
${\sum\limits_x \nu^t_k(x|n)\le 2^{-k}}$.

Положим
$\nu^{t+1}_k(x|n)=2^k\cdot\min\{\mu^t(x),2^{-n}\}$,
если
$\sum\limits_x \min\{\mu^t(x),2^{-n}\}\le 2^{-2k}$,
и
$\nu^{t+1}_k(x|n)=\nu^{t}_k(x|n)$
в противном случае.

Функция
$\nu(x|n)=\sum\limits_k\max\limits_{t} \nu^t_k(x|n)$
перечислима снизу и $\sum\limits_x\nu(x|n)\le 1$.
Поэтому $\nu(x|n)\le O(\mu(x|n))$.

Для любого $k$ существует такое $x_0$, что
${\sum\limits_{x\ge x_0} \mu(x) \le 2^{-2k-1}}$, и
существует такое $n_0$,
что для любого $n\ge n_0$ имеет место
${\sum\limits_{x < x_0} 2^{-n} \le 2^{-2k-1}}$.
Отсюда для $n\ge n_0$ имеем
$\sum\limits_x \min\{\mu^t(x),2^{-n}\}\le 2^{-2k}$,
и поэтому $\nu(x|n)\ge 2^k\cdot\min\{\mu(x),2^{-n}\}$.
Для всех достаточно больших $x$
значение $\mu(x)$ не превышает $2^{-n_0}$,
следовательно, при $n=-\log \mu(x)=KP(x)$
получается
$\nu(x|n) \ge 2^k\cdot\mu(x)$.
Так как
$\mu(x|n)\ge 2^{-C}\cdot \nu(x|n)
\ge 2^{k-C}\cdot\mu(x)$,
то $KP(x|KP(x))\le KP(x)-k+C$,
где $C$ зависит только от выбора
оптимального языка программирования.
\end{proof}


\begin{thm}\label{thm:3}
Функция $IP(x:KP(x))$ стремится к бесконечности.
\end{thm}
\begin{proof}
Доказательство этой теоремы
похоже на доказательство
предыдущей теоремы.

Определим вычислимую функцию $\nu^t_k(n|x)$
от натуральных аргументов
$n$, $x$, $t$ и $k>0$
с рациональными значениями.
Для $t=0$ функция $\nu$ тождественно равна нулю,
при увеличении $t$ она не убывает и
для всех $t$, $x$, $k$ выполнено
${\sum\limits_n \nu^t_k(n|x)\le 2^{-k}}$.

Для определения $\nu^{t+1}_k(n|x)$
введ\"ем вспомогательную величину
$$
\alpha_k(n|x)=
  \begin{cases}
    2^k\cdot \mu^t(n),&\text{ при }\mu^t(x)=2^{-n},\\
    \nu^t_k(n|x), &\text{ иначе}.
  \end{cases}
$$
Если
$\sum\limits_n \alpha_k(n|x)\le 2^{-k}$,
положим
$\nu^{t+1}_k(n|x)=\alpha_k(n|x)$,
в противном случае
$\nu^{t+1}_k(n|x)=\nu^{t}_k(n|x)$.

Функция
$\nu(n|x)=\sum\limits_k\max\limits_{t} \nu^t_k(n|x)$
перечислима снизу и $\sum\limits_n\nu(n|x)\le 1$.
Поэтому $\nu(n|x)\le O(\mu(n|x))$.

Для любого $k$ существует такое $n_0$, что
${\sum\limits_{n\ge n_0} 2^k\mu(n) \le 2^{-k}}$,
и существует такое $x_0$,
что для любого $x\ge x_0$ имеет место
$\mu(x)\le 2^{-n_0}$.
Отсюда для $x\ge x_0$ имеем
$\nu(n|x)=0$ при $n<n_0$ и
неравенство
$\sum\limits_n \alpha_k(n|x)\le 2^{-k}$
из определения функции $\nu$
будет выполнено при всех $t$.
Следовательно, при $n=-\log \mu(x)=KP(x)$
получается
$\nu(n|x) \ge 2^k\cdot\mu(n)$.
Так как
$\mu(n|x)\ge 2^{-C}\cdot \nu(n|x)
\ge 2^{k-C}\cdot\mu(n)$,
то $KP(KP(x)|x)\le KP(x)-k+C$,
где $C$ зависит только от выбора
оптимального языка программирования.

\end{proof}

\begin{thm}\label{thm:4}
 Функция $IS(x:\KS(x))$ неограничена,
но не стремится к бесконечности.
\end{thm}
\begin{proof}
 Неограниченность функции $IS(x:\KS(x))$
почти очевидна.
Пусть $x$~--- случайное слово длины $n$
(то есть $\KS(x)=n+O(1)$).
Тогда $\KS(\KS(x)|x)=O(1)$,
в то время как $\KS(\KS(x))\to\infty$.

Теперь наша цель~--- доказать, что
функция ${IS(x:\KS(x))}$,
ограниченная
на некоторое бесконечное множество,
не превосходит константы.
Поскольку для любого слова $x$
длины $n$
простая энтропия $x$
не превышает $n+O(1)$,
то $\KS(\KS(x))\le \log n+O(1)$.
Мы покажем, что
$$
\forall n\:\exists x\quad
\ell(x)=n \land
\KS(\KS(x)|x)\ge \log n - O(1)\,,
\eqno{(*)}\label{eq}
$$
откуда сразу следует утверждение теоремы.

Назов\"ем \emph{полуперечислителем}
вычислимую функцию $f(x,t)$
(где $x$~--- двоичное слово,
$t$ и значение $f$~--- натуральные числа),
которая монотонно невозрастает по $t$ и
$\lim\limits_{t\to\infty} f(x,t) \ge \KS(x)$.
Если
$\forall x\:\lim\limits_{t\to\infty} f(x,t)=\KS(x)$,
то $f$ называется \emph{перечислителем}.
Значения $f$ мы будем называть
\emph{гипотезами} об энтропии $x$.


Пусть $f_0$~--- какой-нибудь перечислитель,
$C$~--- достаточно большое натуральное число.
Построим по ним
полуперечислитель $f_1$.
Для каждого $x$ он
переходит к новой гипотезе $f_1(x,t)$,
только когда за время $t$
она была выдвинута перечислителем $f_0$
и было обнаружено, что
$\KS(f_1(x,t)|x) < \left\lfloor\log\ell(x)\right\rfloor-C$.
Количество гипотез $f_1$
для каждого $x$ меньше $\ell(x)/2^C$.
Простая энтропия программы вычисления $f_1$
не больше $\log C + O(1)$.
Предположим, что утверждение~$(*)$ не выполнено,
тогда
$\exists n\,\forall x\:
[\ell(x)=n\:\Rightarrow\:
\lim\limits_{t\to\infty} f(x,t)=\KS(x)]$.
Осталось доказать следующую лемму.
\begin{lem}
Пусть число $c$ достаточно велико
и полуперечислитель $f$
зада\"ется программой
с простой энтропией $d>0$.
Если
$\forall x\:[\ell(x)=n\:\Rightarrow\:
 \lim\limits_{t\to\infty} f(x,t)=\KS(x)]$,
то на некотором $x$ длины $n$
количество гипотез $f$
больше $n/(cd)$.
\end{lem}

Эта лемма усиливает теоремы~2 и~4
из работы~\cite{7avt}
(автор доказал эту лемму после
прочтения~\cite{7avt}).

\begin{proof}
Без ограничения общности предположим,
что $f(x,0)=\ell(x)+O(1)>\ell(x)$.
Построим вспомогательную
частичную вычислимую
функцию $g(y,a)$
(где $y$~--- двоичное слово,
$a$ и значение $g$~--- натуральные числа).
На рис.~\ref{fig:alg} привед\"ен алгоритм
перечисления графика функции $g$
(в дальнейшем мы будем ссылаться
на пункты этого алгоритма).

\begin{figure*}
\hrule
\smallskip
{
\sffamily
\slshape
\begin{tabbing}
$0$\=. Параллельно для всех натуральных
          $a$ и $n>5$ делаем следующее.\+\\
  $1$. \=\+ Последовательно для каждого $x$ длины $n$:\\
   $2$. Положим $t=0$.\\
     $3$. \= Е\=сли $f(x,t)\le n/2+a$,\\
           \>\> то завершаем процесс для данного $n$.\+\\
     $4$. \= Ищем такое слово $y$ длины $f(x,t)-a$, \=\\
               \+\>\>что $g(y,a)$ ещ\"е не определено;\'\\
        е\=сли оно найдено,\\
        \>то полагаем $g(y,a)=x$,\\
        \>иначе завершаем процесс для данного $n$.\-\\
      $5$. Жд\"ем такое $t'>t$,
                что $f(x,t')<f(x,t)$.\\
      $6$. Е\=сли $f(x,t')<f(x,t)-a-1$,\\
           \>то переходим к следующему $x$ из пункта $1$,\\
           \>иначе полагаем $t=t'$ и
             переходим к пункту $3$.
\end{tabbing}%
}%
\caption{Алгоритм перечисления графика
         функции $g(y,a)$.}\label{fig:alg}
\smallskip
\hrule
\end{figure*}

Очевидно, что
$\forall a,x\mspace{9mu}
 \KS(x)\le\min\{\ell(y)\mid g(y,a)=x\}+O(d+\log a)$.
Пусть $b$~--- достаточно большое число
(его величина зависит от выбора
оптимального языка программирования).
Фиксируем $a=bd$.
В пункте~5 мы всегда над\"ем $t'>t$,
для которого $f(x,t')<f(x,t)$,
потому что $a>O(d+\log a)$.
Для любых $n$, $m$ есть не более одного
$y$ длины $m$, для которого
$g(y,a)=x$, $\ell(x)=n$ и $\KS(x)\ge m-1$
(такие $y$ будем называть \emph{исключениями}).
При $\ell(y)=m$ значение
$g(y,a)$ могло быть определено
только при рассмотрении
в пункте~0 чисел $n<2m$.
Мощность $\{x\mid \KS(x)<m-1\}$ меньше
$2^m/2$,
количество исключений длины $m$
меньше $2m$;
поэтому если бы в пункте~4 не удалось найти $y$,
то $2^m/2<2m$, что противоречит
ограничению $n>5$ из пункта~0.

При $n < 4a$ утверждение леммы
будет выполнено для $c \ge 4b$.
Пусть $n\ge 4a$.

Если для всех $x$ длины $n$
количество гипотез $f$ не больше $n/(cd)$,
то при некотором $t$ условие
в пункте~6 обязательно будет выполнено.
Действительно, при уменьшении
$f(x,t)$ от $n+O(1)$ до $n/2+a$
было меньше $n/(cd)$ прыжков,
следовательно, один из них был больше
$(n/2-a):(n/(cd)) \ge cd/4 > a+1$
(если $c>4b+4$).
Получается, что для каждого $x$
длины $n$ некоторая гипотеза $f$
строго меньше $n$.
Но мощность $\{x\mid \KS(x)<n\}$
строго меньше $2^n$,
а количество слов длины $n$ равно $2^n$.
Противоречие.
\end{proof}
Теорема доказана.
%\renewcommand{\qed}{\relax}
\end{proof}

В теоремах~\ref{thm:2} и~\ref{thm:3}
не было дано никакой эффективной оценки
на скорость роста функций
$IP(KP(x):x)$ и $IP(x:KP(x))$.
Это неудивительно:
как известно, даже для функций
$KP(x)$ и $KP(KP(x))$
не существует частично вычислимых
неограниченных нижних оценок.
Тем не менее,
следующие две теоремы показывают,
что для каждой из функций
$IP(KP(x):x)$ и $IP(x:KP(x))$
существует бесконечное
(и не слишком редкое) множество,
на котором функция
увеличивается достаточно быстро.

\begin{thm}\label{thm:5}
Для любого натурального $k$
существует двоичное слово $z$
длины не больше $k$,
для которого
$IP(KP(z):z)\ge \log k - O(1)$.
\end{thm}
\begin{proof}
Будем считать число $k$ достаточно большим
(для малых $k$ утверждение теоремы тривиально).

Определим вычислимую функцию $\nu^t(x|n)$
от натуральных аргументов
$x$, $n$ и $t$
с рациональными значениями.
Для $t=0$ функция $\nu$ тождественно равна нулю,
при увеличении $t$ она не убывает и
для всех $t$, $n$ выполнено
${\sum\limits_x \nu^t(x|n)\le 1}$.

Положим
$\nu^{t+1}(x|n)= (n/4)\cdot 2^{-n}$,
если $\mu^t(x) \ge 2^{-n}$ и
$
{\bigl\lvert\{x|\mu^t(x) \ge 2^{-n}\}\bigr\rvert}
\le 2^{n+2}/n$,
в противном случае
$\nu^{t+1}(x|n)=\nu^{t}(x|n)$.

Функция
$\nu(x|n)=\max\limits_{t} \nu^t(x|n)$
перечислима снизу и $\sum\limits_x\nu(x|n)\le 1$.
Поэтому $\nu(x|n)\le O(\mu(x|n))$.

Покажем, что для одного из $n\in[k/2,k]$
при всех $t$ выполнено
$
{\bigl\lvert\{x|\mu^t(x) \ge 2^{-n}\}\bigr\rvert}
\le 2^{n+2}/n$.
Если бы это было не так, то
$$
\forall n\in[k/2,k]\quad
\bigl\lvert\{x|\mu(x) \ge 2^{-n}\}\bigr\rvert
\cdot 2^{-n} > 4/n\,.
$$
Суммируя, выводим
$$
\sum_{n=k/2}^{k}
\bigl\lvert\{x|\mu(x) \ge 2^{-n}\}\bigr\rvert
\cdot 2^{-n} >
\sum_{n=k/2}^{k} 4/n > 2\,.
$$
С другой стороны
$$
2\ge\sum_x 2\mu(x) \ge
\sum_{n=k/2}^{k}
\bigl\lvert\{x|\mu(x) \ge 2^{-n}\}\bigr\rvert
\cdot 2^{-n}\,,
$$
противоречие.

Фиксируем найденное $n$.

Рассмотрим случайное слово $y$ длины $k$.
Его простая, а тем более префиксная энтропия больше
$k-O(1)$.
Пусть $y_i$~--- начало $y$ длины $i$.
Понятно, что в последовательности
$KP(y_{k}),KP(y_{k-1}),\ldots$
соседние числа отличаются не более чем
на константу.
Если $j$~--- наименьшее натуральное число,
для которого $KP(y_{k-j}) \le n$,
то $KP(y_{k-j})\ge n-C$,
где $C$ зависит только от выбора
оптимального языка программирования.
Положим $z=y_{k-j}$,
тогда $\mu(z)\ge 2^{-n}$ и
$\mu^t(z)\ge 2^{-n}$
начиная с некоторого $t$.
Начиная с этого $t$
будет $\nu^t(z|n)=(n/4)\cdot 2^{-n}$
(за сч\"ет выбора $n$).
Отсюда
$\mu(z|n) \ge 2^{-O(1)}\cdot(n/4)\cdot 2^{-n}$.
Логарифмируя, получаем
$KP(z|n)\le n - \log n + O(1)$.
Поскольку
$\lvert KP(z) - n \rvert \le C$,
то
$KP(z|KP(z)) \le KP(z|n) + O(1)$.
Следовательно,
$KP(z)-KP(z|KP(z)) \ge
  (n-C) - (n-\log n + O(1))\ge\log k - O(1)$.
Теорема доказана.
\end{proof}

\begin{thm}
Для любого натурального $k$
существует двоичное слово $z$
длины не больше $k$,
для которого
$IP(z:KP(z))\ge \log k - O(\log\log k)$.
\end{thm}
\begin{proof}
Будем считать число $k$ достаточно большим
(для малых $k$ утверждение теоремы тривиально).

Рассмотрим натуральное число
$n \le k$, двоичная запись которого
является случайным словом длины
$\left\lfloor\log k\right\rfloor$,
то есть
$\KS(n)=\left\lfloor\log k\right\rfloor+O(1)$.
Пусть $z$~--- случайное слово длины $n$,
то есть
$\KS(z)=n+O(1)$.
Понятно, что
$\KS(n)-O(1) \le  KP(n)  \le
 KP(KP(z)) + {KP(KP(z)-n)}+O(1)\le
 KP(KP(z)) + {KP(O(\log n))}+O(1)\le
 KP(KP(z)) + {O(\log\log n)}$.
Поэтому $KP(KP(z))\ge \log k - O(\log\log k)$.
С другой стороны,
$KP(KP(z)|z)\le
 KP(n|z)+{KP(KP(z)-n|z)}+O(1)\le
 O(1)+{KP(O(\log n)|z)}\le
 O(\log\log k)$.
Следовательно,
$KP(KP(z))-KP(KP(z)|z)\ge
  \log k - O(\log\log k)$.
Теорема доказана.
\end{proof}


Автору было полезно
знакомство с работой~\cite{7avt}
и замечание анонимного рецензента
о связи этой работы
со стать\"ей~\cite{Gacs}.
Большую помощь оказал
Алексей Вячеславович Чернов
при подготовке текста к публикации,
за что автор ему очень благодарен.

\begin{thebibliography}{9}

\bibitem{MuchPos}
An.~A.~Muchnik, S.~Ye.~Positselsky.
Kolmogorov entropy in the context
of computability theory.
{\it Theoretical Computer Science},
2002, v.~271, pp.~15\nobreakdash--35.

\bibitem{7avt} R.~Beigel, H.~Buhrman,
 P.~Fejer, L.~Fortnow, L.~Longpr\'e,
 F.~Stephan, L.~Torenvliet.
 Enumerators of the Kolmogorov Function.
 Technical Report 2001-004, NEC Research Institute, 2001.

\bibitem{Gacs} П.~Гач.
О симметрии алгоритмической информации.
{\it Доклады АН СССР}, 1974,
т.~218, N.~6, с.~1265\nobreakdash--1267.
\end{thebibliography}

\end{document}
