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