\documentclass[landscape]{slides}
\usepackage{amsmath,amssymb}
\usepackage{hhline}
\ifx\pdfoutput\undefined
\usepackage{graphicx}
\else
\usepackage[pdftex]{graphicx}
\fi
\usepackage[T1]{fontenc}

\advance\textheight \headheight
\advance\textheight \headsep
\topmargin=-10mm
\headheight=0pt
\headsep=0pt
\advance\textheight -\topmargin

\advance\textwidth \marginparwidth
\marginparwidth=0pt
\marginparsep=0pt
\advance\oddsidemargin -1cm
\advance\textwidth 1cm

%\hyphenpenalty=10000
\parindent=0pt


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

\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\renewcommand{\phi}{\varphi}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\half}{\frac{1}{2}}


\begin{document}
\begin{titlepage}
\begin{center}
\large\bf
Constructive series,\\
descriptive complexity,\\
simple and hypersimple sets
\end{center}
\vspace{7ex}
\centerline{Alexei Semenov\hfil Andrej Muchnik}
\vspace{3ex}
\centerline{\it Institute of New Technologies}
\centerline{\it Moscow}
\end{titlepage}


\begin{slide}

$\logi{1} x= \log x,\quad \logi{i+1} x=\log(\logi{i} x)$
\begin{align*}
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},
&\ldots\\
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},
&\ldots
\end{align*}

\vfil

$$
\infty > \sum a_m^0,\quad\sum a_m^1,\quad\sum a_m^2,\quad\ldots
\hspace{0.5em}?\hspace{0.5em}
\ldots\quad\sum b_m^2,\quad\sum b_m^1,\quad\sum b_m^0\;\; =\infty
$$

\vfil

$a^n_m=\frac{1}{m\logi{1}m\ldots\logi{n-1}(\logi{n} m)^2}$\,,
$b^n_m=\frac{1}{m\logi{1}m\ldots\logi{n-1}\logi{n} m}$\,,

$$
 b^n_m/a^n_m=\logi{n} m
$$

\vfil

\end{slide}


\begin{slide}

\centerline{\bf Computable positive series}
\centerline{(w.l.o.g., members of series are of the form $2^{-n}$)}

\vfill

$$
\sum\alpha_m=\infty
\quad\Rightarrow\quad
\exists\beta_m\;:\mspace{9mu}
\frac{\beta_m}{\alpha_m}\to 0
\mspace{9mu}
\&
\mspace{9mu}
\sum\beta_m=\infty
$$

$$
\begin{array}{ccccccc}
\sum\alpha_m > 2 && \sum\alpha_m > 4 && \sum\alpha_m > 8 &&
\phantom{\sum\alpha_m > 16}\\
&\vline&&\vline&&\vline&\\
\hhline{-|--|--|--}
&\vline&&\vline&&\vline&\\
\beta_m=\alpha_m/2 && \beta_m=\alpha_m/4  && \beta_m=\alpha_m/8  &&
\end{array}
\cdots
$$

\vfill
\end{slide}

\begin{slide}

\centerline{\bf Computable positive series}

\vfill

$$
\sum\alpha_m < \infty \text{ effectively }
\quad\Rightarrow\quad
\exists\beta_m\;:\mspace{9mu}
\frac{\beta_m}{\alpha_m}\to \infty
\mspace{9mu}
\&
\mspace{9mu}
\sum\beta_m < \infty  \text{ effectively }
$$

$$
\begin{array}{ccccccc}
\sum^{\infty}\alpha_m < 1/4 &&
\sum^{\infty}\alpha_m < 1/16 &&
\sum^{\infty}\alpha_m < 1/64 &&
\phantom{\sum\alpha_m < 256}\\
&\vline&&\vline&&\vline&\\
\hhline{-|--|--|--}
&\vline&&\vline&&\vline&\\
\beta_m=\alpha_m\cdot 2 && \beta_m=\alpha_m \cdot 4
&& \beta_m=\alpha_m \cdot 8  &&
\end{array}
\cdots
$$

