8/116
\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}