21/162
\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

We show that $\terminatoronitself$\; does not exist.
Then it follows that $\terminator$ does not exist.