\vfill
\end{slide}


\begin{slide}

\centerline{\bf Computable positive series}

\vfill
\textbf{Theorem 1.}
$$
\exists \alpha_m\mspace{6mu} \sum\alpha_m < \infty
\quad\&\quad
\left(
\forall \beta_m\mspace{12mu}
\frac{\beta_m}{\alpha_m}\to \infty
\mspace{9mu}
\Rightarrow
\mspace{9mu}
\sum\beta_m = \infty
\right)
$$

\vfill

$$
\forall \alpha_m\mspace{6mu} \sum\alpha_m < \infty
\quad
\Rightarrow
\quad
\left(
\exists \beta_m\mspace{12mu}
\sum\beta_m < \infty
\mspace{9mu}
\&
\mspace{9mu}
\sup\frac{\beta_m}{\alpha_m} = \infty
\right)
$$

\vfill
\end{slide}

\begin{slide}

\centerline{\bf Series computably approximated from below}
\centerline{(enumerable series)}
\vfill

\textbf{Definition}\\
\hspace*{0.4em}
$\nu(x)$ is \emph{enumerable series} iff
$\exists$ computable function $\nu(x,t)\ge 0$\\
\hspace*{3em}
$\forall x\;\;\nu(x)=\lim\limits_{t\to\infty} \nu(x,t)$\\
\hspace*{3em}
$\forall x,t\;\;\nu(x,t+1)\ge \nu(x,t)$\\
\hspace*{3em}
$\forall t\;\;\{x\mid\nu(x,t)\ne 0\}$ is finite

\textbf{Theorem 2 (Levin).}
$$
\exists \mu(x)\;:\mspace{6mu}
\sum \mu(x) \le 1
\mspace{9mu}
\&
\mspace{9mu}
\forall \nu(x)
\bigl(
\sum \nu(x) \le 1
\mspace{6mu}
\Rightarrow
\mspace{6mu}
\exists C\,
\forall x\;
\mu(x)\ge \nu(x)\cdot 2^{-C}
\bigr)
$$

This $\mu$ is
\underline{unique} up to a multiplicative constant

\vfill
\end{slide}

\begin{slide}

\centerline{\bf Series computably approximated from below}
\vfill

\textbf{Theorem 2 (Levin).}
$$
\exists \mu(x)\;:\mspace{6mu}
\sum \mu(x) \le 1
\mspace{9mu}
\&
\mspace{9mu}
\forall \nu(x)
\bigl(
\sum \nu(x) \le 1
\mspace{6mu}
\Rightarrow
\mspace{6mu}
\exists C\,
\forall x\;
\mu(x)\ge \nu(x)\cdot 2^{-C}
\bigr)
$$

\textbf{Fact I.}\\
All computable enumerations of enumerable series
are $\mathsf{m}$-reducible\\
to some universal computable enumeration
$n\mapsto \nu_n$.

\textbf{Fact II.}\\
Each enumerable series $\nu$ can be
effectively transformed\\
into an enumerable series $\nu'$ such that\\
\hspace*{1em} $\sum \nu'(x)\le 1$,\\
\hspace*{1em}
$\sum \nu(x)\le 1 \;\Rightarrow\:\forall x\, \nu'(x)=\nu(x)$.

$$
\mu(x)\rightleftharpoons
\sum_n 2^{-n} \nu'_n(x)
$$

\vfill
\end{slide}


\begin{slide}
\centerline{\bf Bounds for $\mu$}
\vfill

\textbf{Theorem 3.} (cf. Marandjian)\\
For any partial computable function $\gamma$
$$
\exists C\qquad
\forall x\in \mathrm{Dom}(\gamma)\;\:\mu(x)\le \gamma(x)
\quad\Rightarrow\quad
\forall x\in \mathrm{Dom}(\gamma)\;\:\gamma(x) \ge 2^{-C}\,.
$$

