11/116
\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{block}{Theorem}
The halting problem $H$ is undecidable.
\end{block}
(The language $H$ is not recursive.)
\end{frame}