\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 \begin{alertblock}{} Is there such a program for every decision problem? \end{alertblock} \pause \begin{alertblock}{} Can we write a program that decides termination? \end{alertblock} \end{frame}