\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}