17/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
  
  \begin{alertblock}{}
    We show that $\terminatoronitself$\; does not exist.
    \medskip
    
    Then it follows that $\terminator$ does not exist.
  \end{alertblock}
\end{frame}