Il teorema di Rice afferma che “Qualunque proprietà non banale delle funzioni calcolabili è indecidibile”. Vediamolo meglio nel dettaglio.
Enunciato del teorema di rice
Sia F una famiglia di funzioni calcolabili, allora l’insieme:
E’ decidile se e solo se F coincide con l’insieme vuoto, quindi F=0, o se F coincide esattamente con l’intera classe di funzioni calcolabili.
Dimostrazione del teorema di Rice
Supponiamo che F non sia vuoto e che non coincida esattamente con l’intera classe di funzioni calcolabili(usiamo questo argomento come strumento di diagonalizzazione).
Supponiamo per assurdo che S sia decidibile. Ci sono quindi funzioni calcolabili che appartengono e non appartengono a S, quindi siano i e j gli indici rispettivamente per cui:
- ϕi ∈ F cioè i ∈ S
- ϕj ∉ F cioè j ∉ S
Siccome abbiamo detto che S è decidile, allora esiste una macchina di Turing M che la calcola:
Quindi si ha che ∀ x ∈ ℕ che
Siccome g è totale e calcolabile allora secondo il teorema di Kleene ci da un naturale e tale che ϕg(e) = ϕe, e questo conduce alla contraddizione
ϕe ∈ F se e solo se ϕe ∉ F
Dunque abbiamo verificato che S non è decidibile.
