Teorema de Rice

## *Definição de propriedade* ##

$P$ é uma propriedade se $P \subseteq RE$, sendo $RE$ o conjunto de todas as linguagens reconheciveis.<br>
$L \in RE$ satisfaz $P$ se $L \in P$.<br>
$L \in RE$ não satisfaz $P$ se $L \notin P$.

Uma propriedade diz-se **não-trivial** se $\emptyset \subset P \subset RE $. Caso contrário, se $P = \emptyset $ ou se $P = RE $, $P$ é **trivial**.
<br>
<br>
## *Teorema de Rice* ##
Sendo $P$ uma propriedade não trivial.<br>
Se

$L = \{$<$M$> $:$ $\mathcal{L}_{ac}(M)$ satisfaz $P \}$

Então $L$ é indecidível.

$P$ = $\{L:L\in RE$ e $\varepsilon \notin L \}$