\documentclass[a4paper,draft]{slides}
\usepackage{amsmath,amssymb}
\def\N{\mathbb{N}}
\def\eps{\varepsilon}
\def\B{\{0,1\}}
\def\email#1{\texttt{#1}}
\begin{document}\sloppy

\begin{titlepage}
  \begin{center}
Bruno Durand,
{\tiny
Laboratoire d'Informatique Fondamentale
de Marseille}\\
Andrei Muchnik, {\tiny Institute of New Technologies, Moscow} \\
Maxim Ushakov, {\tiny Moscow State University} \\
Nikolai Vereshchagin, {\tiny Moscow State Univesity}\\[3cm]

    \Large \textbf {Ecological Turing machines}
  \end{center}
\end{titlepage}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}\Large \textbf{Motivations}\end{center}

Conventional Turing machines: tape alphabet $\ne$ input
alphabet.
% Usually we have input alphabet $\B$, and unrestricted tape
% alphabet (it contains the end marker and other symbols).

What if we have tape alphabet $=$ input alphabet?

\begin{itemize}
\item \textbf{No end marker}: we are bound to prefix functions.
\item \textbf{No space for intermediate calculations}: to compute anything we
  have to erase something else.
\end{itemize}

We call such machines \textbf{ecological} because they should interact
with the environment without any pollution (not to destroy the
input).

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}\Large \textbf{Different models}\end{center}

Main question: ``Are ecological Turing machines equivalent to usual
Turing machines on the domain of prefix functions?''

Which particular computational model used is important:
\begin{itemize}
\item
  One or more semi-infinite tapes.
  \begin{itemize}
    \item
      One semi-infinite tape: ecological model is \textbf{weaker} than the
      conventional one,
    \item
      Two or more tapes: ecological model is \textbf{as strong} as the
      conventional one.
  \end{itemize}
\item
  One or more bi-infinite tapes. The ecological model is \textbf{weaker} than
  the conventional one.
\end{itemize}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}\Large \textbf{Semi-infinite tapes}\end{center}

\begin{itemize}
\item Semi-infinite tape(s)
\item Indepenpent heads
\item The machine knows if the head is at tape start
\end{itemize}

\begin{center}\Large \textbf{Theorem 0 (easy)}\end{center}

If there is an input delimiter that the machine can read, but not
write, then the computational model is equivalent to the usual one.

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{center}\Large \textbf{Theorem 1}\end{center}

There is a computable partial prefix function~$f:\B^*\to\B$ that is
not computable by ecological Turing machines with one semi-infinite
tape.

\textbf{Solution.} The input to the machine is of the form
\begin{center}\begin{tabular}{||c|c|c|c}
\hline
$0^k1$ & \hspace*{5em}$y$\hspace*{5em} & $u$ & \ldots \\
\hline
\end{tabular}
\end{center}

Here, $u$ is binary representation of an integer $n$, and the machine
should output $n$'th bit of $y$.

\textbf{Discussion.} The machine should reach $u$ not destroying
$y$. But to know where to stop it should keep some counter of the
head's position. It has no place for that.

\textit{This is surprisingly nontrivial to prove.}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}\Large \textbf{Theorem 2}\end{center}

If the machine has \textbf{two} or more tapes, then every computable
function is computable on this machine.

\textbf{Idea of the proof.} Use the head positions as counters, and
simulate counter machine.

\begin{itemize}
\item
  Simulate any Turing machine on a machine with $n$ counters.
\item
  Simulate $n$ counters using 2 counters.
\item
  See that one counter is always zero between steps of simulation.
\end{itemize}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}\Large \textbf{Bi-infinite tapes}\end{center}

\begin{itemize}
\item Bi-infinite tapes
\item The machne does not know the head position
\item Two inputs on each tape
\end{itemize}

\begin{center}\Large \textbf{Theorem 3}\end{center}

For any number of bi-infinite tapes there is a computable prefix
function that is not computable by the ecological machine.

%\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{center}\Large \textbf{Idea of the proof of Theorem 3}\end{center}

\textbf{Proof idea.} The function is very similar to that of Theorem
1, but the proof is completely different.

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{center}\Large \textbf{Work tape as oracle}\end{center}

\begin{itemize}
\item Read/write finite tape containing input $x$
\item Bi-infinite work tape containing input $\alpha$
\item Both tapes' alphabets are binary
\end{itemize}

\begin{center}\Large \textbf{Theorem 4}\end{center}

There is a total function $f\colon \B^{*}\to\B$ and a bi-infinite
binary sequence $\alpha$ such that $f$ is computable relative to
$\alpha$ but $f$ cannot be computed by any ecological Turing machine
of the described type.

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}\Large \textbf{Idea of the proof of Theorem 4}\end{center}

\begin{itemize}
\item The function is similar to one in Theorem~1
\item Diagonalization method
\item For each ecological machine construct a partial oracle that
  continues all the previous ones
\end{itemize}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}\Large \textbf{Open questions}\end{center}

\begin{enumerate}
\item
  One bi-infinite tape and one semi-infinite tape: are ecological
  machines weaker than usual ones?
  
\item
  Is there an analog of Theorem~4 for machines with one semi-infinite
  tape?

\item
  Resource bounds: With two semi-infinite tapes, ecological machines
  are as strong as usual ones. Can polynomial function be computed in
  polynomial time?

\item
  What about the power of ecological RAM (Random access machines)?

\end{enumerate}


\end{document}
