\begin{frame}{Theorem of Rice (1951)}
    A property of a class $K$ is \emph{trivial} if it holds 
    for \emph{all} or \emph{no} $k \in K$.
  \begin{block}{Theorem of Rice}
    Every \emph{non-trivial} property $P$ of recursively enumerable languages is undecidable.
    Assume that \alert{$P(\emptyset)$} (if not, take $\neg P$).
    Let $L_0$ be a recursively enumerable language with \alert{$\neg P(L_0)$}.
    Let \alert{$L$} be recursively enumerable. \pause \alert{We decide $x \in L(M)$!}

    For a word $x$, we construct a Turing machine $M_x$ with
      L(M_x) = \emptyset \quad \text{if $x \not\in L$} &&
      L(M_x) = L_0 \quad \text{if $x \in L$} 
    $M_x$ accepts $y$ if $x\in L$ and $y\in L_0$.
    \alert{Then $x \not\in L \iff P(L(M_x))$.}
    \emph{Contradiction:} decidability of $P$ $\implies$ $L$ recursive.