%\documentclass{beamer}
\documentclass[handout]{beamer}
%\documentclass[draft]{beamer}
%\includeonlyframes{SimulTheorem}
\newcommand{\dom}{{\rm dom}}
\newcommand{\N}{{\bf N}}
\newcommand{\D}{\Delta}
\def \T  {\mathcal{T}} 
\newcommand{\fbin}{\mbox{\rm \footnotesize{bin}}}

\newenvironment{alertitemize}%
  {\begin{itemize}[<+-| alert@+>]}%
  {\end{itemize}}
\newcommand\stopalert{\onslide<+| handout:0>}

\usepackage{geometry} 
% Load a theme for the presentation
%\usepackage{beamerthemeshadow}
\mode<article> % only for the article version
{
  \usepackage{fullpage}
  \usepackage{hyperref}
}

  \mode<presentation>
{% \usetheme{Bergen}%{AnnArbor}
  \usetheme{Ilmenau}%{AnnArbor}%{Darmstadt}
%\usetheme{Boadilla}
  \usefonttheme[onlysmall]{structurebold}
  %\usecolortheme{beaver}%seahorse}
  \usecolortheme{crane}
 \usecolortheme{whale}
  %\usecolortheme{sidebartab}
    \setbeamertemplate{background canvas}[vertical shading][bottom=red!10,top=blue!10]
 }
 
 
  \usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
\usepackage{amsmath,amssymb}
\usepackage[latin1]{inputenc}
\usepackage{colortbl}
\usepackage[english]{babel}

