Problema della terminazione

(Reindirizzamento da Problema della fermata)

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

Si supponga per assurdo che esista un algoritmo, implementato in uno pseudolinguaggio, 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 false se C(a,a) restituisce false. Ovvero:

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

Quindi K termina restituendo il valore false 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 false, 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 decidibileModifica

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

  • nello stato di accettazione se x  LH ;
  • nello stato di rigetto se x LH .

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 LH ;
  • nello stato di rigetto se x   LH.

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   Ť questo implica che   n   N (insieme dei numeri naturali) tale che Tn(n) = T''(n).

Se Tn(n) accetta allora anche T'(n) dovrebbe accettare, ma se T'(n) accetta allora significa che n LH e se n LH allora Tn(n) rigetta.

Se Tn(n) rigetta allora anche T'(n) dovrebbe rigettare, ma se T'(n) rigetta allora n   LH e se n   LH allora Tn(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 LH questo porta a dire che LH non è decidibile.

Relazioni con altri teoremiModifica

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.

Collegamenti esterniModifica

Controllo di autoritàGND (DE4247732-3