\begin{frame} \frametitle{Termination} \begin{goal}{} Assume there was a \emph{program $\terminator$} that decides termination: \begin{itemize} \item input: a program \forestgreen{$P$} and input \forestgreen{$w$} \item output: \emph{yes} if \forestgreen{$P$} terminates on input \forestgreen{$w$}, \emph{no} otherwise \end{itemize} \end{goal} \pause\medskip Then using $\terminator$ we can create a program $\terminatoronitself$\ : \pause \begin{goal}{} Then there exists a \emph{program $\terminatoronitself$}\; with the behaviour: \begin{itemize} \item input: a program \forestgreen{$P$} \item output: \emph{yes} if \forestgreen{$P$} terminates on input \forestgreen{$P$}, \emph{no} otherwise \end{itemize} \end{goal} \hint{Note that $\terminatoronitself$ is a special case of $\terminator$ where $\forestgreen{w} = \forestgreen{P}$.} \pause\medskip \begin{exampleblock}{} Programs started on itself:\;\; {\small \texttt{/bin/cat /bin/cat}} \end{exampleblock} \pause \begin{alertblock}{} We show that $\terminatoronitself$\; does not exist. \medskip Then it follows that $\terminator$ does not exist. \end{alertblock} \end{frame}