Problema della terminazione

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 $\in$ L_H ;
nello stato di rigetto se x $\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 $\not \in$ L_H ;
nello stato di rigetto se x $\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 $\in$ Ť questo implica che $\exists$ n $\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 $\not \in$ L_H e se n $\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 $\in$ L_H e se n $\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.