11/162
\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

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