14/40
\begin{frame}
  \small
  
  \begin{center}
  \newcommand{\mdown}{-.6cm}
  \begin{tikzpicture}[node distance=20mm,thick,>=stealth]
  \node (d00) {$\cpi{0}{0} = \csig{0}{0} = \cdel{0}{0} $};
  \node (p01) [above left of=d00,yshift=\mdown] {$\cpi{0}{1}$}; \draw [->] (d00) -- (p01);
  \node (s01) [above right of=d00,yshift=\mdown] {$\csig{0}{1}$}; \draw [->] (d00) -- (s01);
  \node (d02) [above right of=p01,yshift=\mdown] {$\cdel{0}{2}$}; \draw [->] (p01) -- (d02); \draw [->] (s01) -- (d02);
  \node (p02) [above left of=d02,yshift=\mdown] {${\cpi{0}{2}}$}; \draw [->] (d02) -- (p02);
  \node (s02) [above right of=d02,yshift=\mdown] {$\csig{0}{2}$}; \draw [->] (d02) -- (s02);
  \node (d03) [above right of=p02,yshift=\mdown] {$\vdots$}; \draw [->] (p02) -- (d03); \draw [->] (s02) -- (d03);
  \node (d04) [above of=d03,node distance=5mm,yshift=\mdown] {$\vdots$};

  \begin{scope}[draw=black!50]
  \node (fr) [node distance=20mm,left of=p02,yshift=7mm,cloud,cloud puffs=22,draw,cloud ignores aspect,fill=orange!15,inner sep=.5mm] 
             {\parbox{2.5cm}{\centerline{Uniform}\centerline{Halting Problem}}};
  \draw [dashed] (p02) -- (fr);

  \node (fr) [node distance=20mm,left of=p02,yshift=-7mm,cloud,cloud puffs=22,draw,cloud ignores aspect,fill=orange!15,inner sep=.5mm] 
             {\parbox{2.1cm}{\centerline{Totality Problem}}};
  \draw [dashed] (p02) -- (fr);

  \node (psf) [node distance=20mm,right of=s01,yshift=7mm,xshift=5mm,cloud,cloud puffs=27,draw,cloud ignores aspect,fill=orange!15,inner sep=.5mm] 
             {\parbox{2.5cm}{\centerline{Halting Problem}}};
  \draw [dashed] (s01) -- (psf);

  \node (psf) [node distance=20mm,right of=s01,yshift=-7mm,xshift=5mm,cloud,cloud puffs=27,draw,cloud ignores aspect,fill=orange!15,inner sep=.5mm] 
             {\parbox{2.5cm}{\centerline{Empty Tape}\centerline{Halting Problem}}};
  \draw [dashed] (s01) -- (psf);

  \node (psf) [node distance=20mm,right of=s01,yshift=20mm,xshift=5mm,cloud,cloud puffs=27,draw,cloud ignores aspect,fill=orange!15,inner sep=.5mm] 
             {\parbox{2.5cm}{\centerline{Recursively Enumerable}}};
  \draw [dashed] (s01) to[bend left=20] (psf);

  \node (psf) [node distance=20mm,left of=d00,xshift=-15mm,cloud,cloud puffs=27,draw,cloud ignores aspect,fill=orange!15,inner sep=.5mm] 
             {\parbox{2.5cm}{\centerline{Decidable Problems}}};
  \draw [dashed] (d00) -- (psf);
  \end{scope}
  \end{tikzpicture}
  \end{center}

  \pause
  \begin{definition}
  A problem $A \subseteq \NN^d$ is:
  \begin{itemize}
    \item in $\csig{0}{1}$ if $\vec{x} \in A \Longleftrightarrow \exists y.\; P(\vec{x},y)$,
    \item in $\cpi{0}{2}$ if $\vec{x} \in A \Longleftrightarrow \forall y.\; \exists z.\; P(\vec{x},y,z)$,
  \end{itemize}
  for some decidable predicate $P$.
  \end{definition}
\end{frame}