\textbf{Theorem 4.}\\
There exists a computable series $\alpha$ such that\\
\hspace*{1em}$\forall x\;\;\;\alpha(x)\le\mu(x)$,\\
\hspace*{1em}$\exists^\infty x\;\alpha(x)=\mu(x)$.

Obviously, Theorem 4 implies Theorem 1.
\vfill
\end{slide}

%% table 1
\begin{slide}
\centerline{\bf Proof of Theorem 4}
\vfill
$$
\begin{array}{c|c|c|c|c|l}
\hline
1
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\hline
2
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\hline
\vdots
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\hline
i
&
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\phantom{\mu(x^1_i)>2^{-i}}
\end{array}
&
\begin{array}{c}
\phantom{\beta(x^2_i)=2^{-i}\rule{0pt}{2.6ex}}\\[0.5ex]
\phantom{\mu(x^2_i)>2^{-i}}
\end{array}
&
\phantom{\text{\hbox to 5em {\hfil$\cdots$\hfil}}}
&
\begin{array}{c}
\phantom{\beta(x^j_i)=2^{-i}\rule{0pt}{2.6ex}}\\[0.5ex]
\phantom{\mu(x^j_i)<2^{-i}}
\end{array}
&
\qquad
\\
\hline
\vdots
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\end{array}
$$

\vfill
\end{slide}

%% table 2
\begin{slide}
\centerline{\bf Proof of Theorem 4}
\vfill
$$
\begin{array}{c|c|c|c|c|l}
\hline
1
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\hline
2
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\hline
\vdots
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\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]
\phantom{\mu(x^2_i)>2^{-i}}
\end{array}
&
\phantom{\text{\hbox to 5em {\hfil$\cdots$\hfil}}}
&
\begin{array}{c}
\phantom{\beta(x^j_i)=2^{-i}\rule{0pt}{2.6ex}}\\[0.5ex]
\phantom{\mu(x^j_i)<2^{-i}}
\end{array}
&
\qquad
\\
\hline
\vdots
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\end{array}
$$

\vfill
\end{slide}

%%% table 3
\begin{slide}
\centerline{\bf Proof of Theorem 4}
\vfill
$$
\begin{array}{c|c|c|c|c|l}
\hline
1
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\hline
2
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\hline
\vdots
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\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
\vphantom{
\begin{array}{c}
\beta(x^1_i)=2^{-i}\rule{0pt}{2.6ex}\\[0.5ex]
\mu(x^1_i)>2^{-i}
\end{array}
}&&&&&\\
\end{array}
$$

\vfill
\end{slide}

\begin{slide}
\centerline{\bf Proof of Theorem 4}
\vfill
$\{x : \mu(x) \le\beta(x) \}$ is infinite

$\beta$ is computable

$\sum\beta(x)\le\sum\limits_x\mu(x)+\sum\limits_i 2^{-i}\le 1+1$

${\exists c\forall x\mspace{9mu} \mu(x) > \beta(x)2^{-c}}$

$\{x : \mu(x) \le\beta(x)2^{-c} \}$ is empty

\bigskip

$\exists d\in [0,c]$
\begin{gather*}
\{x : \mu(x) \le\beta(x)2^{-d} \} \text{ is infinite}\\
\{x : \mu(x) \le\beta(x)2^{-(d+1)} \} \text{ is finite}
\end{gather*}
\vfill
\end{slide}

\begin{slide}
\centerline{\bf Proof of Theorem 4}
\vfill

$$
\exists^\infty x\mspace{9mu} \mu(x)=\beta(x)2^{-d}
$$

$$
\forall^\infty x\mspace{9mu} \mu(x)\ge\beta(x)2^{-d}
$$

\medskip

$$
\alpha(x)={\min\{\mu(x),\beta(x)2^{-d}\}}
$$

\vfill
\end{slide}


\begin{slide}
\centerline{\bf Bounds for $\mu$}
\vfill

\textbf{Theorem 5.}\\
For any computable series $\alpha(x)$
\begin{gather*}
\forall x\;\alpha(x)\le\mu(x),\quad
\exists^\infty x\;\alpha(x)=\mu(x)\\[1ex]
\Downarrow\\[1ex]
\text{the set }
S={\{x : \alpha(x) < \mu(x) \}}
\text{ is hypersimple}
\end{gather*}

