Limiti della Computazione

Il teorema di Rice dice che ogni proprietà semantica non banale dei programmi è indecidibile. Non difficile, non costosa: indecidibile. Nessuna procedura prende il testo di un programma e restituisce che cosa quel programma significa.

Di solito lo si archivia come curiosità, un risultato che riguarda programmi patologici e non l'ingegneria vera. Preso alla lettera è invece un vincolo di metodo: ispezionare non è un modo per scoprire, e non c'è lettura abbastanza attenta da rimediare.

Il teorema parla di tutti i programmi e di tutte le proprietà, ed è anche il suo punto debole. Basta limitare tempo, memoria e input perché una parte di ciò che era indecidibile diventi soltanto costoso. Dove cada quel confine, per un sistema preciso, è una domanda vera con una risposta vera.

Il lavoro sta lì: capire quali proprietà dei sistemi che si costruiscono oggi finiscono dalla parte decidibile una volta fissati i limiti, quanto costa deciderle, e che cosa va eseguito perché non c'è altro modo di saperlo.