\begin{frame}{The Halting Problem (1936)}
  \begin{block}{}
    The \emph{halting problem} is: given 
    \begin{itemize}
      \item a deterministic Turing machine $M$ and
      \item a word $x$,
    \end{itemize}
    does $M$ reach a halting state when started with input $x$?
  \end{block}
  \pause\medskip
  
  \begin{goal}{}
    The halting problem can be viewed as a language $H$
    \begin{talign}
      H \;=\; \{\, (M,x) \mid \text{$M$ reaches a halting state on input $x$} \,\}
    \end{talign}
  \end{goal}
  $M$ is an encoding of a deterministic Turing machine as a word. 
  \pause\medskip

  \begin{goal}{Theorem}
    The halting problem $H$ is undecidable.
  \end{goal}
  (The language $H$ is not recursive.)
\end{frame}

\themex{The Halting Problem is Undecidable - Proof 1}