\begin{frame}
  \frametitle{Decision Problems: Examples}

  \begin{alertblock}{\firebrick{Prime Problem}}
    Determine whether a \emph{number is prime}:
    \begin{itemize}
      \item input: a natural number \forestgreen{$n$}
      \item output: \emph{yes} if \forestgreen{$n$} is prime, \emph{no} otherwise
    \end{itemize}
  \end{alertblock}
  \pause
  
  \begin{alertblock}{\firebrick{Termination Problem}}
    Decide whether a \emph{program terminates}:  
    \begin{itemize}
      \item input: a program \forestgreen{$P$} and input \forestgreen{$w$}
      \item output: \alert{yes} if \forestgreen{$P$} started with input \forestgreen{$w$} terminates, \alert{no} else
    \end{itemize}
    (Termination means that the program does not run forever.)
  \end{alertblock}
  \pause

  \begin{alertblock}{\firebrick{Validity Problem}}
    Determine whether a \emph{formula is valid}:
    \begin{itemize}
      \item input: a formula $\forestgreen{\phi}$ of predicate logic
      \item output: \alert{yes} if $\forestgreen{\phi}$ is valid, \alert{no} otherwise
    \end{itemize}
  \end{alertblock}
\end{frame}