problema dell'arresto
problema dell’arresto
Primo esempio di problema indecidibile, cioè che non ammette alcun algoritmo di risoluzione. Il problema dell’arresto nacque nel 1936, sulla base di studi sugli insiemi infiniti della fine del XIX sec. La sua enunciazione è dovuta ad Alan Turing ed è basata sulla formalizzazione dei modelli primitivi di calcolo sviluppati all’inizio di quel secolo, tra cui la macchina dello stesso autore. In modo informale il problema può essere così formulato: presi arbitrariamente un algoritmo A e un dato D, stabilire se la computazione A(D) termina in un numero finito di passi. Turing dimostrò che non può esistere alcun algoritmo ARR che stabilisca in tempo finito se la computazione A(D) si arresta anch’essa in tempo finito (ARR(A,D)=true), o non si arresta mai (ARR(A, D)=false). In particolare ARR non può semplicemente simulare la computazione A(D), perché se questa non termina, neanche la simulazione termina. L’argomentazione di Turing si basa sulla rappresentazione di algoritmi e dati come sequenze di simboli dello stesso alfabeto, per cui è lecito usare la sequenza corrispondente a un algoritmo A come dato per un altro algoritmo o per sé stesso: calcolare cioè A(A). Dunque l’eventuale algoritmo ARR potrebbe essere applicato ad A(A) e avremmo:
ARR(A, A)=true se A(A) termina;
ARR(A, A)=false se A(A) non termina.
L’esistenza di ARR consentirebbe di definire il seguente algoritmo NEW che invoca ARR al suo interno:
NEW(A):
p=true;
while (p=true) do p=ARR (A, A);
la cui computazione termina se e solo se ARR(A, A) ha valore false ovvero, per la relazione [2]:
[3] NEW(A) termina se e solo se A(A) non termina.
Se NEW esiste, è lecito eseguire la computazione NEW(NEW). Ma sostituendo NEW ad A nella relazione [3] dovremmo concludere che NEW(NEW) termina se e soltanto se NEW(NEW) non termina. La contraddizione mostra che NEW non esiste, e poiché l’unico motivo di debolezza nella costruzione di questo algoritmo è l’ammissione che ARR esista, concludiamo che ARR non esiste.