9/40
\begin{frame}
  \small
  
  \begin{problem}[Halting Problem]
  Input: Turing machine $M$, word $w \in \Sigma^*$\\
  Question: Does $M$ halt on $w$?
  \end{problem}
  \smallskip\pause
  
  \begin{problem}[Empty-Tape Halting Problem]
  Input: Turing machine $M$\\
  Question: Does $M$ halt on the empty tape $\epsilon$?
  \end{problem}
  \smallskip\pause

  \begin{problem}[Uniform Halting Problem]
  Input: Turing machine $M$\\
  Question: Does $M$ halt on all configurations?
  \end{problem}
  \smallskip\pause
  
  \begin{problem}[Totality Problem]
  Input: Turing machine $M$\\
  Question: Does $M$ halt on all natural numbers $\{s^n 0 \mid n \in \NN\}$?
  \end{problem}
\end{frame}