![]() ![]() ![]() Problemi irresolubiliIl ricoprimento di una stanza
qualsiasi non è che uno dei tanti (infiniti!) problemi per i quali non esistono
(e non esisteranno)
programmi Un esempio famoso viene dalla
stessa informatica. Ci sono programmi che, per qualche motivo (spesso un errore
di programmazione) "vanno in ciclo", cioè non terminano. Non è una bella
situazione, perché noi siamo ad aspettare un risultato e non sappiamo se il
calcolatore
Ebbene, questo non si può fare, perché il seguente problema non è C-risolubile:
Osserva che non è possibile
semplicemente provare ad eseguire P su n ed aspettare: questo basterebbe per
rispondere SI (quando effettivamente l'esecuzione si ferma), ma quando
rispondere NO? Anche dopo milioni di
istruzioni Il modo dei problemi è dunque
suddiviso in due aree tra loro molto diverse: in una stanno i problemi
C-risolubili, nell'altra quelli non C-risolubili (come i due problemi che
abbiamo descritto qui: ricoprimento di una stanza qualsiasi e programmi
che vanno in ciclo). Il seguente grafico rappresenta in modo sintetico il
mondo dei problemi e delle loro soluzioni; osserva come ogni problema
algoritmicamente risolubile
Bibliografia
|