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