Problema della terminazione

Il problema di Halting è un problema di informatica. Il problema è guardare un programma per computer e scoprire se il programma funzionerà per sempre o no. Noi diciamo che un programma "risolve il problema dell'arresto" se può guardare qualsiasi altro programma e dire se quell'altro programma funzionerà per sempre o no.

Per esempio, un programma come questo:

mentre Vero: continua;

si ripeterà per sempre, ma il programma

mentre Falso: continua;

si ferma molto rapidamente.

C'è un programma che risolve il problema dell'arresto? A quanto pare no. Lo dimostriamo dimostrando che se c'è un programma che risolve il problema dell'arresto, allora succede qualcosa di impossibile. Quindi per il momento ci comporteremo come se ci fosse davvero un programma che risolve il problema dell'arresto. Qui, P è una funzione che valuterà la funzione F (chiamata con l'argomento I) e ritornerà vera se funziona per sempre e falsa altrimenti.

def P(F, I): se F(I) corre per sempre: ritorna Vero; altrimenti: ritorna Falso;

P può guardare qualsiasi programma e scoprire se funzionerà per sempre o no. Usiamo P per creare un nuovo programma che chiameremo Q. Quello che fa Q è guardare un altro programma e poi rispondere alla seguente domanda: "Se eseguiamo questo programma e gli facciamo vedere una copia di se stesso, funzionerà per sempre? Possiamo fare Q perché abbiamo P. Tutto quello che dobbiamo fare è dire a Q di creare un nuovo programma che è il vecchio programma guardando se stesso, e poi usare P per scoprire se il nuovo programma funziona per sempre o no.

def Q(F): ritorno P(F, F);

Ora facciamo un altro programma R. R. guarda un altro programma e chiede a Q la sua risposta su quel programma. Se Q risponde "sì, se eseguiamo questo programma e gli facciamo vedere una copia di se stesso funzionerà per sempre", allora R si ferma. Se Q risponde "no, se eseguiamo questo programma e gli facciamo vedere una copia di se stesso, non funzionerà per sempre", allora R entra in un ciclo infinito e funziona per sempre.

def R(F): se Q(F): ritorno; //terminare altro: mentre True: continuare; //loop forever

Ora guardiamo cosa succede se facciamo guardare a R una copia di se stessa. Due cose possono succedere: o si fermerà o scapperà per sempre.

Se eseguire R e fargli guardare una copia di se stesso non funziona per sempre, allora Q ha risposto "sì, se eseguiamo questo programma e gli facciamo guardare una copia di se stesso, funzionerà per sempre". Ma Q ha detto questo quando ha guardato R stesso. Quindi ciò che Q ha detto in realtà è: "sì, se eseguiamo R e gli facciamo vedere una copia di se stesso, funzionerà per sempre". Quindi: Se R che gira su una copia di se stesso non gira per sempre, allora gira per sempre. Questo è impossibile.

Se si esegue R e si fa guardare una copia di se stessi per sempre, allora Q ha risposto "no, se eseguiamo questo programma e lo facciamo guardare una copia di se stesso non funzionerà per sempre". Ma Q ha detto questo quando ha guardato R stesso. Quindi ciò che Q ha detto in realtà è: "no, se facciamo girare R e gli facciamo vedere una copia di se stesso non funzionerà per sempre". Quindi: Se R gira su una copia di se stesso funziona per sempre, allora non funzionerà per sempre. Anche questo è impossibile.

Qualunque cosa accada, ci troviamo in una situazione impossibile. Abbiamo fatto qualcosa di sbagliato e dobbiamo scoprire cosa. La maggior parte delle cose che abbiamo fatto non erano sbagliate. Non possiamo dire che "far guardare a un programma una copia di se stesso è sbagliato", o "guardare quello che ha detto un altro programma e poi entrare in un loop se ha detto una cosa, e fermarsi se ha detto un'altra cosa" è sbagliato. Non ha senso dire che non ci è permesso fare queste cose. L'unica cosa che abbiamo fatto che sembra sbagliata è che abbiamo fatto finta che un programma come P esista. E siccome questa è l'unica cosa che potrebbe essere sbagliata, e qualcosa deve essere sbagliato, questo è quanto. Questa è la prova che un programma come P non esiste. Non c'è nessun programma che risolva il problema dell'arresto.

Questa prova è stata trovata da Alan Turing nel 1936.

Domande e risposte

D: Che cos'è il problema di Halting?

R: Il problema di Halting è un problema di informatica che esamina un programma informatico e determina se il programma verrà eseguito per sempre o meno.

D: Come facciamo a sapere se un programma risolve il problema di Halting?

R: Diciamo che un programma 'risolve il problema dell'halting' se è in grado di guardare qualsiasi altro programma e dire se quell'altro programma funzionerà per sempre o no.

D: Esiste un modo per dimostrare che non esiste un programma di questo tipo?

R: Sì, dimostrando che se esistesse un programma del genere, accadrebbe qualcosa di impossibile. Questa prova è stata trovata da Alan Turing nel 1936.

D: Cosa fa P?

R: P è una funzione che valuta un'altra funzione F (chiamata con l'argomento I) e restituisce vero se funziona per sempre e falso altrimenti.

D: Cosa fa Q?

R: Q esamina un altro programma e poi risponde alla domanda se l'esecuzione di questo stesso programma su se stesso provocherà o meno un ciclo infinito. Lo fa utilizzando P per effettuare una valutazione della funzione F data.

D: Cosa fa R?

R: R guarda un altro programma e chiede a Q la sua risposta su quel particolare programma. Se Q risponde "sì, se eseguiamo questo programma e lo facciamo guardare una copia di se stesso, verrà eseguito per sempre", allora R si ferma; tuttavia, se Q risponde "no, se eseguiamo questo programma e lo facciamo guardare una copia di se stesso, non verrà eseguito per sempre", allora R entra in un ciclo infinito ed esegue per sempre.

D: Cosa succede quando si fa in modo che R guardi se stesso?

R: Possono accadere due cose: o R si ferma o viene eseguito per sempre, ma entrambi i risultati sono impossibili in base a ciò che è stato dimostrato sull'inesistenza di programmi come P, quindi qualcosa deve essere andato storto da qualche parte lungo il percorso che porta a far guardare R a se stesso.