Teorema di Rice

Da Wikipedia, l'enciclopedia libera.

Indice

1 Formulazione intuitiva del teorema
2 Enunciato formale del teorema
3 Dimostrazione del Teorema
4 Fonti

[modifica] Formulazione intuitiva del teorema

Nella logica matematica e nella teoria della calcolabilità, 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, il problema di decidere quali funzioni soddisfino tale proprietà e quali no, è indecidibile. Per proprietà banale in questo caso di intende una proprietà che non effettua alcuna discriminazione tra le funzioni calcolabili, cioè che vale o per tutte o per nessuna.

[modifica] Enunciato formale del teorema

Consideriamo una una qualunque enumerazione delle funzioni ricorsive (ricordiamo che funzioni ricorsive e calcolabili sono la stessa cosa), in cui la funzione $\varphi_i$ corrisponde alla $i$ -esima funzione ricorsiva. L'insieme di tutte le funzioni ricorsive lo indichiamo con $\mathit{R} = \lbrace \varphi_x | x \in \mathbb{N}\ \rbrace$ .
Consideriamo inoltre l'insieme $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à.
Consideriamo infine l'insieme $S$ , che contiene gli indici (secondo l'enumerazione del punto 1) delle funzioni contenute in $P$ , cioè più formalmente $\mathit{S} = \lbrace x | \varphi_x \in \mathit{P} \rbrace$ .

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

Altrimenti, se $P$ è "non banale", $S$ è indecidibile.

[modifica] Dimostrazione del Teorema

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. 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)= {i ~~~~se~~ x \notin S \choose j~~~~ se~~ x \in S}$

Poichè la funzione C è totale, per il Teorema di Ricursione (o altresì chiamato Teorema di Kleene o del punto fisso) $\exists e \in N$ t.c. $\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 otterà 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.

[modifica] Fonti

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

Estratto da "http://it.wikipedia.org../../../t/e/o/Teorema_di_Rice_c976.html"

Categorie: Logica matematica | Teoria della computazione | Teoremi