\begin{frame}{Decidability} \begin{block}{} A \emph{decision problem $P$} is a language $P \subseteq \Sigma^*$. \medskip The problem $P$ is called \begin{itemize} \item \emph{decidable} if the $P$ is recursive, otherwise \emph{undeciable}, \item \emph{semidecidable} if the $P$ is recursively enumerable. \end{itemize} \end{block} \pause \begin{goal}{} Decidable problem: \begin{itemize} \item algorithm that always halts \item always answers yes or no \end{itemize} \end{goal} \pause \begin{goal}{} Semidecidable problem: \begin{itemize} \item algorithm halts (eventually) it the answer is yes ($w \in P$), \item may or may not halt if the answer is no ($w \not\in P$). \end{itemize} \end{goal} (Problem: one cannot know how long to wait for an answer.) \end{frame}