\begin{frame}{Decidability}
  \begin{goal}{}
    A decision problem $P$ is decidable if
    \begin{itemize}
      \item $P$ is semidecidable, and
      \item $\overline{P}$ is semidecidable.
    \end{itemize}
    \smallskip
  \end{goal}
  \pause\bigskip
  
  The following question is undecidable, but semidecidable:
  \begin{block}{Halting problem}
    Does TM $M$ reach a halting state for input $w$? \textcolor{gray}{(Input: $M$ and $w$.)}
  \end{block}
  \pause
  (Semidecidable: execute $M$ on $w$ and wait.)
  \pause\bigskip
    
  The following question not decidable and \alert{not} semidecidable:
  \begin{block}{Universal halting problem}
    Does TM $M$ reach a halting state on all $w \in \Sigma^*$?  \textcolor{gray}{(Input: $M$.)}
  \end{block}
  (The complement is also not semidecidable.)
  \bigskip
\end{frame}