%%From: "Lenya Positselsky" <posic@mccme.ru>
%%Date: Thu, 29 Jul 1999 18:45:18 GMT
%%To: posic@IUM.IPS.RAS.RU
%%Subject: entropy
%%
%
%From: shen@mccme.ru
%Subject: sample-for-Senya
%To: posic@ium.ips.ras.ru
%Date: Tue, 6 Jul 1999 02:26:34 +0400 (MSD)

\documentclass[12pt,a4paper]{article}
\usepackage{latexsym, amsmath, amsthm}

\tolerance=3000
\emergencystretch=2em

\setcounter{topnumber}{5}
\setcounter{bottomnumber}{5}
\renewcommand{\topfraction}{1}
\renewcommand{\bottomfraction}{1}
\setcounter{totalnumber}{5}
\renewcommand{\textfraction}{0}
\renewcommand{\floatpagefraction}{0.1}

\renewcommand{\itshape}{\slshape}

\newfont{\Bbb}{msbm10}
\newcommand{\BbbN}{{\mbox{\Bbb N}}}
\newcommand{\ssne}{\;{\mbox{\Bbb\symbol{"28}}}\;}
\newcommand{\overA}{{\,\overline{\!A}}}
\newcommand{\overU}{{\,\overline{\!U}}}

\newcommand{\sumlim}{\sum\limits}
\newcommand{\bigcuplim}{\bigcup\limits}

%\newcounter{df}[part]
%\newenvironment{df}{\par\medskip\refstepcounter{df}%
%{\bf Definition \Roman{part}.\arabic{df}}}%
%{\par\medskip}
%
%\newenvironment{dfn}[1]{\par\medskip\refstepcounter{df}%
%{\bf Definition \Roman{part}.\arabic{df} (#1)}}%
%{\par\medskip}

\newtheorem{thm}{Theorem}[part]
\newtheorem*{pr}{Statement}
\newtheorem*{prob}{Problem}
\newtheorem*{lem}{Lemma}
\newtheorem*{cor}{Corollary}
\newtheorem{df}{Definition}[part]
\newenvironment{pf}{\par\medskip\noindent{\bf Proof:}}%
{\hfill$\Box$\par\medskip}
\newenvironment{pft}{\par\medskip\noindent{\bf Proof of Theorem.}}%
{\nopagebreak\hfill$\Box$\par\medskip}
\newenvironment{pfl}{\par\medskip\noindent{\bf Proof of Lemma.}}%
{\nopagebreak\hfill$\Box$\par\medskip}

%\renewcommand{\partname}{Part}

%{\mathrel{\mathop{\subset}\limits_{\ne}}}
%%{\mathrel{\hbox to 0pt{\hspace{5pt}\raisebox{-3.5pt}
%%{\tiny$/$}\hss}\subseteq}}

%\newcommand{\lebt}{\mathrel{\mathop{\le}\limits_{\strut bT}}}
%{\stackrel{\le}{bt}}

\begin{document}

%\title{Kolmogorov entropy in the framework of general theory of
%algorithms}

\title{Kolmogorov Entropy in the Context of General Theory of Algorithms}

\author{Andrej A.~Muchnik \and Semen Ye.~Positselsky}

\date{\normalsize
Institute of New Technologies of Education (INT), \\
109004, Moscow, Nizhnyaya Radishchevskaya str., 10. \\
%%������ ����������� �����, 10
Fax: 7-(095)-915-6963}

\maketitle

Main results of this paper were reported at Kolmogorov Seminar of Moscow
State University in the Fall of~1998.%
\footnote{The results of the first part were annonced in~\cite{MP}.}
The authors express their gratitude to the Institute of New Technologies
of Education, Moscow, which supported their research in these unfortunate
for all Russian science days. We thank the leaders of Kolmogorov
Seminar---A.~Semenov, A.~Shen, N.~Vereshchagin---and its participants for
always fruitful discussions.  B.~Durand\- gave favorable conditions
for this research by inviting the first author
through a CNRS exchange program to finish the work in
Laboratoire d'Informatique du Parallelisme (Lyon, France).
L.~Positselsky and M.~Semenova helped us very much with translation of
our text from Russian to English.
F.~Stephan read the preliminary version of this paper carefully
and made extremely useful remarks.
We thank all who contributed to our work.

\part*{\Large \bf Preface}

In 1960-s the notion of entropy of a finite object was introduced in the
works of A.~Kolmogorov and R. Solomonoff. An important contribution of this
notion is constituted by formal mathematical explication of the concept
of randomness (in respect to a probability distribution). In this paper
we do not consider distributions, neither other structures on finite
objects (like the pairing function). We are interested in a purely
algorithmic characterization of the entropy function. Let us mention that
alternative definitions of entropy were given after the first one. They
are systematized in~\cite{UsSh}. If the opposite is not mentioned, our
considerations will be applicable to any of these notions of entropy.
To make our considerations complete and self-contained, we describe
both new and known results.

An entropy function maps a constructive universe%
\footnote{The reader can learn about constructive objects
and constructive universes (aggregates) in~\cite{UsSem}.
}
(for example---the set
of all finite binary strings) into the set of all positive integers.
This function, denoted by~$K(\cdot)$, is enumerable from above (or upper
computable). This means that the overgraph $M=\{(x,n)\ |\ K(x)<n\}$ is
enumerable. In our study of the set~$M$ we discovered several algorithmic
properties and notions, which are interesting independently of
the entropy context.

In Part~I we study these notions.
We shall utilize several types of algorithmic reducibility. Among many
reducibilities introduced in the theory of algorithms, we have chosen
seven. The first is $m$-reducibility. Its role for computability is
similar to that of homomorphism in algebra. We write $A\le_m B$ if
$A$ is an inverse image of~$B$ under a total computable function.
The other six reducibilities are transitive and closed under Boolean
operations. (This means that $A\le B$ and $B\le C$ imply $A\le C$,
\ $A\le C$ and $B\le C$ imply $A\cup B\le C$, \ $A\le B$ implies
$\overA \le B$.) Namely, we consider the Turing (or $T$-) reducibility,
the weak truth-table (or $w$-) reducibility, the truth-table (or $tt$-)
reducibility, and their bounded versions ($bT$, $bw$, $btt$).
As usually, the Turing reducibility uses the oracle without restrictions.
For $w$-reducibility, the oracle is used once and is asked several
(finite number of) questions. For the truth-table reducibility,
the reducing algorithms gives a result for any answers of the oracle,
even those not corresponding to the set to which we reduce.
The bounded reducibilities assume that the number of questions
to the oracle is limited by a constant independent of the input.

\begin{pr}
By a compactness argument, any tt-reducing algorithm can be effectively
transformed to an algorithm satisfying both the $tt$- and $w$-restrictions.
Similarly, a $btt$-reducing algorithm can be effectively transformed to
an algorithm satisfying both the $btt$- and $bw$-restrictions.
In this transformation, if the original algorithm asks no more than $c$
questions to the oracle, the new algorithm will ask no more than $2^c$
questions.
\end{pr}

Proof of this statement is straightforward.

Further on, discussing the $tt$- ($btt$-) reducing algorithms we will
assume that they are also restricted by $w$ ($bw$).

Clearly, the transitivity and Boolean-closure properties for all
reducibilities are valid effectively. In the following diagram
the arrows are directed from stronger reducibilities to weaker ones:

\begin{figure}[!tbh]
\vspace{-7.5pt}
\unitlength=1.2pt
\begin{center}
\begin{picture}(240,100)
\put(40,80){\makebox[0pt][c]{$T$}}
\put(100,80){\makebox[0pt][c]{$w$}}
\put(160,80){\makebox[0pt][c]{$tt$}}
\put(40,40){\makebox[0pt][c]{$bT$}}
\put(100,40){\makebox[0pt][c]{$bw$}}
\put(160,40){\makebox[0pt][c]{$btt$}}
\put(205,10){\makebox[0pt][c]{$m$}}

\put(85,83){\vector(-1,0){30}}
\put(85,43){\vector(-1,0){30}}
\put(145,83){\vector(-1,0){30}}
\put(145,43){\vector(-1,0){30}}

\put(40,53){\vector(0,1){20}}
\put(100,53){\vector(0,1){20}}
\put(160,53){\vector(0,1){20}}

\put(195,18){\vector(-3,2){25}}

\end{picture}
\end{center}
\vspace{-20pt}
\end{figure}

Let us now outline the further content of the paper.

In Part I we would like to mention a strengthening of Post's theorem on
non-$btt$-completeness of simple sets. It is proved that simple sets
are even non-$bT$-complete.
This follows from the fact that the complete $bT$-degree contains
exactly one $btt$-degree (not only among the enumerable sets).

Part II needs familiarity with the definitions of unconditional and
conditional entropies (the simple and prefix ones). We study the conditional
entropy $K(\cdot|\cdot)$ first. It is enumerable from above and we prove
that the enumerable set $M = \{(x,y,n)\ |\ K(x|y)<n\}$ is $m$-complete.
By a theorem of J.~Myhill, all $m$-complete enumerable sets are
recursively isomorphic.
Hence, we get a final algorithmic characterization of conditional entropy.
The situation with unconditional entropy is more complicated.
Its overgraph is not $bT$-complete, but it is $w$-complete. It remains
to resolve the problem of its $tt$-completeness. M.~Kummer proved that
the overgraph of \underline{simple} entropy is $tt$-complete.
Let us recall here that any entropy consists of a countable
family of functions. The difference between any two members of the
family is bounded. In the previous consideration all results were
equally true for all members of any entropy family. Unexpectedly,
it is not so now: there are functions of \underline{prefix} entropy
for which the overgraph is $tt$-complete and such functions for which
the overgraph is not $tt$-complete.

In Part II we also prove an interesting inequality%
\footnote{Here $KS$ denotes the simple entropy and $KP$ denotes
the prefix entropy.  It is well known that
$KS(z) - O(1) < KP(z) < KS(z) + O(\log(KS(z)))$.
}:
$$
\forall d\ \exists x,y\ (KS(x)+d<KS(y)\ \land\ KP(y)+d<KP(x)).
$$

So, ``up to an additive logarithm'' the simple and prefix entropies are
the same, but in closer look they are very different.


\part{}

In~1956 Albert Muchnik introduced the following notion~\cite{Much}.
\begin{df}\label{d11}
An enumerable set $A$ is called $r$-separable if for any enumerable
set~$B$ such that $A\cap B =\emptyset$ there exists a decidable set~$C$
that separates $A$ from $B$ (that is~$A\subset C$ and $B\cap
C=\emptyset$).
\end{df}

Obviously, all decidable sets and all simple sets are $r$-separable.
M.~Kummer and F.~Stephan proved that the enumerable
frequency decidable%
\footnote{A set $G$ is called frequency decidable with parameter $m$
if there is a computable function $\alpha$ such that for each set $H$
of $m$ elements $\alpha(H)$ is a function from $H$ to $\{0,1\}$ which
differs from the restriction of the characteristic function of $G$.
}
sets are $r$-separable~\cite{KS}.
For any function $f$ consider the set $\{\,(x,n)\vert f(x)<n\}$;
we will call it the {\em overgraph\/} of~$f$.
The overgraph of an entropy function is also $r$-separable.
It is interesting to note that the very rich class of frequency decidable
sets does not contain the overgraph of an entropy function
(M.~Kummer's theorem~\cite{Kum}). On the other hand,
no $m$-complete enumerable set is $r$-separable
(this follows from two facts: all $m$-complete enumerable sets
are recursively isomorphic to the universal set
and there exists a nonseparable pair of enumerable sets).

In the general theory of algorithms, many notions find their effective
analogs (often in various ways).

\begin{df}[S.~Positselsky]\label{d12}
An $r$-separable set $A$ is called effectively $r$-separable if there
exists the following algorithm $\gamma$.  For any enumerable set $B$
not intersecting~$A$, the algorithm~$\gamma$ terminates on the text
of any program~$\beta$ enumerating~$B$.
Besides, $\gamma(\beta)$ is the text of the program for recognition
of some set~$C$ that separates~$A$ from~$B$.
(The program for recognition of a set outputs $1$ on the elements of
this set and $0$~on the other elements).
\end{df}

It is clear that all decidable sets are effectively $r$-separable.

\begin{thm}[S.~Positselsky]\label{t1}
All effectively $r$-separable sets are decidable.
\end{thm}

\begin{pf}
Here and in the sequel we will construct enumerable sets using
in the construction the text of a program enumerating the set that
we are constructing.
To avoid a vicious circle, we must construct the set corresponding
to a program enumerating another set.
Then we make the two sets coincide, using the fixed point
theorem of S.~Kleene.
The same method is used to construct computable functions
(partially defined).

Let $A$ be an effectively $r$-separable set. Suppose an algorithm $\gamma$
ensures this effectiveness. For each~$n$ let us construct the set~$B_n$,
which is enumerated by the program $\beta_n$. If $\gamma$ is defined on
$\beta_n$, let us run the program $\gamma(\beta_n)$ on the input $n$.
If the output of $\gamma(\beta_n)$ on the input $n$ is equal to~$1$,
then~$B_n=\{n\}$.
If either $\gamma$ is not defined on $\beta_n$, or the output of
the program $\gamma(\beta_n)$ on the input $n$ is not defined
or is not equal to~$1$, then $B_n=\emptyset$.

We claim that $n\notin A$ $\Longleftrightarrow$ $[\gamma(\beta_n)](n)=0$;
therefore, the complement of the set~$A$ is enumerable.

Let us prove ``$\Longrightarrow$''. If $n\notin A$, then $B_n$
in any case does not intersect~$A$. Therefore the algorithm
$\gamma$ is defined on $\beta_n$ and the program
$\gamma(\beta_n)$ is defined on any input.
If $[\gamma(\beta_n)](n)=1$, then $B_n=\{n\}$.
But the set recognized by $\gamma(\beta_n)$ separates $A$ from $B_n$.
We see that $[\gamma(\beta_n)](n)=0$.

Let us prove ``$\Longleftarrow$''. If $[\gamma(\beta_n)](n)=0$,
then $B_n=\emptyset$.
It follows from the definition of $\gamma$ that
$A\subset\{x\ |\ [\gamma(\beta_n)](x)=1\}$.
We see that $n\notin A$.
\end{pf}

More fruitfull is the following weak effectivization of $r$-separability.

\begin{df}[S.~Positselsky]\label{d13}
An $r$-separable set $A$ is called resilient if there exists the
following algorithm $\gamma$. If $B$ is an enumerable set not intersecting
$A$, this algorithm $\gamma$ is defined on the text of any program
$\beta$ enumerating~$B$. The output $\gamma(\beta)$ is the text of
a program enumerating a decidable set $C$ which separates $A$ from~$B$.
\end{df}

The only difference between resilience and effective $r$-separability
is that for the former, though the separating set~$C$ remains decidable,
one finds only an enumeration (and not recognition) of~$C$ starting from
an enumeration of~$B$.

It is clear that all decidable sets and all strongly effectively simple%
%%
\footnote{An enumerable set $A$ is called strongly effectively simple
if given a program enumerating a set~$B$ not intersecting~$A$ one can
effectively construct a number larger than $\max(B)$.
The simple set of E.~Post~\cite{Post} is strongly effectively simple.}
%%
sets are resilient.  In the secont part of this paper we will show that
the overgraph of an entropy function is resilient.

The classes of $r$-separable and resilient sets have a good property
of being lattices (just as the classes of decidable, enumerable,
frequency decidable sets).

\begin{thm}[S.~Positselsky]\label{t2}
The class of $r$-separable sets is closed under the operations
of union and intersection.

The class of resilient sets is effectively closed under
the operations of union and intersection.
\end{thm}

In the second statement, the effectiveness means that starting from
algorithms enumerating two sets $A_1$ and $A_2$ and algorithms
ensuring their resilience, one effectively constructs algorithms
ensuring the enumerability and resilience of $A_1\cup A_2$
and $A_1\cap A_2$.

\begin{pf}
The proofs of these two statements are very similar.
Let $A_1$ and $A_2$ be $r$-separable (or, respectively, resilient) sets.

Let us prove that the set $A_1\cup A_2$ is $r$-separable (resilient).
Let $B$ be an enumerable set not intersecting $A_1\cup A_2$.
Then $B$ is separated from $A_1$ and $B$ is separated from $A_2$.
We can find enumeration programs for two decidable sets
$C_1$ and $C_2$ such that $A_1\subset C_1$, $A_2\subset C_2$,
$B\cap C_1=\emptyset$, $B\cap C_2=\nolinebreak\emptyset$.
Then the sets $A_1\cup A_2$ and $B$ are separated by the decidable set
$C_1\cup C_2$ (whose enumeration program is known).

Let us prove that the set $A_1\cap A_2$  is $r$-separable (resilient).
Let $B$ be an enumerable set which does not intersect $A_1\cap A_2$.
Since $A_1\cap (A_2\cap B)=\emptyset$, the set $A_1$ is separated
from the enumerable set $A_2\cap B$.
We can find an enumeration program for a decidable set $C$ such that
$A_1\subset C$ and $(A_2\cap B)\cap C=\emptyset$.
Since $A_2\cap(B\cap C)=\emptyset$, the set $A_2$ is separated from
the enumerable set $B\cap C$ (whose enumeration program we know).
Therefore, we can find an enumeration program for a decidable set~$D$
such that $A_2\subset D$ and $(B\cap C)\cap D=\emptyset$.
Now we see that $A_1\cap A_2\subset C\cap D$ and
$B\cap(C\cap D)=\emptyset$.
Thus the decidable set $C\cap D$ separates $A_1\cap A_2$
from $B$ (and we know an enumeration program of $C\cap D$).
\end{pf}

It is obvious that the class of $r$-separable (resilient) sets is
(effectively) closed under cylindrification.
It follows that this class is also (effectively) closed
under many other operations. For example, the Cartesian product
of two sets is an intersection of two cylinders.

We turn now to the questions of completeness with respect to
the various reducibilities.
We need the following result, which is due to A.~Lachlan~\cite{Lah}.
If the set $A\cap B$ is $m$-complete and the set $A$ is enumerable,
then either $A$ or $B$ is $m$-complete.
Here we formulate and give a new proof of an effectivization
of this statement.

\begin{thm}[A.~Lachlan]\label{t3}
Let $U$ be an enumerable $m$-complete set. Then there exists
an algorithm that given a program enumerating a set~$A$
constructs a program computing a function $f$ such that
$f(U)\subset U$, $f(\overU)\subset A\setminus U$, and if the set
$U\cup A$ is not $m$-complete, then $f$ is a total function.
\end{thm}

\begin{pf}
Using the fixed point theorem, let us construct an auxiliary function
$\lambda xyz.g_{x,y}(z)$. Having a program computing this function and
two elements~$x$ and $y$, we find the program computing
$h=\lambda z.g_{x,y}(z)$. It is known that given a program $h$ one can
effectively find an input $v$ such that if $h(v)$ terminates, then
$v\in U\Longleftrightarrow h(v)\in U$.%
\footnote{For the universal set $U$ this fact immediately
follows from the fixed point theorem.}
Running the enumerations of the sets $U$ and $A$, we wait until $y$ is
caught in~$U$ or $v$ is caught in~$U\cup A$. If neither of the two events
ever happens, then $g_{x,y}(z)$ is undefined for all~$z$. If it is first
revealed that $y\in U$, then $\forall z\ g_{x,y}(z)=y$. If it is first
revealed that $v\in U\cup A$, then $\forall z\ g_{x,y}(z)=x$.

Let us construct the function $\lambda x.f(x)$. Given an input~$x$, we
look over all the values of~$y$ and find a value such that for the
corresponding $v$ it is true that $g_{x,y}(v)=x$. Then we put $f(x)=v$.

Let us prove that the function $f$ is well defined. We will show that if
for some $x_0$ the value of $f(x_0)$ is not defined, then the set $U\cup
A$ is $m$-complete.

Construct the function $\lambda y.p(y)$ which $m$-reduces the set $U$
to the set $U\cup A$. Let $p(y)$ be equal to $v$ that corresponds
to the pair~$x_0$, $y$. If $y\in U$, then $\forall x,z$ $g_{x,y}(z)$
is defined. It follows that $g_{x_0,y}(v)=y$. This implies that
$v\in U$ $\Longleftrightarrow$ $y\in U$. That is, $p(y)\in U$.
If $y\notin U$, then $v\notin U\cup A$; otherwise we have
$g_{x_0,y}(v)=x_0$ and $f(x_0)=v$.
Thus, $y\in U$ $\Longleftrightarrow$ $p(y)\in U\cup A$.

Suppose that the function $f$ is defined on an input~$x$. This means
that $\exists y\ g_{x,y}(f(x))=x$. It follows that $f(x)\in U\cup A$
and $f(x)\in U\Longleftrightarrow x\in U$.
This proves the desired property of~$f$.

\end{pf}

Let us illustrate this proof by the next three pictures.

\begin{figure}[!tbh]
  \vspace{-10pt}
\begin{center}
\qquad\qquad\qquad
\unitlength=0.4pt
\begin{picture}(400,250)
%\put(50,260){function $g_{x,y}$}
\put(100,200){\vector(-1,-2){80}}
\put(100,200){\circle*{6}}
\put(20,40){\circle*{6}}
\put(180,40){\circle*{6}}
\put(90,210){$v$}
\put(100,200){\vector(1,-2){80}}
\put(10,20){$x$}
\put(180,20){$y$}
\put(-90,120){$v\in U\cup A$}
\put(160,120){$y\in U$}
\end{picture}
\end{center}
  \vspace{-7.5pt}
\caption{function $g_{x,y}$}
\end{figure}

\begin{figure}[!tbh]
  \vspace{-7.5pt}
\begin{center}
\unitlength=0.4pt
\begin{picture}(400,250)
\put(20,40){\vector(1,2){80}}
\put(100,200){\circle*{6}}
\put(20,40){\circle*{6}}
\put(180,40){\circle*{6}}
\put(90,210){$v$}
\multiput(100,200)(17,-34){5}%{\circle*{10}}%
{\line(1,-2){13}}
\put(10,20){$x$}
\put(180,20){$y$}
\put(-90,120){$g_{x,y}(v)=x$}
%\put(160,120){$y\in U$}

%------------------------------------

\put(300,50){\circle{50}}
\put(290,40){\small $U$}
\put(315,50){\circle*{6}}
\put(315,90){\circle*{6}}
\put(315,50){\vector(1,0){105}}
\put(315,90){\vector(4,-1){80}}
\put(430,50){\circle{50}}
\put(430,70){\circle{130}}
\put(425,40){\small $U$}
\put(396,85){\small $U\cup A$}
\end{picture}
\end{center}
\vspace{-7.5pt}
\caption{function $f(x)$}
\end{figure}

\begin{figure}[!tbh]
  \vspace{-7.5pt}
\begin{center}
\unitlength=0.4pt
\begin{picture}(400,250)
\put(180,40){\vector(-1,2){80}}
\put(100,200){\circle*{6}}
\put(20,40){\circle*{6}}
\put(180,40){\circle*{6}}
\put(90,210){$v$}
\multiput(100,200)(-17,-34){5}%{\circle*{10}}%
{\line(-1,-2){13}}
\put(10,20){$x_0$}
\put(180,20){$y$}
\put(-120,120){$g_{x_0,y}(v)\ne x_0$}
%\put(160,120){$y\in U$}


%-----------------------


\put(300,50){\circle{50}}
\put(290,40){\small $U$}
\put(315,50){\circle*{6}}
\put(315,90){\circle*{6}}
\put(315,50){\vector(1,0){105}}
\put(315,90){\vector(2,1){110}}
\put(430,50){\circle{50}}
\put(430,70){\circle{130}}
\put(425,40){\small $U$}
\put(396,85){\small $U\cup A$}
\end{picture}
\end{center}
  \vspace{-7.5pt}
\caption{function $p(y)$}
\end{figure}

\vspace{7cm}

The next theorem is a stronger version of Kobzev's result about
non-$btt$-completeness of $r$-separable sets.
However, in our case the non-$bT$-completeness cannot be proved
in the same way.
Kobzev's reasoning is based on the following fact: if an enumerable
set~$A$ can be $btt$-reduced to an $r$-separable set, then $A$
is $r$-separable.
Indeed, we will show that there exists an enumerable non-$r$-separable
set~$A$ which can be $bw$-reduced to an $r$-separable set.

\begin{thm}[S.~Positselsky]\label{t4}
No $r$-separable set is $bT$-complete.
\end{thm}

\begin{pf}
Let $B$ be an $r$-separable set and $U$ be an enumerable $m$-complete
set.  The proof is by reductio ad absurdum. Suppose $U\le_{bT} B$ and
$\gamma$ is an algorithm which $bT$-reduces $U$ to~$B$ and has
the minimal possible boundary on the number of questions to the oracle.
If this boundary is equal to zero, then the set $U$ is decidable.
If the boundary is equal to $n+1$, let us construct a {\em new\/}
algorithm. The new algorithm will reduce $U$ to~$B$
and for any input it will ask the oracle no more than $n$ questions.

For each program $\delta$ enumerating the set $D_\delta$ consider the set
$A_\delta$ of all the inputs~$y$ on which the algorithm $\gamma$ either
does not ask the oracle any questions, or the first question asked
belongs to $D_\delta$. It is clear that $A_\delta$ is enumerable
uniformly in $\delta$. Let $f_\delta$ be the function given by the
construction of Theorem~\ref{t3} applied to the sets $U$ and $A_\delta$.
Denote by $q(y)$ the first question that the algorithm $\gamma$ poses to
the oracle on the input~$y$.

Suppose the new algorithm has received an input $x$.
Consider the set $C$ of all elements of the form
$q(f_\delta(x))$, where $x$ is fixed and $\delta$~is changing
(notice that $q$ and $f_\delta$ are partial functions).
It is clear that $C$ is enumerable uniformly in~$x$.

Suppose that $B\cap C=\emptyset$; then for some $\varepsilon$ the set
$D_\varepsilon$ is decidable, $B$ is contained in $D_\varepsilon$, and
$C$ does not intersect $D_\varepsilon$ (due to $r$-separability of $B$).
The set $U\cup A_\varepsilon$ can be reduced to the set $B$ in a way
that requires no more than $n$ questions to the oracle on each input.
Indeed, if the algorithm $\gamma$ asks the oracle no questions on the
input~$y$, then $y\in A_\varepsilon$.  If $q(y)\in D_\varepsilon$,
then $y\in A_\varepsilon$.
If $q(y)\notin D_\varepsilon$, then $y\notin A_\varepsilon$.
The algorithm $\gamma$ finds out whether $y$ belongs to~$U$
without asking oracle the first question (it knows the answer:
$q(y)\notin D_\varepsilon$ $\Longrightarrow$ $q(y)\notin B$).
One can find out whether $q(y)$ belongs to $D_\varepsilon$,
because this set is decidable.

If the set $U\cup A_\varepsilon$ is $m$-complete, the new algorithm
$m$-reduces the set $U$ to the set $U\cup A_\varepsilon$ and then
$bT$-reduces the set $U\cup A_\varepsilon$ to the set $B$, as described.

If the set $U\cup A_\varepsilon$ is not $m$-complete, then by
Theorem~\ref{t3} the value $f_\varepsilon(x)$ is defined,
$f_\varepsilon(x)\in U\cup A_\varepsilon$, and
$x\in U$ $\Longleftrightarrow$ $f_\varepsilon(x)\in U$.
If $q(f_\varepsilon(x))$ is defined, then $q(f_\varepsilon(x))\in C$,
hence $q(f_\varepsilon(x))\notin D_\varepsilon$
and $f_\varepsilon(x)\notin A_\varepsilon$,
hence $f_\varepsilon(x)\in U$ and $x\in U$.

We see that there at least one of the next three conditions holds:
($B\cap C\ne\emptyset$), or ($f_\varepsilon(x)$ is defined, but
$q(f_\varepsilon(x))$ is not defined), or ($x\in U$). Let us return to
the construction of the new algorithm. Given an input $x$, it waits until
either of the following three events happens: a program $\delta$ is found
such that $q(f_\delta(x))\in B$; a program $\varepsilon$ is found such
that $f_\varepsilon(x)$ is defined, but $q(f_\varepsilon(x))$ is not; or
$x$~is caught in the enumeration of~$U$. In the first case, the new
algorithm emulates the work of the algorithm $\gamma$ on the input
$f_\delta(x)$ without asking the oracle the first question (since the
answer is known). In the second case, the new algorithm emulates the work
of the algorithm $\gamma$ on the input~$f_\varepsilon(x)$ without asking
oracle any questions. In the third case we actually know that $x\in U$.
Recall that if $f(x)$ is defined, then $x\in U$ $\Longleftrightarrow$
$f(x)\in U$.
\end{pf}

\begin{thm}[S.~Positselsky]\label{t4t1}
There exists a nonseparable pair of enumerable sets such that
each of the them is $bw$-reducible to a resilient set.
\end{thm}

\begin{pf}
Let $A$ be a nondecidable resilient set.
By the decomposition theorem (\cite{Fr},\cite{Mu2})
there exist enumerable sets $B_1, B_2,$ for which the following holds.
First, $A=B_1\cup B_2$; second, $B_1\cap B_2=\emptyset$;
third, $B_1$ and $B_2$ aren't separable by a decidable set.
An algorithm, $bw$-reducing $B_i$ to $A$, works as follows.
Given an input~$x$, if the oracle answers ``$x\notin A$'',
the output of the algorithm is ``$x\notin B_i$''.
If the oracle answers ``$x\in A$'', we enumerate the sets $B_1$
and $B_2$ until $x$ is caught in one of them.
In the latter case we use the assumption that the oracle's answer
is correct (hence it is not a $tt$-reducing algorithm).
\end{pf}

A.~Lachlan proved in~\cite{La2} that for an enumerable set~$B$
the properties of $bw$-completeness and $btt$-completeness
are equivalent.
Here we will prove a stronger result, replacing $bw$-completess
by $bT$-completeness and eliminating the enumerability
requirement.
Theorem~\ref{t4} can be deduced from Theorem~\ref{t4t2} and
the preservation property of $r$-separability with respect
to $btt$-reducibility, which was mentioned earlier.
Nevertheless, we gave an independent proof, which will
be useful in the second part of this paper.

\begin{thm}[An.~Muchnik]\label{t4t2}
If an enumerable $m$-complete set~$U$ is $bT$-reducible
to a set~$B$, then $U$ is also $btt$-reducible to~$B$.
\end{thm}

\begin{lem}
Let $U$ be an enumerable $m$-complete set,
$A_0\supset A_1\supset ...\supset A_k$ be enumerable sets,
and $\overline{A_0} =A_k =\emptyset$.
Then there exists a total computable function~$r$
and a number~$i$ such that $r(U)\subset U$ and
$r(\overline{U})\subset A_i\setminus (A_{i+1}\cup U)$.
\end{lem}

\begin{pfl}
For the identity function $q_0$ we have
$q_0 (U)\subset U$ and $q_0 (\overline{U})\subset A_0\setminus U$.
Let us argue by induction on~$i$.
Given a total computable function~$q_i$ for which
$q_i (U)\subset U$ and $q_i (\overline{U})\subset A_i\setminus U$,
we will construct either an analogous function $q_{i+1}$,
or a function~$r$ required in the Lemma.
Because no function $q_k$ exists for which
$q_k (\overline{U})\subset A_k\setminus U$,
at a certain step~$i$ a function~$r$ will be constructed.
Let $s$ be a computable injective function whose image is
the enumerable set $U\cup A_i$.
The preimage of $U$ under~$s$ is a computable $m$-complete set,
since the composition of functions $s^{-1}q_i =\lambda x.s^{-1}(q_i(x))$
$m$-reduces $U$ to the set $s^{-1}(U)$.
According to the proof of Theorem~\ref{t3},
for the enumerable set $s^{-1}(A_{i+1})$ there exists
either a total computable function $f$ for which
$f(s^{-1}(U))\subset s^{-1}(U)$ and
$f(\overline{s^{-1}(U)})\subset s^{-1}(A_{i+1})\setminus s^{-1}(U)$,
or a total computable function~$p$ for which
$p(s^{-1}(U))\subset s^{-1}(U)$ and
$p(\overline{s^{-1}(U)})\subset \overline{s^{-1}(A_{i+1})\cup s^{-1}(U)}$.
In the first case we can put $q_{i+1}=sfs^{-1}q_i$;
then $q_{i+1} (U)\subset U$ and
$q_{i+1} (\overline{U})\subset A_{i+1}\setminus U$.
In the second case we set $r=sps^{-1}q_i$.
\end{pfl}

\begin{pft}
Assume that $U$ is reduced to $B$ by a $bT$-algorithm $\gamma$
posing no more than $n$ questions to the oracle.
We will construct a $btt$-algorithm $\delta$, reducing $U$ to $B$
and asking the oracle less than $2^n$ questions.
In addition, the construction of $\delta$ will not depend on~$B$.

Let us assign to each input~$y$ of the algorithm~$\gamma$
a set $D(y)$ of binary charts $<d_1,d_2,...,d_j,u>$.
A chart belongs to the set $D(y)$ if the algorithm $\gamma$ gives
the output $u$ on the input $y$, provided that it receives
$d_1,...,d_j$ as the oracle's answers to the algorithm's
questions (no matter whether the oracle's answers correspond
to the set~$B$).
It is clear that $|D(y)|<2^n$ for each~$y$.
For each $0\le i\le 2^n$ we set $A_i=\{y\bigm| |D(y)|\ge i\}$.
It is obvious that sets $A_i$ satisfy the conditions of the Lemma.
Let $r$ be a total computable function for which $r(U)\subset U$
and $r(\overline{U})\subset A_i\setminus (A_{i+1}\cup U)$.

Given an input $z$, the algorithm $\delta$ enumerates
the sets~$U$ and $D(r(z))$ simultaneously.
We know that $z\in U$ or $|D(r(z))|=i$.
If $z$ is caught $U$, then the output of~$\delta$ is known.
Suppose that $i$~elements have been caught in the enumeration
of~$D(r(z))$ (denote the set of those elements by~$E$).
The algorithm $\delta$ asks the oracle at once all the questions
which would be posed by the algorithm~$\gamma$ on the input~$r(z)$,
assuming that the latter algorithm receives the answers from~$E$.
If the oracle's answers turn out to be compatible with one of
the charts from~$E$, then the output of~$\delta$ is equal to
the output of~$\gamma$ mentioned in this chart (there can be
no more than one such chart).
If the oracle's answers turn out incompatible with any chart from~$E$,
then the output of~$\delta$ is ``$z\in U$''.
In the first case the algorithm $\delta$ is correct, because
the algorithm $\gamma$ is.
In the second case, if the oracle's answers correspond to the set~$B$
and the algorithm~$\gamma$ is correct, then a chart which does not
belong to~$E$ will eventually appear in $D(r(z))$.
The latter is incompatible with ``$z\notin U$''.
\end{pft}

The next result is symmetric to the previous one.

\begin{thm}[An.~Muchnik]\label{t4t3}
If a set $B$ is $bT$-reducible to an enumerable $m$-complete set~$U$,
then $B$~is also $btt$-reducible to~$U$.
\end{thm}

\begin{pf}
Assume that $B$ is reduced to~$U$ by a $bT$-algorithm $\gamma$
posing no more than $n$ questions to the oracle.
We will construct a $btt$-algorithm $\delta$, reducing $B$ to~$U$
and asking the oracle less than $2^{n+2}$ questions.
First let us modify the algorithm~$\gamma$ so that
it would satisfy the following {\it requirement}.
If the oracle answered ``yes'' to the question ``$x\in U$?'',
the enumeration of $U$ is started; after $x$~is caught in~$U$,
the usual work of~$\gamma$ resumes.
That is, if the true answer to the question is ``no'', then
the modified algorithm will never stop.
Obviously, the modified algorighm~$\gamma$ still $bT$-reduces
$B$ to~$U$.

Now let us use the sets $D(y)$ defined in the proof of the
previous theorem.
Since the set $\{(y,z)|z\in D(y)\}$ is enumerable,
it is $m$-reducible to~$U$ (say, by a function~$f$).
Given an input~$y$, the algorithm~$\delta$ asks the oracle
about all the elements~$f(y,z)$, where $z$ is a binary chart
of length no more than $n+1$.
If the oracle answers correctly, we will know the set~$D(y)$.

Due to the requirement imposed on the algorithm~$\gamma$,
the set of true oracle's answers to the questions of~$\gamma$
and the output of~$\gamma$ on the input~$y$ can be found as follows.
Let us define by induction a sequence of sets
$D_0\supset D_1\supset D_2...$~. Put $D_0=D(y)$.
In all the charts from the set $D_j$ the first $j$ digits
will correspond to the true oracle's answers to the first~$j$
questions of~$\gamma$ on the input~$y$.
If $D_j$ contains a chart of length $j+1$, than this chart is true.
Otherwise, let us define $D_{j+1}$.
If $D_j$ contains some charts in which the ($j+1$)-th digit means
``yes'', then $D_{j+1}$ consists of all such charts.
Otherwise $D_{j+1}=D_j$.

This construction gives some output even when the oracle answers
the questions of~$\delta$ incorrectly.
\end{pf}

The following answer to a question of G.~Kobzev is a corollary
of Theorems \ref{t4t2} and~\ref{t4t3}.

\begin{cor}
The complete $bT$-degree contains exactly one $btt$-degree.
\end{cor}

\begin{thm}[S.~Positselsky]\label{t5}
Any resilient set is either decidable, or $T$-complete.
\end{thm}
\nopagebreak

This theorem will follow from Theorem~\ref{t6}, which was proven
in~\cite{BM}.

\begin{df}[M.~Blum, I.~Marques]\label{d16}
An enumerable set $A$ is called subcreative if there exists an
algorithm $\gamma$ with the following properties. If $B$ is an enumerable
set not intersecting~$A$, the algorithm $\gamma$ is defined on the text
of any program $\beta$ enumerating~$B$. The result $\gamma(\beta)$ is
the text of a program enumerating a set $C$ such that $A\ssne C$ and
$B\cap C=\emptyset$.
\end{df}

Obviously, if a nondecidable set is resilient, then it is subcreative.

\begin{thm}[M.~Blum, I.~Marques]\label{t6}
Any subcreative set is $T$-com\-plete.
\end{thm}

\begin{pf}
Let $A$ be a subcreative set; suppose that an algorithm $\gamma$
ensures this property of~$A$.
Let $U$ be an enumerable set.
Given $x$, we have to find out whether $x\in U$.

Using the fixed point theorem, we will construct an auxiliary enumerable
set~$B_x$, containing no more than one element. Let us run an enumeration
of $U$. If $x\notin U$, then $B_x=\emptyset$. If~$x$ was enumerated in
$U$ exactly at the $s$-th step, we run the first $s$ steps of the
enumeration of~$A$. (Let us denote by~$E^s$ the set of all elements
of~$E$ enumerated during first~$s$ steps.) Let a program $\beta$
enumerate the set $B_x$ and the program~$\gamma(\beta)$ enumerate a
set~$C$ (if $\gamma(\beta)$ is not defined, let $C$ be empty). Then the
set~$B_x$ contains the first%
\footnote {in the enumeration of the set $C$}
element not belonging to $A^s$ that is
caught in the enumeration of~$C$ (if there is no such element, then $B$
is empty). The construction of $B_x$ is finished.

The algorithm that $T$-reduces $U$ to~$A$ works as follows.
Let us enumerate the set $U$ and run the following procedure
in parallel.

We do an enumeration of~$C$. Using the oracle for~$A$, we look for
the first%
\footnote {in the enumeration of the set $C$}
~$y$ which is caught in~$C$ and does not belong to~$A$.
We find a~$t$ for which all the elements caught in~$C$ before~$y$
belong to~$A^t$. If $x$~does not belong to $U^t$, the answer is
$x\notin U$. The description of the procedure running in parallel
to the enumeration of~$U$ is finished.

We have to show that $x\notin U$ if and only if the parallel procedure
gives an answer.

If $x\notin U$, then $B_x=\emptyset$.
In this case by the definition of $\gamma$ we have $A\ssne C$.
It follows that the parallel procedure will find an element~$y$ and
$x$ does not belong to~$U^t$.

Suppose that the parallel procedure gave an answer, but $x\in U$.
Assume that $x\in U^s$.  Let $y$ be the element found by the parallel
procedure.  Than $B_x$ contains some element~$z$.  Moreover,
$z$~was caught in~$C$ no later than~$y$.
Let us consider two cases: $z=y$ and $z\ne y$.

If $z=y$, then $B_x\cap A=\emptyset$. It would follow that
$B_x\cap C=\emptyset$, but this is not so.

Suppose $z\ne y$. Since $z\notin A^s$, we have $s < t$
(by the constructions of~$B_x$ and of the parallel procedure).
Since $x\notin U^t$, we have $t<s$.
This contradiction completes the proof.
\end{pf}


\part{}

\begin{thm}[An.~Muchnik]\label{t21}
The overgraph of any conditional entropy function is an $m$-complete set.
\end{thm}

\begin{pf}
We will use an idea from the proof of M. Kummer's theorem on the
unconditional simple entropy.

Let $U$ be an enumerable set. We would like to construct an algorithm
$m$-reducing $U$ to the set $M=\{(x,y,n)\ |\ K(x|y)<n\}$, where $K(x|y)$
denotes the entropy of~$x$ conditional to~$y$. We will need the following
auxiliary construction. It depends on a natural number~$d$ considered as
a free parameter.

To any condition $y$ we assign a {\em scale}. Any scale has a
{\em pointer\/} and $2^d$ {\em points}, numbered by the integers
between~$1$ and~$2^d$. During the time when the construction is
performed, the number of the point under the pointer will never decrease.
Some points will be {\em marked\/} with a pair of natural numbers each,
where the first component of the pair coincides with the number of the
point. No point is marked more than once, and no pair of numbers marks
more than one point. Some pointers will be {\em tied\/} to their positions
at certain moments of time and do not move thereafter.

Let us fix certain enumerations of the sets $U$ and~$M$. Denote by $U^t$
and $M^t$ the subsets, enumerated in the first $t$ steps. The construction
consists of a sequence of finite stages. On the first stage all the pointers
are on the lowest points of their scales (numbered by~$1$) and no point
is marked. Let us describe the stage number~$t$.

For each $v\in U^t$ all the pointers placed over the points marked by
pairs of the form $(w,v)$ are tied to those points. Let us process one
after one the first $t$ scales whose pointers aren't tied. Consider the
scale assigned to the condition~$y$. We move its pointer to the minimal
point $x$ for which $(x,y,d)\notin M^t$. Such an $x$ does exist, because
$\forall y,n\ \big|\{x\ |\ (x,y,n)\in M\}\big| < 2^n$.
If the new position of the pointer differs from the previous one, let us
take the minimal~$z$ for which the pair $(x,z)$ was not used as a mark
yet. We mark the $x$-th point on the $y$-th scale by the pair $(x,z)$.
This completes the description of the auxiliary construction.

Assume that the parameter $d$ is large enough.  Let us prove that
$$
\parbox{0.68\textwidth}
{
   if the pointer of the $y$-th scale is tied \newline
   to the point
 number~$x$, then $(x,y,d)\in M$.
}
\eqno(\alpha)
$$
%%$\begin{itemize}
%%\item[$(\alpha)$]
%%\end{itemize}

Indeed, given $y$ and $d$, we start the construction with the
parameter~$d$ and wait until the pointer of the $y$-th scale is tied;
$x$ is the number of the point under this pointer. Then we have
$K(x|\langle y,d\rangle)<c$, where $c$~is a constant. Therefore,
$K(x|y) < c'\cdot\log d < d$ (where $c'$ is a constant and $d$
is large enough).

Now let us fix a sufficiently large value for~$d$.  Let $b$ be the maximal
point number which is reached by infinitely many pointers in the process
of the auxiliary construction.  The algorithm, $m$-reducing $U$ to $M$,
works as follows.

Given an input $z$, let us find the condition $y_z$ for which the $b$-th
point of the scale assigned to~$y_z$ is marked by $(b,z)$. Such a
condition exists due to our choice of~$b$. We claim that $z\in U$ if
and only if $(b,y_z,d)\in M$ for all~$z$ except a finite set of the
elements~$z$ for which the pointer of the scale assigned to~$y_z$ stops
above~$b$. The proof immediately follows from the description of the
auxiliary construction, from $(\alpha)$, and the choice of~$b$.
\end{pf}

Note that the one-dimensional section $\{y\,|\,(b,y,d)\in M\}$ of
the three-dimensional set $M$ is already $m$-complete.

>>From now on, we will consider the unconditional entropy only.

\begin{thm}[S.~Positselsky]\label{t22}
The overgraph of any entropy function is a resilient set.
\end{thm}

\begin{pf}
Put $M=\{(x,n)\,|\,K(x)<n\}$ and let $B$ be an enumerable set not
intersecting $M$. We claim that the second component of the pairs
from~$B$ is bounded, and the boundary can be effectively found
starting from a program enumerating~$B$.

Given $n$, consider the first pair of the form~$(x,n)$ caught in the
enumeration of~$B$. If such a pair exists, then $K(x) < C\cdot\log n$,
where the factor $C$ effectively depends on a program enumerating $B$.
For large~$n$ we have $C\cdot\log n<n$ and therefore $K(x)<n$. The latter
means that $(x,n)$ belongs to $M$, which contradicts our assumption that
$M$ and $B$ do not intersect.

Let $d$ be the boundary found in the previous paragraph. Then it is easy
to write a program enumerating the set $D = M\cup\{(x,n)\,|\,n>d\}$. We
know that $M$ is contained in $D$ and $B\cap D$ is empty. It remains to
prove that $D$ is decidable. Indeed,
$D = (M\cap\{(x,n)\,|\,n\le d\})\,\cup\,\{(x,n)\,|\,n>d\}.$
The second term of this union is obviously decidable. The first term is
finite for the simple and the prefix entropy. For the cases of the
decision entropy, the a priori entropy, and the monotone entropy it
suffices to show that for any $n$ the set $E=\{x\,|\,K(x)<n\}$ is
decidable. The mentioned three entropies are defined on binary words.
It follows easily from their definitions that the set $E$ contains all
initial subwords of any of its words. Besides, any subset of the set~$E$
such that none of its elements are initial subwords of one another
contains no more than $2^n$ elements. Hence there are no more than~$2^n$
infinite strings having the property that all of their initial subwords
belong to~$E$. Let us denote those strings by $y_1$,~\dots, $y_i$~\dots,
and the set of all their initial subwords by~$F$. For any word
$z\in E\setminus F$, let us define an initial subword called the
{\em trunk\/} of~$z$. It is the shortest initial subword of~$z$ which
does not belong to~$F$. It is clear that all the trunks belong to $E$ and
they are not one another's initial subwords. Thus there are no more than
$2^n$ trunks. All the words with the same trunk form a locked tree, which
is therefore finite. Hence the set $E\setminus F$ is finite. Each $y_i$
is computable, since $E$ is enumerable and for any long enough~$w$ which
is an initial subword of~$y_i$, exactly one of the two words $w0$
and~$w1$ belongs to~$E$.
\end{pf}

\begin{thm}[An.~Muchnik]\label{t23}
The overgraph of any entropy function is not $bT$-complete.
\end{thm}

\begin{pf}
This follows from Theorems~\ref{t4} and~\ref{t22}.
\end{pf}

An argument analogous to the proof of Theorem~\ref{t4} shows that
the universal enumerable set is not $bT$-reducible to the overgraphs
of the entropy functions, relativized by any oracle.

\medskip

The idea of the next proof was invented nearly before the notion of
the entropy itself.  Since similar arguments were suggested by many
people independently, we do not indicate who the author is.

\begin{thm}\label{t24}
The overgraph of any entropy function is $w$-complete.
\end{thm}

\begin{pf}
We would like to construct an algorithm $w$-reducing an enumerable
set~$U$ to the set $M=\{(x,n)\,|\,K(x)<n\}$. Let us fix some enumerations
of $U$ and~$M$. The algorithm has to find out whether $y\in U$. Let
$d$~be the length of the binary representation of~$y$.

Using the oracle, we find the values of $K$ on all the binary words of
length~$d^2$. Since these values are bounded by $\mbox{const}\cdot d^2$,
all the questions to the oracle can be posed simultaneously. For each
word $z$ of length $d^2$ such that $K(z)<d^2$, let us find the number of
steps $t(z)$ in which the pair $(z,d^2)$ will be caught in the
enumeration of~$M$. Here we presume that the oracle gave the correct
answers; otherwise our algorithm may never stop! Let us denote by~$s$ the
maximal value of~$t(z)$ on the words~$z$ of length~$d^2$ on which $t$ is
defined. We claim that if $d$ is large enough, then $y$ is caught in the
first $s$ steps of the enumeration of $U$ whenever $y$ belongs to $U$.
Indeed, assume the contrary. We have $y\in U$. Let $r$ denote the number
of steps in which $y$ gets caught in $U$. Then we have $s<r$.  Consider
the set $V$ of all the words~$z$ of length~$d^2$ for which the pair
$(z,d^2)$ gets caught in the enumeration of $M$ in the first $r$ steps.
Since $|V|<2^{d^2}$, there is a word of length $d^2$ which does not
belong to $V$. If $w$ is the first such word, then it is sufficient to
know $y$ in order to find $w$. Hence we have
$K(w)<K(y)+\mbox{const}<\mbox{const}\cdot d$. The rightmost term of the
inequality is smaller than $d^2$ for large $d$. That is a contradiction.

It remains to ``repair'' the constructed algorithm on a finite number of
inputs of small lengths to make it correct.
\end{pf}

\begin{thm}[M.~Kummer]\label{t25}
The overgraph of any simple entropy function is $tt$-complete.
\end{thm}

\begin{pf}
The argument is parallel to our proof of Theorem~\ref{t21}.

Let $U$ be an enumerable set.  We would like to construct an algorithm
$tt$-reducing $U$ to the set $M=\{(x,n)\,|\,KS(x)<n\}$, where $KS$ is the
simple entropy. Let us describe an auxiliary construction with a
parameter~$d$.

This construction differs from the one introduced for the proof
of~\ref{t21} in the following. In the previous construction, the scales
were assigned to conditions; now they are numbered by positive integers
expressing the lengths of binary representations%
\footnote{This distinction is, of course, informal.}.
On the stage number~$t$ the pointer of $y$-th scale is moved to the
point~$x$, which is defined below (if this pointer is not tied yet).
We take the minimal~$x$ for which there is $p\le x\cdot2^{y-d}$ such
that $(p,y)\notin M^t$. Such a value of~$x$ exists, because
$
\big|\{p\ |\ (p,y)\in M\}\big|<2^y=2^d\cdot2^{y-d}.
$

The claim $(\alpha)$ from the proof of~\ref{t21} is modified as follows:
$$
\parbox{0.68\textwidth}
{
     if the pointer of $y$-th scale is tied to the point~$x$,
     then the entropy of any number from the semi-interval
     $\big((x-1)\cdot2^{y-d},x\cdot2^{y-d}\big]$ is smaller
     than $y-d/2$.
}
\eqno(\alpha)
$$
%%\begin{itemize}
%%\item[$(\alpha)$]
%%\end{itemize}

Let us prove that $(\alpha)$ is true for $d$ large enough.
We want to construct a number $q$ from the semi-interval
$\big((x-1)\cdot2^{y-d},x\cdot2^{y-d}\big]$. In order to do that, it
suffices to know the value of~$d$ and the binary representation of the
number $(x\cdot2^{y-d}-q)$, completed by zeroes to the left so that there
be exactly $(y-d)$ bits. Let us denote this binary word by~$v$. Further,
let $\partial(v)$ denote the length of~$v$ and $\hat v$ be the number
represented by $v$. We can recover $y$ as $d+\partial(v)$. Let us start
the auxiliary construction with the parameter~$d$ and wait until the
pointer of $y$-th scale is tied to some point. If $x$~is the number of
this point, then $q=x\cdot2^{y-d}-\hat v$. Now let us estimate the
entropy of~$q$:
$$
KS(q)<KS(\langle d,v\rangle)+\mbox{const}<\!
\footnote{It is for this inequality that we need the entropy to be
\em{simple}.}
\mbox{ const}\cdot\mbox{log}d+\partial(v)=
\mbox{const}\cdot\mbox{log}d+y-d < y-d/2.
$$

The reducing algorithm chooses $b$ and given an input $z$ finds $y_z$
exactly as in Theorem~\ref{t21}. We claim that for all $z$ but a finite
set of exceptions the following implications hold:
$$
\renewcommand{\arraystretch}{1.5}
\begin{array}{l}
z\in U\ \Longrightarrow\ \forall p\in\big((b-1)\cdot2^{y-d},b\cdot2^{y-
d}\big]
\quad KS(p)<y-d/2; \\
z\notin U\ \Longrightarrow\ \exists p\in\big((b-1)\cdot2^{y-d},
b\cdot2^{y-d}\big] \quad KS(p)\ge y.
\end{array}
$$

As in Theorem~\ref{t21}, these implications follow straightforwardly
from
the description of the auxiliary construction, the statement~$(\alpha)$,
and the choice of~$b$.

Note that these implications allow to answer the question ``Does $z$
belong to~$U$?'' even when the oracle's answers are incorrect. Of course,
if the oracle answers incorrectly, then the reducing algorithm can answer
incorrectly, too.
\end{pf}

Unlike in the previous theorem, in the following theorem we deal with
one specific entropy function.  On the other hand, our considerations
do not depend on the entropy type (it is correct for the simple entropy
as well as for the prefix, monotone, decision, or apriopy entropy).

\begin{thm}[An.~Muchnik]\label{t26}
There exists an entropy function with a $tt$-complete overgraph.
\end{thm}

\begin{pf}
Let $U$ be an enumerable set and $K$ be any entropy function. Let us
modify the function~$K$ to get another entropy function~$K'$.
%%If the word $x$ doesn't have the form $0^x1$, then $K'(x)=K(x)$.
If $z=0^x1v$ and $x\notin U$, then $K'(z)$ equals the number
$K(z)+2$ if the latter is even, and $K(z)+3$ otherwise.
If $z=0^y$ or $z=0^x1v$ and $x\in U$, then $K'(z)$ is equal to
the number $K(z)+1$ if it is odd, and $K(z)+2$ otherwise.
It is easy to check that $K'$~is an entropy function (of the same
type as the function~$K$).

Let us construct an algorithm $tt$-reducing the set~$U$ to
the overgraph of~$K'$. We fix large enough $c$ and
for each $p<c\cdot x$ ask the oracle whether the pair $(0^x1,p)$
belongs to this overgraph.
The output of our reducing algorithm on the input~$x$ is defined
by the condition that $x\in U$ if and only if $K'(0^x1)$ is odd.

Note that the algorighm terminates even for incorrect answers of
the oracle.
\end{pf}

\begin{thm}[An.~Muchnik]\label{t27}
There exists a prefix entropy function with a non-$tt$-complete
overgraph.
\end{thm}

\begin{pf}
Let $KP$ be any prefix entropy function.
Let us call a function $f$ above-enumerable if it has
an enumerable overgraph. We will construct an enumerable
set~$U$ and an above-enumerable function~$F$ for which the function
$H=\min(KP+2,F)$ will be a prefix entropy function. In addition,
the set $U$ will not be $tt$-reducible to the overgraph of~$H$.
Denote by $KP^s$ and $F^s$ the upper boundaries for $KP$ and $F$
which one can obtain from the first $s$ steps of the above-enumerations
of $KP$ and~$F$.
We assume that $KP^1$ and $F^1$ have finite values and
$\sumlim_x 2^{-F^1(x)}\le 1/4$.
The set~$U$ will be constructed as a subset of the universe of all
triples of natural numbers.  Let $\{\gamma_n\}$ be an enumeration of
all $tt$-reducing partially defined algorithms. Using inputs of the form
$(n,i,j)$, we will make sure that the algorithm~$\gamma_n$ doesn't
reduce $U$ to the overgraph of~$H$. The numbers~$n$ will be processed
in the following order: $1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,\dots$~.

To each number~$n$ whose processing have already started we assign
two natural numbers $i_n$, $j_n$ and a finite game~$G_n$.
When we return to the number~$n$ for the next time, we can either
let one of the partners make his next move in the game
$G_n$, or change the numbers $i_n$, $j_n$ and the game $G_n$.
A position in the game $G_n$ is a finite set~$A_n$ (which is fixed for
this game) and a function $h_n:A_n\to\BbbN$ (it changes with any move).
Moves of the first player will decrease the estimate~$F^s$.  Moves of the
second player will be determined by the decrease of the estimate~$KP^s$.
When we are processing the number~$n$ for the first time, we set $i_n=1$
and $j_n=1$. When we return to the number~$n$ again, we increase the
value of~$i_n$ by~$1$ if the following holds: there exists a
number~$m$ smaller than~$n$ such that a move was made in the game~$G_m$
(or the game~$G_m$ was changed) when we were dealing with~$m$ for the
last time. If a move of the second player violates the rules of the
game~$G_n$, we increase the value of~$j_n$ by~$1$.

Assume that we are processing the number~$n$ for the $s$-th time. Define
the values of $i_n$ and $j_n$. Run $s$ steps of the algorithm~$\gamma_n$
on the input $(n,i_n,j_n)$. If the algorithm did not produce a table%
%%
\footnote{which shows questions to the oracle and the outputs of the
algorithm depending on the oracle's answers}
%%
in the output, we set $G_n=A_n=\emptyset$. If the algorithm
produced a table, then the game $G_n$ is defined as follows.
The questions to oracle are of the form ``is $H(x)$ smaller than $r$?'',
that is, a question is related to a pair $(x,r)$. Let $B_n$ be the set of
all the first coordinates of the questions to the oracle from the table;
then we put $A_n=B_n\setminus\bigcuplim_{m<n}A_m$. We define
$h_n=\min(KP^s+2,F^s)$.
If since we dealt with~$n$ for the last time one of the values of $h_n$
decreased due to a decrease in $KP^s$, then we decide that a move was
made by the second player, while if it was due to a decrease in $F^s$, we
conclude that the first player made a move (it is assumed that $KP^s$ and
$F^s$ decrease in turn).
Each player is prohibited from making the sum of the changes in the value
of $\left(\sumlim_x 2^{-h_n(x)}\right)$ attributed to his moves in one game
exceed $2^{-n-i_n-2}$.
To each function from $B_n$ to $\BbbN$ the table assigns the answer
of the algorithm $\gamma_n$ to the question whether the triple
$(n,i_n,j_n)$ belongs to~$U$.
This answer determines the result of the game $G_n$.
For one of the two answers the player who wants this answer has a winning
strategy (this is a property of all finite games).
In any case the first player (enumerating from above the function~$F$) sets
himself the goal of obtaining this particular answer.
In addition, if the answer is negative, we put the element $(n,i_n,j_n)$
into the set~$U$.
Hence if the games with numbers different from~$n$ will not ``interfere''
and the second player will not violate the prohibition to change the value
of $\left(\sumlim_x 2^{-h_n(x)}\right)$ too much, the algorithm $\gamma_n$
will make an error on the input $(n,i_n,j_n)$ (if one considers this
algorithm as attempting to reduce $U$ to the overgraph of~$H$).
The games with numbers greater than~$n$ cannot interfere, since $A_m$
does not intersect $B_n$ for $m>n$.
Let us prove by induction on~$n$ (as usually in the priority method) that
the values of $i_n$, $j_n$, and $G_n$ change a finite number of times.
By the induction hypothesis, starting from some moment all the games with
numbers smaller than~$n$ do not change.
Since the games are finite, after some moment no more moves in them are
made.  Therefore the value of $i_n$ stabilizes.
After that, any change of~$j_n$ is the consequence of an increase of
the value of $\left(\sumlim_x 2^{-KP^s(x)-2}\right)$ by at least
$2^{-n-i_n-2}$ (which is now fixed).
Since $\left(\sumlim_x 2^{-KP^s(x)}\right)\le 1$, the value of~$j_n$
stabilizes.
When $i_n$ and $j_n$ are fixed, the table produced by the algorithm
$\gamma_n$ on the input $(n,i_n,j_n)$ is uniquely determined if it exists.
Therefore, $G_n$ stabilizes too.
It remains to prove that the function $H=\mathop{\mbox{min}}(KP+2,F)$
is a prefix entropy.
For this one has to prove that $H\le KP+\mbox{const}$, function~$H$ is
above-enumerable, and $\sumlim_x 2^{-H(x)}\le 1$.
The first follows straightforwardly from the definition of~$H$.
The function~$H$ is above-enumerable because $KP$ and $F$ are.
Finally, let us prove that $\sumlim_x 2^{-H(x)}\le 1$.
Indeed, $\sumlim_x 2^{-H(x)}\le
\sumlim_x 2^{-KP(x)-2} + \sumlim_x 2^{-F(x)} \le
1/4 + \sumlim_x 2^{-F(x)}$.
We will use the identity $\sumlim_x 2^{-F(x)} =
\sumlim_x 2^{-F^1(x)} + \sumlim_s\left(\sumlim_x 2^{-F^{s+1}(x)} -
\sumlim_x 2^{-F^s(x)}\right)$.
The values of $F^1$ were put such that $\sumlim_x 2^{-F^1(x)}\le 1/4$.
Each nonzero difference
$\left(\sumlim_x 2^{-F^{s+1}(x)} - \sumlim_x 2^{-F^s(x)}\right)$
corresponds to a move of the first player in one of the games.
For any $n$ and $i$ there may be several games in which
the second player violated the game prohibition, and no more
than one game where the prohibition wasn't broken.
The sum $\left(\sumlim_x 2^{-F^{s+1}(x)} - \sumlim_x 2^{-F^s(x)}\right)$
over all $s$ corresponding to the games with the prohibition
unbroken does not exceed $\sumlim_{n,i} 2^{-n-i-2}=1/4$.
The sum $\left(\sumlim_x 2^{-F^{s+1}(x)} - \sumlim_x 2^{-F^s(x)}\right)$
over all $s$ corresponding to the games with the prohibition violated
is not greater than the sum over the same $s$ of the differences
$\left(\sumlim_x 2^{-KP^{s+1}(x)-2} - \sumlim_x 2^{-KP^s(x)-2}\right)$.
This follows from the condition that the first player obeys
the prohibition in all the games.
Since $\sumlim_s\left(
\sumlim_x 2^{-KP^{s+1}(x)-2} - \sumlim_x 2^{-KP^s(x)-2}\right) <
\sumlim_x 2^{-KP(x)-2} \le 1/4$,
we obtain $\sumlim_x 2^{-H(x)} \le 1$.
\end{pf}

In conclusion let us prove a ``quantitative'' theorem.

\begin{thm}[An.~Muchnik]\label{t28}
For any $\delta$ there exist $x$ and $v$ such that
$$
\renewcommand{\arraystretch}{1.5}
\begin{array}{c}
KS(x) + \delta < KS(v) \\
\mbox{and}\\
KP(v) + \delta < KP(x).
\end{array}
$$
\end{thm}

\begin{pf}
Suppose that there is a $\delta$ such that for all $x$ and $v$
$
KS(x) + \delta < KS(v)\ \Longrightarrow\ KP(x) < KP(v) + \delta.
$
Then the algorithm from Theorem~\ref{t25}, which
$tt$-reduces the enumerable set~$U$ to the overgraph of~$KS$,
can be modified to obtain an algorithm $\gamma$ which
$tt$-reduces the set~$U$ to the overgraph of~$KP$.
This contradicts Theorem~\ref{t27}.

Recall that the algorithm from Theorem~\ref{t25} takes an input~$z$ and
constructs a natural number $y$ and a set $A$ of binary words of
length~$y$ such that
$$
\renewcommand{\arraystretch}{1.5}
\begin{array}{l}
z\in U    \quad\Longrightarrow\quad \forall p\in A\quad KS(p) <   y - 4d,\\
z\notin U \quad\Longrightarrow\quad \exists p\in A\quad KS(p) \ge y.
\end{array}
$$
The number $d$ here is fixed in advance and may be as large as
one wishes.

The new algorithm $\gamma$ works as follows.
If for all $p\in A$ there exists a binary word~$q$ of length $y-2d$
such that $KP(p)<KP(q)$, then $\gamma$ decides that $z\in U$.
Otherwise $\gamma$ decides that~$z\notin U$.

To prove that the algorithm $\gamma$ is well defined we need two
well-known facts.

\begin{description}  \it
\item[Fact 1]
$\exists c$ $\forall n$ for any word $w$ of length $n$ it is true that
$$
KP(w) < n + KP(n) + c.
$$

\item[Fact 2]
$\exists c$ $\forall n$ there exists a word $w$ of length $n$ such that
$$
KP(w) > n + KP(n) - c.
$$
\end{description}

To prove Fact~1 note that the function
$f=\lambda w.(\partial(w) + KP(\partial(w)))$ is above-enumerable
and $\sumlim_w 2^{-f(w)}\le 1$ (where $\partial(w)$ denotes
the length of~$w$).

To prove Fact~2 consider the function
$g = \lambda n.\sumlim_{\partial(w)=n}\!\! 2^{-KP(w)}$.
Since $g$ is enumerable from below and $\sumlim_n g(n)\le 1$
we have $\forall n$ $g(n)<\mbox{const}\cdot 2^{-KP(n)}$.
In the sum $\sumlim_{\partial(w)=n}2^{-KP(w)}$ at least
one of the summands must be less than
$2^{-n}\cdot\mbox{const}\cdot 2^{-KP(n)}$,
since there are $2^n$ summunds.
Passing to the logarithms, we obtain Fact~2.

Let us return to our algorithm $\gamma$.

If $\forall p\in A$ $KS(p)<y-4d$
then for any random word $r$ of length $y-3d$ we have $\forall p\in A$
$KS(p)+\delta < KS(r)$. Indeed, $KS(r)\ge\partial(r)$, and
one may assume that $d>\delta$. From the initial hypothesis we obtain
$\forall p\in A$ $KP(p)<KP(r)+\delta$.
Using Fact 2 we find a word $q$ of length $y-2d$ such that
$KP(q) > y-2d + KP(y-2d)-c$.
>>From Fact 1 we get $KP(r)<y-3d+KP(y-3d)+c$.
Finally, we obtain
$\forall p\in A$ $KP(p)<KP(q)-d+KP(y-3d)-KP(y-2d)+\delta+2c$.
As we know, $\exists c$ $\forall i,j$ $KP(i)<KP(j)+KP(i|j)+c$.
Therefore $KP(y-3d)-KP(y-2d)<KP(y-3d|y-2d)+c$.
To find $y-3d$ knowing $y-2d$, it suffices to have~$d$.
Thus, $\forall p\in A$
$KP(p)<KP(q)-d+\mbox{const}\cdot\log d$.
For large $d$ we get $\forall p\in A$ $KP(p)<KP(q)$.

If for some $p\in A$ we have $KS(p)\ge y$, then consider a word $s$
of length $y-d$ such that $KP(s)>y-d+KP(y-d)-c$ (here we use Fact~2).
Since $KS(s)<\partial(s)+\mbox{const}$, for large $d$ we have
$KS(s)+\delta < KS(p)$. By the initial hypothesis,
$KP(p) > KP(s)-\delta$. According to Fact~1, for any word $q$ of length
$y-2d$ we have $KP(q)<y-2d+KP(y-2d)+c$. Combining all these
inequalities, for any word $q$ of length $y-2d$ we get
$KP(p)>KP(q)+d-KP(y-2d)+KP(y-d)-\delta-2c$.
Applying the conditional entropy $KP(y-2d|y-d)$,
we obtain $\exists p\in A$ $\forall q$ ($\partial(q)=y-2d$
$\Longrightarrow$ $KP(p)>KP(q)$) if $d$ is large enough.

This proves that the algorithm $\gamma$ is well defined.
\end{pf}

The question of $tt$-completeness was studied for the simple
and the prefix entropies.  One can prove an analogue of Theorem~\ref{t25}
for the decision entropy.  An analogue of Theorem~\ref{t27} can be
verified for the a priori entropy.

\begin{prob}
Is there a monotone entropy function whose overgraph is
not $tt$-complete?
\end{prob}


\begin{thebibliography}{99}

\bibitem{BM}
 {\it M.~Blum, I.~Marques.}
  On complexity properties of recursively enumerable sets.
{\it Journal of Symbolic Logic\/} {\bf38}, p.~579--593, 1973.

\bibitem{Fr}
 {\it R.~M.~Friedberg.}
  Three theorems on recursive enumeration.
{\it Journal of Symbolic Logic\/} {\bf23}, no.~3, p.~309--316, 1958.

\bibitem{Kob}
 {\it G.~N.~Kobzev.}
  On $r$-separable sets.  (Russian.)
{\it Issledovanija po matematicheskoj logike i teorii algoritmov},
p.~19--30, University of Tbilisi, 1975.

%\bibitem{Ko2}
% {\it G.~N.~Kobzev.}
%  On recursively enumerable $bw$-degrees.
%{\it Matematicheskije Zametki\/} {\bf21}, no.~6, p.~839--846, 1977.

%(Translation available in {\it Mathematical Notes}.)

\bibitem{Kum}
 {\it M.~Kummer.}
  On the complexity of random strings.
13th Symposium on Theoretical Aspects of Computer Science, 1996;
{\it Lecture Notes in Computer Science\/} {\bf1046}, p.~25--36.

\bibitem{KS}
 {\it M.~Kummer, F.~Stephan.}
  Recursion theoretic properties of frequency computation
  and bounded queries.
{\it Information and Computation\/} {\bf120}, no.~1, p.~59--77, 1995.

\bibitem{Lah}
 {\it A.~H.~Lachlan.}
  A note on universal sets.
{\it Journal of Symbolic Logic\/} {\bf31}, no.~4, p.~573--574, 1966.

\bibitem{La2}
 {\it A.~H.~Lachlan.}
  wtt-Complete sets are not necessarily tt-complete.
{\it Proceedings of the American Mathematical Society\/}
{\bf48}, no.~2, p.~429--434, 1975.

\bibitem{Much}
 {\it Al.~A.~Muchnik.}
  On separability of recursively enumerable sets.  (Russian.)
{\it Doklady Akademii Nauk SSSR\/} {\bf109}, no.~1, p.~29--32, 1956.

(Translation available in {\it Soviet Math.\ Doklady}.)

\bibitem{Mu2}
 {\it Al.~A.~Muchnik.}
  On reduction of the problems of decidability of enumerable sets
to separability problems.
{\it Izvestija Akademii Nauk SSSR. Serija matematicheskaja\/}
{\bf29}, no.~3, p.~717--724, 1965.

(Translation available in {\it Soviet Math.\ Izvestiya}.)

\bibitem{MP}
 {\it An.~A.~Muchnik, S.~E.~Positselsky.}
  On one class of enumerable sets. (Russian.)
{\it Uspehi matematicheskih nauk\/} {\bf54}, no.~3, p.~171--172, 1999.

(Translation available in {\it Russian Math.\ Surveys}.)

\bibitem{Post}
 {\it E.~L.~Post.}
  Recursively enumerable sets of positive integers
  and their decision problems.
{\it Bulletin of the American Mathematical Society\/}
{\bf50}, no.~5, p.~284--316, 1944.

\bibitem{UsSem}
 {\it V.~Uspensky, A.~Semenov.}
  Algorithms: main ideas and applications.
Kluwer Academic Publishers, 1993.

\bibitem{UsSh}
 {\it V.~Uspensky, A.~Shen.}
  Relations between varieties of Kolmogorov complexities.
{\it Mathematical systems theory\/} {\bf29}, no.~3, p.~271--292, 1996.

\end{thebibliography}

\end{document}