\newcommand{\bin}{\mbox{\rm  bin}}
\def \x {\mathbf{x}}
\def \y {\mathbf{y}}
\def \z {\mathbf{z}}
\def \fU{{\mathfrak U}}
\def \fV{{\mathfrak V}}
\def \hmass#1#2{{\bbbl}_{#1}(#2)}
\def \bbbi{{\mathrm{I\!I}}}
\def \bbbf{{\mathrm{I\!F}}}
\def \bbbn{{\mathrm{I\!N}}}
\def \N  {\bbbn}
\def \bbbb{{\mathrm{I\!B}}}
\def \bbbl{{\mathit{I\!\!L}}}
% \def \card {\mathop{\rm\#}}
\def \infix#1{\mathbf{infix}({#1})}
\newcommand{\RC}{{\mathcal R}}
\def \rem#1{{\bfseries\sffamily Reminder !!!: }{\tt #1}\par}


\definecolor{MyDarkBlue}{rgb}{0,0.08,0.45}
\definecolor{MyBlue}{rgb}{0,0,1}
\definecolor{MyLightMagenta}{cmyk}{0.1,0.8,0,0.1}
\definecolor{MyGreen}{rgb}{0,0.9,0.1}
\definecolor{MyYellow}{rgb}{0.7,0.8,0.1}
\definecolor{MyDarkGreen}{rgb}{0,7.0,0.2}
\definecolor{MyLightBlue}{rgb}{0,0.8,0.9}
\definecolor{MyGray}{cmy}{1,1,0.8}
\definecolor{MyBrick}{rgb}{0.4,0,0.3}
\definecolor{MyWhite}{rgb}{255,255,255}

\newcommand{\raisedot}{%
  \makebox[0cm][c]{%
  \raisebox{0.19\baselineskip}{\ensuremath{.}}}}


\title{On Universal Computably Enumerable
Prefix
  Codes
}
\author{Cristian~S.~Calude and Ludwig Staiger}
\date{2007}



\begin{document}
% Create the title frame

\frame{\titlepage}
% ----------------------------------
% Create the outline frame
% ----------------------------------
\section*{Outline}
\frame{\tableofcontents}

\section{Characterisation of universal c.e.\ prefix codes}

 \begin{frame}
  \frametitle{\small Introduction \hfill 1}
  
  Fix  an alphabet $X = \{0,\ldots ,r-1\}$ and denote by $X^*$  the set of finite strings (words) on $X$.
  \medskip
  \pause
  
  If $v$ is a prefix of $w$ we write
$v\sqsubseteq w$. A set $V\subseteq X^{*}$ is \alert{prefix-free} or a \alert{prefix code} if for all $v,w \in V$ with $v\sqsubseteq w$ we have $v=w$.
  \medskip
  \pause
 
  
  A {\it self-delimiting Turing machine} (shortly, a {\it machine}) is a
Turing
machine $C$ processing binary strings such that its program set (domain)
$\dom(C) =\big\{\pi\mid \pi\in X^*\wedge \mid C(\pi) \mbox{
halts}\big\}$  is
prefix-free.

 \medskip
  \pause


A prefix code is \alert{computably enumerable (c.e.)} iff it is
the domain of a machine.
\end{frame}
 \begin{frame}
  \frametitle{\small Introduction \hfill 2}

We can effectively construct a machine $U$ (called \alert{universal}) such
that
for every machine $C$, there exists a constant $k$ (depending only on
$U$ and
$C$) such that for every string $\pi \in \dom(C)$ there exists a string
$\pi'
\in \dom(U)$ such that $U(\pi')=C(\pi)$ and $|\pi{}'| \le |\pi{}| + k$.

 \medskip
  \pause



A \alert{prefix-universal} machine $U$ is a machine
such that for every  machine $C$
there
exists a string $w$ (depending only on $U$ and $C$) such that for every
string
$\pi{} \in \dom(C)$ we have $U(w\pi{}) = C(\pi{})$.


 \medskip
  \pause


Every prefix-universal machine is universal, but the converse is not true.

   \end{frame}

 \begin{frame}
  \frametitle{\small Main questions}

 We say that a c.e.\ prefix code is {\it universal} if it  supersets  the domain of a 
  universal machine.
  
  \begin{itemize}
  \item Characterise universal c.e.\ prefix codes.
  \item
  \end{itemize}
  
  
   \end{frame}
 
 \begin{frame}
  \frametitle{\small A characterisation of universal c.e.\ prefix codes \hfill 1}
  \begin{theorem} \label{eq}
  Let $V\subseteq X^{*}$ be a c.e.\ prefix code. Then, the following
  statements are equivalent:
\begin{enumerate}
\item[{\rm 1.}] The set  $V$ is a universal c.e.\ prefix code.

\item[{\rm 2.}] For every partial
 computable one-one function $g:\bbbn\to
  X^{*}$ having a prefix-free range, there exist a partial
 computable
  one-one function $f :\bbbn\to X^{*}$ and a constant $k\in\bbbn$ such
that
\begin{enumerate}
\item[{\rm a.}]  $f(\dom (f)) \subseteq V$,
\item[{\rm b.}]  $\dom (g) \subseteq \dom (f)$ and $|f(n)| \le |g(n)| +
k$,
  for every $n\in \dom (g)$.
\end{enumerate}

\end{enumerate}
\end{theorem}
\end{frame}
 
 \begin{frame}
  \frametitle{\small A characterisation of universal c.e.\ prefix codes \hfill 2}
   \begin{theorem}[continuation]
   \begin{enumerate}
  \item[{\rm 3.}] For every computable one-one function $g:\bbbn\to X^{*}$
  having a prefix-free range, there exist a computable one-one function
  $f:\bbbn\to X^{*}$ and a constant $k\in\bbbn$ such that
\begin{enumerate}
\item[{\rm a.}]  $f(\bbbn) \subseteq V$,
\item[{\rm b.}]  $|f(n)| \le |g(n)| + k$, for every $n\in \bbbn$.
\end{enumerate}
\item[{\rm 4.}]  For every c.e.\ prefix code $D\subseteq X^{*}$ there
exist a
  partial
 computable one-one function $\varphi:X^{*}\to X^{*}$ and a
  constant
  $k\in\bbbn$
  such that:
\begin{enumerate}
\item[{\rm a.}] $D\subseteq\dom(\varphi)$, $\varphi (D) \subseteq V$,
and
\item[{\rm b.}] $|\varphi (u)| \le |u| + k$, for every $u \in
\dom(\varphi)$.
\end{enumerate}
\end{enumerate}
\end{theorem}

   \end{frame}
 \begin{frame}
   \frametitle{\small A characterisation of universal c.e.\ prefix codes \hfill 3}

 For the case $V=\dom(U)$, where $U$ is a universal machine we have:
 \begin{corollary}\label{c.eq}
  For every c.e.\ prefix code $D\subseteq X^{*}$ and every universal
machine
  $U$ there are a one-one partial
 computable one-one function
  $\varphi:X^{*}\to X^{*}$ and a constant $k\in\bbbn$ such that:
\begin{enumerate}
\item[{\rm a.}] $D\subseteq\dom(\varphi)$, $\varphi(D) \subseteq
\dom(U)$,
\item[{\rm b.}] $|\varphi (u)| \le |u| + k$, for all $u \in D$, and
\item[{\rm c.}] $U(\varphi(u))=u$, for all $u\in D$.
\end{enumerate}
\end{corollary}
 \end{frame}
 
 \begin{frame}
  \frametitle{\small A characterisation of universal c.e.\ prefix codes \hfill 4}

 \begin{theorem}\label{eq=}
  Let $V\subseteq X^{*}$ be a c.e.\ prefix code. Then, the following
  statements are equivalent:
\begin{enumerate}
\item[{\rm 1.}] There exists a prefix-universal machine $U$ such that
$V= \dom
  (U)$.
\item[{\rm 2.}] For every c.e.\ prefix code $D\subseteq X^{*}$ there
exists a
  string $w\in X^{*}$ such that $wD = V \cap wX^{*}$.
\end{enumerate}
\end{theorem}
\end{frame}
 \section{Properties of universal c.e.\ prefix codes}

\begin{frame}
  \frametitle{\small Noncomputability}
  
  \begin{theorem}\label{th.noncomp}
  No universal c.e.\ prefix code $V\subseteq X^{*}$ is computable.
\end{theorem}

   \end{frame}
 
 \begin{frame}
  \frametitle{\small Maximality}
  
A
prefix
code $V$ is  \alert{maximal} if for every prefix code $W$,
$V\subseteq W$ implies $W=V$.

\medskip
\pause

\begin{lemma}\label{l.max}
  If $V\subseteq X^{*}$ is a c.e.\ maximal prefix code, then $V$ is
computable.
\end{lemma}



\medskip
\pause

With Theorem~\ref{th.noncomp} we obtain the following.
\begin{corollary}\label{c.cemax}
  No universal c.e.\ prefix code is a maximal prefix code.
\end{corollary}


\medskip
\pause

Not every computable prefix
code is contained in  a computable maximal prefix code.

   \end{frame}
 
 \begin{frame}
  \frametitle{\small Sparsity}

A set $W\subseteq X^{*}$ is called \alert{sparse} if there
is a polynomial $p(n)$ such that $|W\cap
X^{n}|\leq p(n)$ for every $n\in \bbbn$.

\begin{theorem}
  \label{l.div2}Let $W\subseteq X^{*}$ be the complement of c.e.\ subset
of
  $X^{*}$, and let $W$ be non-sparse. Then, for all $0\leq \alpha<1$ we
have:
\[\sum\nolimits_{w\in W}
  r^{-\alpha\cdot H_{U}(w)}=\infty.\]
\end{theorem}
\begin{frame}
  \frametitle{\small Entropy}
   \end{frame}
 
\end{frame}
 \end{document}
 \begin{frame}
  \frametitle{\small }
   \end{frame}
   
  
   
  

