\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{goal}{Theorem of Rice}
    Every \emph{non-trivial} property $P$ of recursively enumerable languages is undecidable.
  \end{goal}
  \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$!}
    \pause\medskip

    Construct a TM $M_x$ such that \alert{$M_x$ accepts $y$ if $x\in L$ and $y\in L_0$}.
    \pause
    \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
    \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}