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