Problema della terminazione

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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, 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 decidibile[modifica | modifica wikitesto]

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

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 xLH ;
  • 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 nLH e se nLH 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 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.

Controllo di autoritàGND (DE4247732-3