\vfill

(An enumerable set $S$ with infinite complement
is \emph{hypersimple}\\
if for any computable sequence $0 < j_1 < j_2 < \ldots$\\
there exists $k$ such that
$[j_k,j_{k+1})\subset S$.)

\vfill
\end{slide}


\begin{slide}
\centerline{\bf Proof of Theorem 5}
\vfill

{\small
$$
\begin{array}{ccccc}
&& \sum\alpha(x) < 1/4
&& \\
&\vline&&\vline&\\
\hhline{-|--|--}
&\vline&&\vline&\\
\beta(x)=\alpha(x) && \beta(x)=\alpha(x)\cdot 2
&& \beta(x)=\alpha(x)
\end{array}
\;\;\cdots\;\;
\begin{array}{ccccc}
&& \sum\alpha(x) < 2^{-2m}
&& \\
&\vline&&\vline&\\
\hhline{-|--|--}
&\vline&&\vline&\\
&& \beta(x)=\alpha(x)\cdot 2^{m}
&&
\end{array}
\;\;\cdots
$$
}

$\beta$ is computable

$\sum\beta(x) \le
  \sum_x\alpha(x)+\sum_m 2^{-2m}\cdot 2^{m} \le
  \sum_x\mu(x)   +\sum_m 2^{-m}
  \le 1+1$

$\exists c\;\forall x\;\; \mu(x)\ge\beta(x)2^{-c}$

The whole segment corresponding to $m=c$
is included in $S$.

\vfill
\end{slide}

\begin{slide}
\centerline{\bf Descriptive complexity}
\vfill

\emph{Plain entropy} (Kolmogorov, 1965)
$KS$ is the minimal length\\
of a code word
with respect to an optimal coding.

A coding is called \emph{prefix} if
no code word is a beginning\\
of any other code word.
(Useful for dividing a message flow.)

\emph{Prefix entropy} (Levin, 1970)
$KP$ is the minimal length\\
of a code word
with respect to an optimal prefix coding.

\vfill
\end{slide}


\begin{slide}
\centerline{\bf Plain entropy}
\vfill
\textbf{Theorem.}\\
There exists a computable function $f$ such that\\
\hspace*{1em}$\forall x\;\;\;f(x)\ge KS(x)$,\\
\hspace*{1em}$\exists^\infty x\; f(x)=KS(x)$.

($f(x)=\log_2(x)+O(1)$)

\bigskip

\textbf{Theorem 6.}\\
For any computable function $f$
\begin{gather*}
\forall x\; f(x)\ge KS(x),\quad
\exists^\infty x\; f(x)= KS(x)\\[1ex]
\Downarrow\\[1ex]
\text{the set }
S={\{x : f(x) > KS(x) \}}
\text{ is simple}
\end{gather*}

\vfill
\end{slide}


\begin{slide}
\centerline{\bf Prefix entropy}
\vfill

\textbf{Theorem (Levin).}\\
$KP(x)=-\log_2 \mu(x)+O(1)$

\vfill

\textbf{Theorem 7 (Solovay).}\\
There exists a computable function $f$ such that\\
\hspace*{1em}$\forall x\;\;\;f(x)\ge KP(x)$,\\
\hspace*{1em}$\exists^\infty x\; f(x)=KP(x)$.

\bigskip

\textbf{Theorem 8 (Solovay).}\\
For any computable function $f$
\begin{gather*}
\forall x\; f(x)\ge KP(x),\quad
\exists^\infty x\; f(x)= KP(x)\\[1ex]
\Downarrow\\[1ex]
\text{the set }
S={\{x : f(x) > KP(x) \}}
\text{ is hypersimple}
\end{gather*}


\vfill
\end{slide}



\begin{slide}
\end{slide}

\end{document}

\begin{slide}
\includegraphics[width=\textwidth]{graph3}
\end{slide}
