Teorema di Rice

Da Wikipedia, l'enciclopedia libera.

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 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 sorgente]

  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. L'insieme di tutte le funzioni ricorsive lo indichiamo 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 sorgente]

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

Poiché la funzione C è totale, per il Teorema di Ricorsione (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 sorgente]


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