\documentclass[12pt,a4paper]{article}

\usepackage{amsmath,amssymb,amsthm}
\ifx\pdfoutput\undefined
\usepackage[indentheadings]{russcorr}
\else
\usepackage[T2A]{fontenc}
\usepackage[cp866]{inputenc}
\usepackage[russian]{babel}
\fi

\newcommand*{\logi}[1]{\log^{[#1]}}

\newcommand{\N}{\mathbb{N}}

\newtheorem{thm}{Теорема}
\newtheorem*{unthm}{Теорема}
\renewcommand{\proofname}{Доказательство}
\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}



\begin{document}

В знаменитой статье 1944 года Э. Пост
ввел понятия простого и гиперпростого
множества для построения перечислимых множеств,
которые были бы $btt$-неполными или даже $tt$-неполными.

Оказывается, простые и гиперпростые множества
естественно возникают при рассмотрении
вычислимых верхних оценок на функцию
колмогоровской (простой) и префиксной энтропии.
Простая энтропия была введена А.~Колмогоровым
в 1965~году, префиксная энтропия была введена
Л.~Левиным в 1970~году.

Как известно, функция префиксной энтропии
может рассматриваться как $-\log_2 \mu(x)$,
где $\mu(x)$~--- некоторый сходящийся ряд
(так называемая априорная полумера).
Это позволяет нам большую часть изложения
построить на языке положительных рядов.

Основной вопрос, связанный с рядами,~---
это вопрос об их сходимости.
Обозначим через $\logi{i}x$
$i$-ую итерацию двоичного логарифма.
%%$\logi{1} x= \log x$ $\logi{i+1} x=\log(\logi{i} x)$
Классическими примерами сходящихся рядов
являются
$a_m^0=\frac{1}{m^2}$,
$a_m^1=\frac{1}{m(\log m)^2}$,
$a_m^2=\frac{1}{m\log m(\logi{2} m)^2}$
и так далее.
Каждый следующий ряд из этой серии
существенно больше предыдущего,
то есть $\forall i\: (a_m^{i+1}/a_m^{i}\to\infty$
при $m\to\infty$).
Классическими примерами расходящихся рядов
являются
$b_m^0=\frac{1}{m}$,
$b_m^1=\frac{1}{m\log m}$,
$b_m^2=\frac{1}{m\log m\logi{2} m}$
и так далее.
Каждый следующий ряд из этой серии
существенно меньше предыдущего,
то есть $\forall i\: (b_m^{i+1}/b_m^{i}\to 0$
при $m\to\infty$).
Ряды $a_m^i$ и $b_m^i$ очень близки,
их отношение $\logi{i} m$
раст\"ет, но очень медленно.
Возникает естественный вопрос:
нет ли наибольшего сходящегося или
наименьшего расходящегося ряда?
Ответ на этот вопрос отрицателен.
Впрочем, нас будут интересовать вычислимые ряды.
Без ограничения общности будем считать,
что члены рядов принимают только значения
вида $2^{-n}$.
Каждое положительное число можно заменить
на ближайшее к нему снизу число указанного вида.
При этом оно уменьшится не более чем вдвое,
и сохранится сходимость или расходимость ряда.

Каждый вычислимый расходящийся ряд
можно существенно уменьшить,
оставив его расходящимся.

\begin{unthm}
По каждому вычислимому расходящемуся ряду
$\alpha_m$
можно построить вычислимый расходящийся ряд
$\beta_m$,
такой что $\beta_m/\alpha_m\to 0$.
\end{unthm}
\begin{proof}
Построим последовательность $\{m_i\}$,
так что
$\sum\limits_{m=m_i}^{m_{i+1}} \alpha_m > 2^{i}$,
$m_1=1$.
Положим $\beta_m=\alpha_m 2^{-i}$
для $m_{i}\le m< m_{i+1}$.
\end{proof}

Каждый вычислимый \emph{эффективно}
сходящийся ряд можно существенно увеличить,
оставив его эффективно сходящимся.

\begin{unthm}
По каждому вычислимому эффективно сходящемуся ряду
$\alpha_m$
можно построить вычислимый эффективно сходящийся ряд
$\beta_m$,
такой что $\beta_m/\alpha_m\to \infty$.
\end{unthm}
\begin{proof}
Построим последовательность $\{m_i\}$,
так что
$\sum\limits_{m=m_i}^{\infty} \alpha_m < 2^{-2i}$.
Положим $\beta_m=\alpha_m 2^{i}$
для $m_{i}\le m< m_{i+1}$.
\end{proof}

Неожиданно оказывается, что существует вычислимый
сходящийся ряд, который нельзя существенно увеличить,
оставив его сходящимся.

\begin{thm}\label{thm:1}
Существует вычислимый сходящийся ряд $\alpha_m$,
для которого нет
вычислимого сходящегося ряда $\beta_m$,
такого что $\beta_m/\alpha_m\to \infty$.
\end{thm}
Доказательство этой теоремы
мы привед\"ем ниже.

\begin{unthm}
Не существует наибольшего с точностью
до мультипликативной константы
вычислимого сходящегося ряда.
\end{unthm}
\begin{proof}
Пусть $\alpha_m$~--- вычислимый сходящийся ряд.
Построим последовательность $\{m_i\}$,
так что
$\alpha_{m_i} < 2^{-2i}$.
Положим $\beta_{m_i}=\alpha_{m_i} 2^{i}$,
и $\beta_m=\alpha_m$ для остальных $m$.
\end{proof}

Замечательным открытием в сво\"е время явилось то,
что в некотором естественном расширении
класса вычислимых рядов,
наоборот, существует наибольший с точностью
до мультипликативной константы сходящийся ряд.
Этим расширением является класс
вычислимо аппроксимируемых снизу рядов.
(В каждый момент времени нижняя аппроксимация ряда
отлична от нуля на конечном множестве.
Подчеркн\"ем, что не предполагается
\emph{равномерность} аппроксимации.)
Для удобства обозначений в дальнейшем
мы будем допускать члены ряда, равные нулю;
номер члена ряда будем писать не в индексе,
а в скобках.

\begin{thm}[Левин]
Существует вычислимо аппроксимируемый снизу
ряд $\mu(x)$, сумма которого $\le 1$, и
по каждому вычислимо аппроксимируемому снизу
ряду $\nu(x)$, сумма которого $\le 1$,
можно указать константу $C$,
для которой $\forall x\: \mu(x) > \nu(x)2^{-C}$.
\end{thm}
\begin{proof}
По аналогии с перечислимыми множествами
существует такая универсальная вычислимая функция
$U\colon n\mapsto \nu_n$,
нумерующая все вычислимо аппроксимируемые снизу ряды,
что каждая другая вычислимая функция $V$,
нумерующая вычислимо аппроксимируемые снизу ряды,
$\mathsf{m}$\nobreakdash-сводится к $U$.

Каждый вычислимо аппроксимируемый снизу ряд $\nu$
можно эффективно заменить на
вычислимо аппроксимируемый снизу ряд $\nu'$
так, что $\sum\nu'(x)\le 1$ и,
если $\sum\nu(x)\le 1$, то $\forall x\:\nu'(x)=\nu(x)$.
Программа, аппроксимирующая снизу $\nu'$,
действует так же, как
программа, аппроксимирующая снизу $\nu$,
пока сумма значений текущей аппроксимации $\nu$
не превышает $1$;
если же такое превышение случится,
то программа для $\nu'$ останавливается.

Искомый ряд $\mu$ можно определить как
$\sum_n 2^{-n} \nu'_n$.
\end{proof}

Очевидно, что ряд $\mu$, существование которого
мы доказали, единствен с точностью
до мультипликативной константы.

Левин доказал, что ряд $\mu$ невычислим.
Займ\"емся вопросом о его вычислимых
верхних и нижних оценках.

Ряд $\mu$ не имеет нетривиальных
частично вычислимых
верхних оценок
(аналог теоремы Маранджана
для простой энтропии).
\begin{thm}
Для каждой частично вычислимой функции
$\gamma$ можно указать такую константу $C$,
что
$$
\forall x\in Dom(\gamma)\;\:\mu(x)\le \gamma(x)
\quad\Rightarrow\quad
\forall x\in Dom(\gamma)\;\:\gamma(x) \ge 2^{-C}\,.
$$
\end{thm}
\begin{proof}
Рассмотрим следующий вычислимо
аппроксимируемый снизу ряд $\delta=\lim \delta_n$.
Аппроксимация $\delta_0$ тождественно равна нулю.
Аппроксимация $\delta_{n+1}$ совпадает с
аппроксимацией $\delta_n$ всюду,
кроме, возможно, одного аргумента $x$,
который ищется так.
Параллельно вычисляя $\gamma$ на всех аргументах,
ищем такое $x$, что $\gamma(x)< 2^{-2n}$.
На первом найденном $x$ (если оно вообще нашлось)
положим
$\delta_{n+1}(x) = \max\{\delta_n(x), 2^{-n-1}\}$.
Понятно, что $\sum_{x} \delta(x)\le 1$.
Следовательно, можно указать (эффективно по номеру $\gamma$)
такое $c$, что $\forall x\: \mu(x) > \delta(x)2^{-c}$.
Соединяя нижнюю и верхнюю оценки на $\mu(x)$,
получаем, что для $n \ge c$ число $x$
в определении $\delta_n$ найдено не будет,
и $\forall x\: \gamma(x) \ge 2^{-2c}$.
\end{proof}

Возникает предположение, что
у $\mu$ нет и хороших вычислимых нижних
оценок, то есть отношение $\mu$
к любой вычислимой нижней оценке $\mu$
стремится к бесконечности.
Следующая теорема опровергает это предположение
и заодно доказывает теорему~\ref{thm:1}.

\begin{thm}\label{thm:2}
Существует вычислимый ряд $\alpha$,
являющийся нижней оценкой,
и на бесконечном множестве равный $\mu$.
\end{thm}
\begin{proof}
Построим вспомогательный
вычислимый ряд $\beta$.
$$
\begin{array}{c|c|c|c|c|l}
\hline
1&&&&&\\
\hline
2&&&&&\\
\hline
\vdots&&&&&\\
\hline
i
&
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
&
\begin{array}{c}
\beta(x^2_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^2_i)>2^{-i}
\end{array}
&
\text{\hbox to 5em {\hfil$\cdots$\hfil}}
&
\begin{array}{c}
\beta(x^j_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\phantom{\mu(x^j_i)<2^{-i}}
\end{array}
&
\qquad
\\
\hline
\vdots&&&&&\\
\end{array}
$$

Ряд $\beta$ получается в результате
вычислимого процесса заполнения указанной таблицы.
К каждой строке мы возвращаемся бесконечно много раз,
и параллельно аппроксимируем снизу ряд $\mu$.
При первом обращении к $i$-ой строке
мы бер\"ем первый ещ\"е не определ\"енный
член ряда $\beta$ (обозначим его номер через $x^1_i$),
и полагаем $\beta(x^1_i)=2^{-i}$.
При следующем обращении к $i$-ой строке
мы сравниваем текущую аппроксимацию $\mu(x^1_i)$
с числом $2^{-i}$, и если $\mu(x^1_i) > 2^{-i}$,
то снова бер\"ем первый ещ\"е не определ\"енный
член ряда (обозначим его номер через $x^2_i$),
и полагаем $\beta(x^2_i)=2^{-i}$,
и так далее.
Ясно, что каждый номер $x$ ровно один раз
встречается в таблице.


Поскольку $\sum \mu(x)\le 1$, то
длина $i$-ой строки заведомо меньше $2^i$.
Рассмотрим множество $D$ номеров $x^j_i$,
для которых $\mu(x^j_i) \le 2^{-i}$.
Сумма ряда $\beta(x)$ по этому множеству
равна $\sum_i 2^{-i}=1$.
Сумма ряда $\beta(x)$ по дополнению до $D$
меньше $\sum \mu(x)\le 1$.
Итак, ряд $\beta(x)$ сходится
и
${\exists c\forall x\: \mu(x) > \beta(x)2^{-c}}$.

С другой стороны, $\mu(x)\le \beta(x)$
на бесконечном множестве $D$.
Для каждого $C$ рассмотрим множество
$M_C=\{x : \mu(x) \le\beta(x)2^{-C} \}$.
Для $C=0$ это множество бесконечно,
для $C=c$ это множество пусто.
С ростом $C$ множество $M_C$ уменьшается.
Рассмотрим наибольшее $d$,
для которого $M_{d}$ бесконечно.
Так как ${\mu(x) > \beta(x)2^{-(d+1)}}
\Leftrightarrow
{\mu(x) \ge \beta(x)2^{-d}}$,
то на дополнении до конечного множества
$M_{d+1}$ будет
$\mu(x) \ge \beta(x)2^{-d}$
и на бесконечном множестве
$M_{d}\setminus M_{d+1}$
будет
$\mu(x)=\beta(x)2^{-d}$.


Искомый ряд $\alpha$ определяется формулой
$\alpha(x)={\min\{\mu(x),\beta(x)2^{-d}\}}$.
\end{proof}

\begin{thm}\label{thm:3}
Для произвольного вычислимого ряда $\alpha$,
оценивающего снизу $\mu$
и на бесконечном множестве равного $\mu$,
множество
${\{x : \mu(x) > \alpha(x)\}}$ гиперпростое.
\end{thm}
(Напомним, что перечислимое множество
с бесконечным дополнением называется гиперпростым,
если в любой вычислимой бесконечной последовательности
непересекающихся отрезков натуральных чисел
существует отрезок, целиком вложенный в это множество.)
\begin{proof}
Пусть $T_j$~--- вычислимая последовательность
непересекающихся отрезков натуральных чисел.

Построим вспомогательный вычислимый ряд $\beta$.
Для каждого $m$ найд\"ем $j_m$, для которого
$\sum_{x\in T_{j_m}} \alpha(x) < 2^{-2m}$.
Это возможно, так как ряд $\mu(x)$ сходится,
$\alpha(x)\le \mu(x)$ и, следовательно,
вычислимый ряд $\alpha(x)$ сходится.
На отрезках $T_{j_m}$ положим $\beta(x)=\alpha(x)2^{m}$,
в остальных местах $\beta(x)=\alpha(x)$.
Поскольку
$$
\sum_{x\in\,\bigcup\limits_m T_{j_m}} \beta(x) <
\sum_m 2^m\cdot 2^{-2m} = 1\,,
$$
то ряд $\beta(x)$ сходится.
Поэтому ${\exists c \forall x\: \mu(x) > \beta(x)2^{-c}}$.
Из определения $\beta$ получается, что на отрезке
$T_{j_c}$ не может быть $x$, в котором $\alpha(x)=\mu(x)$.
\end{proof}



Перейд\"ем к языку сложности описаний.

Простая энтропия (введ\"енная Колмогоровым в 1965 году)~---
это минимальная длина кода
относительно оптимального кодирования.

Кодирование называется префиксным, если ни один код
не может быть продолжением другого кода.
Требование префиксности позволяет делить
последовательность закодированных сообщений
на отдельные сообщения без использования
вспомогательного символа (например, пробела).
Префиксная энтропия (введ\"енная Левиным в 1970 году)~---
это минимальная длина кода
относительно оптимального префиксного кодирования.

\smallskip

Бескодовые определения.

\smallskip

Простая энтропия~--- это минимальная с точностью
до аддитивной константы перечислимая сверху функция $KS$
(со значениями в $\N$),
для которой при любом $n$ выполнено
$|\{x : KS(x)<n\}| < 2^n$.

Префиксная энтропия~---  это минимальная с точностью
до аддитивной константы перечислимая сверху функция KP
(со значениями в $\N$),
для которой выполнено
$\sum_{x} 2^{-KP(x)} \le 1$.

\medskip

Из определений очевидно, что функции $KS$ и $KP$
стремятся к бесконечности,
и $\forall x\: KS(x)\le KP(x) + O(1)$.
Значительно сложнее доказывается, что разность
$(KP-KS)$ стремится к бесконечности.
(Четыре месяца назад доказательство было рассказано
нами на международном семинаре в Гейдельберге.
Ли и Витаньи в своей книге приводят этот факт
без доказательства
со ссылкой на неопубликованную рукопись Соловэя.)

Функции $KS$ и $KP$ имеют редкие,
но непредсказуемые падения.

\textsl{\small Здесь рисунок из файла graph.eps}

Г.~Маранджан в 1969 году доказал, что
функция $KS$ не имеет нетривиальных
частично вычислимых нижних оценок
(для функции $KP$ рассуждение аналогично).

Что касается вычислимых верхних оценок
простой энтропии,
то такой оценкой является, например,
$\ell(x)+C$, где $\ell(x)$~---
длина двоичной записи натурального числа $x$.

Из мощностных соображений следует, что
$$
\forall n \exists x\: \ell(x)=n \, \&\, KS(x)\ge n-1\,.
$$
С другой стороны, по определению $KS$
имеем $\exists c\forall x\: KS(x) < \ell(x)+c$.
Для каждого $C$ рассмотрим множество
$M_C=\{x : \ell(x)+C \le KS(x)\}$.
Для $C=-1$ это множество бесконечно,
для $C=c$ это множество пусто.
С ростом $C$ множество $M_C$ уменьшается.
Рассмотрим наибольшее $d$,
для которого $M_{d}$ бесконечно.
Ясно, что на дополнении до конечного множества
$M_{d+1}$ будет
$\ell(x)+d\ge KS(x)$
и на бесконечном множестве
$M_{d}\setminus M_{d+1}$
будет
$\ell(x)+d = KS(x)$.
Пусть функция $f$ равна $KS$
на конечном множестве $M_{d+1}$
и равна $\ell(x)+d$ в остальных местах.
Понятно, что $f$~--- вычислимая функция,
оценивающая сверху $KS$
и на бесконечном множестве равная $KS$.

\begin{thm}
Для \emph{произвольной}
вычислимой функции $f$, оценивающей сверху $KS$
и на бесконечном множестве равной $KS$,
множество $\{x : KS(x) < f(x)\}$ простое.
\end{thm}
(Напомним, что перечислимое множество
с бесконечным дополнением называется простым,
если в его дополнение нельзя вложить
бесконечное перечислимое подмножество.)
\begin{proof}
Предположим, что существует
бесконечное перечислимое множество $R$,
на котором $f(x)=KS(x)$.
Пусть $f'$~--- ограничение $f$ на $R$.
Тогда $f'$~--- частично вычислимая \emph{нижняя}
оценка на $KS$.
Последнее невозможно, поскольку $KS(x)\to\infty$.
\end{proof}

Теоремы~\ref{thm:2} и~\ref{thm:3}
на языке префиксной энтропии
приведены без доказательства в книге Ли и Витаньи
со ссылкой на неопубликованную рукопись Соловэя.
Сформулируем их.

\begin{thm}
Существует всюду определ\"енная
вычислимая функция $f$,
оценивающая сверху $KP$
и на бесконечном множестве равная $KP$.
\end{thm}

\begin{thm}
Для произвольной всюду определ\"енной
вычислимой функции $f$,
оценивающей сверху $KP$
и на бесконечном множестве равной $KP$,
множество
${\{x : KP(x) < f(x)\}}$ гиперпростое.
\end{thm}

\end{document}