\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}