\begin{frame}
  \frametitle{Decidability}

  \begin{goal}{Decidability}
    A decision problem $\yesinstances \subseteq \instances$ is called \emph{solvable} or \emph{decidable}\\ 
    if there exists a program
    that tells for every $\forestgreen{i} \in \instances$ whether $\forestgreen{i} \in \yesinstances$.
    \medskip
    
    In other words, the program has the following behaviour:
    \begin{itemize}
      \item input:  \tabto{1.5cm} $\forestgreen{i} \in \instances$
      \item output: \tabto{1.5cm} \firebrick{yes} \tabto{2.3cm} if $\forestgreen{i} \in \yesinstances$ 
                    \tabto{1.5cm} \firebrick{no}  \tabto{2.3cm} if $\forestgreen{i} \not\in \yesinstances$
    \end{itemize}
  \end{goal}
  \pause
  
  \begin{exampleblock}{}
    Clearly, the \emph{prime problem} is decidable.
    \medskip
    
    We can write a program deciding whether a number is prime.
  \end{exampleblock}
  \pause\bigskip
  
  \begin{alertblock}{}
    Is there such a program for every decision problem?
  \end{alertblock}
  \pause

  \begin{alertblock}{}
    Can we write a program that decides termination?
  \end{alertblock}
\end{frame}

\theme{Termination Problem (Halting Problem)}