Problema della terminazione

Da Wikipedia, l'enciclopedia libera.

Il problema della terminazione (dall'inglese Halting problem, tradotto anche con problema dell'arresto o problema della fermata) chiede se sia sempre possibile, descritto un algoritmo e un determinato input finito, stabilire se l'algoritmo in questione termini o continui la sua esecuzione all'infinito. È stato dimostrato che non può esistere un algoritmo generale che possa risolvere il problema per tutti i possibili input. La versione più nota del problema è quella proposta nel 1936 dal matematico Alan Turing, insieme alla dimostrazione della sua indecidibilità.

Dimostrazione[modifica | modifica wikitesto]

Supponiamo per assurdo che esista un algoritmo (programma) C che prendendo in input un qualsiasi algoritmo a avente un input finito d, è in grado di stabilire se a termina in tempo finito (ritornando il valore true) o se non termina (ritornando in questo caso il valore false).

C(a, d) = true se a(d) termina, false se a(d) non termina.

Essendo sia a che d sequenze indistinte di simboli per la macchina possiamo passare come secondo parametro di C lo stesso algoritmo a, ovvero eseguire C(a,a).

Sia ora loop un programma che non termina mai (ad esempio while true do done): possiamo costruire un altro algoritmo che chiameremo K, che prendendo in ingresso a esegue loop (non tornando alcun valore) se C(a,a) restituisce true, mentre ritorna false se C(a,a) restituisce false. Ovvero:

K(a): if C(a,a) then loop; else return false;

In pratica K termina (restituendo il valore false) solo se l'algoritmo a con input a non termina, altrimenti K continua a eseguire loop (ciclando all'infinito) non restituendo alcun valore.

A questo punto passiamo come input dell'algoritmo K lo stesso K, ovvero:

K(K): if C(K,K) then loop; else return false;

Questo algoritmo termina (restituendo il valore false) solo se l'algoritmo K con input K non termina. Ovvero abbiamo che K(K) termina se e solo se K(K) non termina! Siamo giunti a una contraddizione che prova essere assurda l'ipotesi iniziale che esista un algoritmo C che, dato un qualsiasi algoritmo a e un suo input d, è in grado di stabilire se a(d) termina o non termina.

Relazioni con altri teoremi[modifica | modifica wikitesto]

Il teorema di Rice è una versione più generale del teorema che afferma che il problema della fermata è indecidibile. Infatti, esso afferma che, per ogni proprietà non banale delle funzioni parziali, è indecidibile il problema di determinare quali funzioni soddisfino tale proprietà e quali no.