\begin{frame}
  \frametitle{Decision Problems}
  
  \vspace{-.5ex}
  \begin{goal}{}
    A \emph{decision problem} consists of a set $\instances$ and a predicate $\yesinstances \subseteq \instances$.
  \end{goal}
  \vspace{-.5ex}
  \pause
  
  \begin{exampleblock}{Prime Problem}
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item $\instances = \nat$
      \item $\yesinstances = \{\; n \in \nat \mid \text{$n$ is prime} \;\}$
    \end{itemize}
  \end{exampleblock}
  \vspace{-.5ex}
  \pause

  \begin{exampleblock}{Termination Problem}
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item $\instances = $ set of all pairs $\pair{\text{program}}{\text{input}}$
      \item $\yesinstances = \descsetexp{\pair{P}{w}}{\text{$P$ terminates on input $w$}}$
    \end{itemize}
  \end{exampleblock}
  \pause

  \begin{exampleblock}{Validity Problem}
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item $\instances = $ set of formulas of predicate logic
      \item $\yesinstances = $ set of valid formulas in predicate logic
    \end{itemize}
  \end{exampleblock}
  \pause

  \begin{alertblock}{}
    Can we write a program that on the input of $\forestgreen{i} \in \instances$ tells
    if $\forestgreen{i} \in \yesinstances$?
  \end{alertblock}
  \pause
  \begin{goal}{}
  If such program exists, the predicate $\yesinstances$ is called \emph{decidable}.
  \end{goal}
\end{frame}