Problema della terminazione

Questa voce o sezione sugli argomenti logica e algoritmi non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

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 ingresso finito, stabilire se l'algoritmo in questione termina o continua la sua esecuzione all'infinito. È stato dimostrato che non può esistere un algoritmo generale in grado di risolvere il problema per tutti i possibili ingressi. La versione più nota del problema è quella proposta nel 1936 dal matematico Alan Turing, insieme alla dimostrazione della sua indecidibilità.

Si supponga per assurdo che esista un algoritmo che prende in ingresso un qualsiasi altro algoritmo a avente un ingresso finito d ed è in grado di stabilire se a termina in tempo finito (restituendo il valore true) o se non termina (restituendo in questo caso il valore false).

// halts() restituisce true se il suo input termina, false altrimenti boolean C(a, d):     return halts(a(d)); 

Essendo per la macchina sia a sia d sequenze indistinte di simboli, è possibile 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): è possibile costruire un altro algoritmo chiamato K che, prendendo in ingresso a, esegue loop non restituendo alcun valore se C(a,a) restituisce true, mentre restituisce true se C(a,a) restituisce false. Ovvero:

// loop() è una funzione che non termina boolean K(a):   if C(a,a) loop();     return true; 

Quindi K termina restituendo il valore true solo se l'algoritmo a con ingresso a non termina, altrimenti K continua a eseguire loop ciclando all'infinito senza restituire alcun valore.

Passando all'algoritmo K lo stesso K, ovvero K(K), questo algoritmo termina, restituendo il valore true, solo se l'algoritmo K con input K non termina. Ovvero K(K) termina se e solo se K(K) non termina, il che è una contraddizione che prova essere assurda l'ipotesi iniziale sull'esistenza di 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.

Si indichi con L_H il linguaggio dell'Halting problem e si supponga che L_H sia decidibile. Allora per definizione esiste una macchina di Turing T che decide L_H e che per un qualsiasi input x la computazione T(x) va

• nello stato di accettazione se x${\displaystyle \in }$ L_H ;
• nello stato di rigetto se x${\displaystyle \not \in }$L_H .

Da T si deriva una seconda macchina di Turing T' complementando gli stati di accettazione e di rigetto della macchina T, quindi la computazione di T'(x) va

• nello stato di accettazione se x${\displaystyle \not \in }$L_H  ;
• nello stato di rigetto se x ${\displaystyle \in }$ L_H.

Da T' si deriva una terza macchina di Turing T'' che o accetta o non termina, quindi la computazione di T''(x) va

• nello stato di accettazione se T' accetta;
• non termina se T' rigetta.

Poiché l'insieme delle macchine di Turing Ť è numerabile allora T ${\displaystyle \in }$ Ť questo implica che ${\displaystyle \exists }$ n ${\displaystyle \in }$ N (insieme dei numeri naturali) tale che T_n(n) = T''(n).

Se T_n(n) accetta allora anche T'(n) dovrebbe accettare, ma se T'(n) accetta allora significa che n${\displaystyle \not \in }$L_H e se n${\displaystyle \not \in }$L_H allora T_n(n) rigetta.

Se T_n(n) rigetta allora anche T'(n) dovrebbe rigettare, ma se T'(n) rigetta allora n ${\displaystyle \in }$ L_H e se n ${\displaystyle \in }$ L_H allora T_n(n) accetta.

In entrambi i casi esiste una contraddizione, quindi T'' non esiste e poiché T'' è ottenuta mediante semplici modifiche alla macchina T che decide L_H questo porta a dire che L_H non è decidibile.

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

• (EN) halting problem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Problema della terminazione, su MathWorld, Wolfram Research.

Portale Informatica

Portale Matematica