\begin{frame}{Semidecidability}
  \begin{goal}{}
    Recall that a decision $P \subseteq \Sigma^*$ is called
    \begin{itemize}
      \item \emph{decidable} if the $P$ is recursive,
      \item \emph{semidecidable} if the $P$ is recursively enumerable.
    \end{itemize}
  \end{goal}
  \pause
  
  \begin{exampleblock}{}
    Examples of (undecidable but) semidecidable problems:
    \begin{itemize}
      \item halting problem,
      \item Post correspondence problem,
      \item non-empty intersection of context-free languages,
      \item ambiguity of context-free grammars.
    \end{itemize}    
  \end{exampleblock}
  \pause\medskip
  
  There exist algorithms for these problems that always halt if the answer is yes,
  but \alert{may or may not halt if the answer is no}.
  \bigskip  
\end{frame}