42/162
\begin{frame}[t]
  \frametitle{Termination is Undecidable (Structure of Argument)}
  
  \begin{block}{Theorem}
    The \emph{termination problem} is \alert{unsolvable} (\alert{undecidable}).
  \end{block}   
  \vspace{-3ex}
  \begin{talign}
    \mhide[10]{
      \mpause[1]{
        \text{$\terminator$ outputs \alert{yes} on input $\pair{\forestgreen{P}}{\forestgreen{w}}$}
        \;\;& \overset{ \mat{time:undefined:fail}{\mpause[?+1]{ \textcolor{red}{\huge\xmark} }} }{ \Longleftrightarrow } \;\;
        \text{$\forestgreen{P}$ halts on input $\forestgreen{w}$}
      } \\[-.95ex]
      \mpause{ & \;\; \Downarrow } \\[-.95ex]
      \mpause{
        \text{$\terminatoronitself$ outputs \alert{yes} on input $\forestgreen{P}$}
        \;\; & \Longleftrightarrow \;\;
        \text{$\forestgreen{P}$ halts on input $\forestgreen{P}$}
      } \\[-.95ex]
      \mpause{& \;\; \Downarrow} \\[-2.45ex]
    }
    \mpause{
      \text{$\diagonalisator$ halts on input $\forestgreen{P}$}
      \;\; &  \overset{ \mpause[?+5]{ \textcolor{red}{\huge\xmark} } }{ \Longleftrightarrow } \;\;
      \text{$\forestgreen{P}$ does \alert{not} halt on input $\forestgreen{P}$}
    } \\[-.95ex]
    \mpause{ & \;\; \Downarrow} \\[-.95ex]
    \mpause{
      \text{$\diagonalisator$ halts on input $\diagonalisator$}
      \;\; & \underset{ \mpause[?+1]{\textcolor{red}{\huge\xmark}\mtime{time:undefined:fail}} }{ \Longleftrightarrow } \;\;
      \text{$\diagonalisator$ does \alert{not} halt on input $\diagonalisator$}
    } 
    \mpause[+3]{
    \intertext{Compare with \emph{Russell's barber paradox}:\vspace{-.75ex}}
      \text{\firebrick{barber} shaves $\forestgreen{x}$}
      \;\; & \overset{\textcolor{red}{\huge\xmark}}{\Longleftrightarrow} \;\;
      \text{$\forestgreen{x}$ does \alert{not} shave $\forestgreen{x}$} \\[-.95ex]
      & \;\; \Downarrow \\[-.95ex]
      \text{\firebrick{barber} shaves \firebrick{barber}}
      \;\; &  \underset{\textcolor{red}{\huge\xmark}}{\Longleftrightarrow} \;\;
      \text{\firebrick{barber} does {\alert{not}} shave \firebrick{barber}}
    }
  \end{talign} 
\end{frame}