Teorema di Rice

Da Wikipedia, l'enciclopedia libera.

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, è indecidibile 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.

Enunciato formale del teorema[modifica | modifica wikitesto]

  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} è indecidibile.

Dimostrazione del Teorema[modifica | modifica wikitesto]

Senza perdita di generalità, dimostriamo il teorema attraverso un'enumerazione della Macchina di Turing, dato che ci si può sempre ricondurre al caso di funzioni[non chiaro]. 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.

Fonti[modifica | modifica wikitesto]

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


matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica