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à.

Dimostrazione di indecidibilità

[modifica | modifica wikitesto]

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.

Dimostrazione che il linguaggio dell'Halting Problem è un linguaggio non decidibile

[modifica | modifica wikitesto]

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.

Relazioni con altri teoremi

[modifica | modifica wikitesto]

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.