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