15/162
\begin{frame}
\frametitle{Decidability}

\begin{goal}{Decidability}
A decision problem $\yesinstances \subseteq \instances$ is called \emph{solvable} or \emph{decidable}\\
if there exists a program
that tells for every $\forestgreen{i} \in \instances$ whether $\forestgreen{i} \in \yesinstances$.
\medskip

In other words, the program has the following behaviour:
\begin{itemize}
\item input:  \tabto{1.5cm} $\forestgreen{i} \in \instances$
\item output: \tabto{1.5cm} \firebrick{yes} \tabto{2.3cm} if $\forestgreen{i} \in \yesinstances$
\tabto{1.5cm} \firebrick{no}  \tabto{2.3cm} if $\forestgreen{i} \not\in \yesinstances$
\end{itemize}
\end{goal}
\pause

\begin{exampleblock}{}
Clearly, the \emph{prime problem} is decidable.
\medskip

We can write a program deciding whether a number is prime.
\end{exampleblock}
\pause\bigskip