Teorema di Rice

Sia $P=\{\lang M \rang | M \text{ è una MdT che verifica la proprietà } P\}$ un linguaggio che soddisfa le seguenti due condizioni:

1. l’appartenenza di $M$ a $P$ dipende solo da $L(M)$, cioè $\forall M_1,M_2$ MdT tali che $L(M_1) = L(M_2)$, $\lang M_1\rang \in P \iff \lang M_2 \rang \in P$
2. $P$ è un problema non banale, cioè $\exist M_1,M_2$ MdT tali che $\lang M_1\rang \in P$, $\lang M_2\rang \notin P$

$P$ è indecidibile

Conseguenze

Non possiamo decidere se una MdT:

• accetta $\empty$
• accetta un linguaggio finito
• accetta un linguaggio regolare, ecc

Dimostrazione

Mostriamo $A_{TM} \leq_m L_P$

• sia $T_{\empty}$ una MdT tale che $L(T_{\empty}) = \empty$
• possiamo assumere $\lang T_{\empty}\rang \notin L_P$ (altrimenti si potrebbe procedere con $\overline{L}_P$)
• poiché $L_P$ è non banale, esiste una MdT $T$ tale che $\lang T\rang \in L_P$

Progettiamo una funzione $f$ come segue: $f( \lang M,w \rang ) = \lang S \rang$

dove su input $x$ simula $M$ con input $w$:

• se $M$ si ferma e rifiuta, allora $S$ rifiuta $x$
• se $M$ accetta, allora $S$ simula $T$ su input $x$:
  • se $T$ accetta $x$ allora $S$ accetta
  • se $T$ rifiuta $x$ allora $S$ rifiuta

Mostriamo che la funzione $f$ è una riduzione