\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}