Teorema di Rice

Nella logica matematica, nella teoria della calcolabilità e nell'informatica teorica, il teorema di Rice costituisce un importante risultato nella teoria delle funzioni ricorsive e delle funzioni calcolabili (le due sono la stessa cosa, secondo la tesi di Church-Turing). Esso afferma che, per ogni proprietà non banale delle funzioni calcolabili, è non decidibile il problema di decidere quali funzioni soddisfino tale proprietà e quali no. Per proprietà banale in questo caso si intende una proprietà che non effettua alcuna discriminazione tra le funzioni calcolabili, cioè che vale o per tutte o per nessuna. Il teorema prende il nome da Henry Gordon Rice, il quale ne fornì la dimostrazione nel 1951 nella sua tesi di dottorato presso la Syracuse University.

Enunciato formale del teorema

1. Consideriamo una qualunque enumerazione delle funzioni ricorsive (ricordiamo che funzioni ricorsive e calcolabili sono la stessa cosa), in cui la funzione $\varphi _{i}$ corrisponde alla ${\mathit {i}}$-esima funzione ricorsiva. Indichiamo l'insieme di tutte le funzioni ricorsive con ${\mathit {R}}=\lbrace \varphi _{x}|x\in \mathbb {N} \ \rbrace$.
2. Consideriamo inoltre l'insieme ${\mathit {P}}$ di funzioni ricorsive (formalmente ${\mathit {P}}\subseteq {\mathit {R}}$), che esprime una certa proprietà di queste funzioni, nel senso che esso contiene solo quelle funzioni ricorsive che soddisfano la proprietà.
3. Consideriamo infine l'insieme ${\mathit {S}}$, che contiene gli indici (secondo l'enumerazione del punto 1) delle funzioni contenute in ${\mathit {P}}$, cioè più formalmente ${\mathit {S}}=\lbrace x|\varphi _{x}\in {\mathit {P}}\rbrace$.

L'insieme ${S}$ è decidibile se e solo se ${\mathit {P}}$ è l'insieme vuoto (ossia ${\mathit {P}}=\emptyset \;$) o se coincide esattamente con l'intera classe delle funzioni ricorsive, formalmente ${\mathit {P}}={\mathit {R}}=\lbrace \varphi _{x}|x\in \mathbb {N} \ \rbrace$.

Altrimenti, se ${\mathit {P}}$ è "non banale", ${\mathit {S}}$ non è decidibile.

Dimostrazione del Teorema

Dato che qualsiasi funzione può essere rappresentata da una macchina di Turing senza alcuna perdita di generalità, dimostriamo il teorema attraverso un'enumerazione della Macchina di Turing. In questo caso l'insieme S conterrà gli indici delle macchine che calcolano funzioni appartenenti a P. Supponiamo adesso che P non sia vuoto $(P\neq 0)$ e che P non coincida con l'intera classe delle funzioni ricorsive $(P\neq R)$. Inoltre supponiamo per assurdo che S sia decidibile (viste le condizioni precedenti, infatti, secondo il teorema S dovrebbe essere indecidibile). Siano i, j rispettivamente il primo indice appartenente a S e il primo indice non appartenente a S. Cioè: $i\in {\mathit {S}}$ e $j\notin {\mathit {S}}$. Adesso consideriamo la funzione:

$C(x)={\begin{cases}i&{\text{se }}x\notin S\\j&{\text{se }}x\in S\end{cases}}$

Poiché la funzione C è totale, per il Teorema di ricorsione di Kleene (o altresì chiamato Teorema di Kleene o del punto fisso) $\exists e\in N$ | $\varphi _{C(e)}=\varphi _{e}$.

Per definizione se $C(e)=i$ allora $e\notin S$ e quindi $\varphi _{e}\notin P$.

Ma per ipotesi sappiamo che $i\in S$ e $\varphi _{i}\in P$; si ha anche che $\varphi _{C(e)}=\varphi _{i}=\varphi _{e}\in P$.

Si ha quindi una contraddizione in quanto si ha contemporaneamente che: $\varphi _{e}\in P$ e $\varphi _{e}\notin P$.

Se ripetiamo il procedimento nel caso in cui $C(e)=j$ si otterrà la stessa contraddizione.

Per cui siamo arrivati ad un assurdo ed in particolare non è vera l'ipotesi iniziale che S in questo caso è decidibile. Il Teorema risulta dimostrato.

Bibliografia

• Giorgio Ausiello, Fabrizio D'amore and Giorgio Gambosi. Linguaggi Modelli Complessità, Brossura. Franco Angeli 2003. , 2001. ISBN 8846444701 / 88-464-4470-1 EAN: 9788846444707.

Collegamenti esterni

• (EN) Eric W. Weisstein, Teorema di Rice, su MathWorld, Wolfram Research.