38/116
\begin{frame}{Theorem of Rice (1951)}
\begin{goal}{}
A property of a class $K$ is \emph{trivial} if it holds
for \emph{all} or \emph{no} $k \in K$.
\end{goal}
\pause\medskip

\begin{block}{Theorem of Rice}
Every \emph{non-trivial} property $P$ of recursively enumerable languages is undecidable.
\end{block}
\pause

\begin{proof}
Assume that \alert{$P(\emptyset)$} (if not, take $\neg P$).
\pause\smallskip

Let $L_0$ be a recursively enumerable language with \alert{$\neg P(L_0)$}.
\pause\medskip

Let \alert{$L$} be recursively enumerable. \pause \alert{We decide $x \in L(M)$!}
\pause\medskip

For a word $x$, we construct a Turing machine $M_x$ with
\begin{talign}
L(M_x) = \emptyset \quad \text{if $x \not\in L$} &&
L(M_x) = L_0 \quad \text{if $x \in L$}
\end{talign}
\pause
$M_x$ accepts $y$ if $x\in L$ and $y\in L_0$.
\pause
\alert{Then $x \not\in L \iff P(L(M_x))$.}
\pause\medskip

\emph{Contradiction:} decidability of $P$ $\implies$ $L$ recursive.
\end{proof}
\end{frame}