La versione più famosa del problema fu ipotizzata e risolta da Alan Turing, nel 1936.
Prima di spiegare per bene cosa sia l'halting problem, devo però introdurre al lettore qualche concetto essenziale.
Innanzitutto, cosa si intende per macchina di Turing (mdT d'ora innanzi)? Essa è una macchina ideale in grado di eseguire algoritmi. Congetturata da Turing, essa prevede, tecnicamente, l'utilizzo di un nastro di ingresso da cui si legge, k nastri di memoria, tradizionalmente considerati di lunghezza infinita (è un modello astratto, appunto), e un nastro di uscita. La “testina” che scorre il nastro di input, così come le testine dei nastri di memoria, ha tre movimenti possibili: S(tand), L(eft), R(ight). Sul nastro di output, sono possibili invece solamente i movimenti S e R (L sovrascriverebbe un simbolo di output, il che sarebbe stupido e inutile).
La mdT risulta importantissima poiché secondo la Tesi di Church essa è il modello astratto di riferimento di macchina con maggiore potenziale espressivo, ossia non è possibile pensare un algoritmo che non sia implementabile da una macchina di Turing.
Detto in altra maniera, citando wikipedia:
L'importanza della MdT deriva dal fatto che permette di compiere tutte le elaborazioni effettuate mediante le macchine (elettroniche o meccaniche) apparse nella storia dell'umanità, incluse le elaborazioni che oggi si eseguono con le tecnologie più avanzate e gli odierni computer, e perfino le dimostrazioni matematiche che l'umanità ha raccolto nel corso della sua storia, diciamo a partire da Euclide.Bene, adesso invece prepariamoci a affrontare un ulteriore concetto: cosa si intenda per decidibilità di un problema o computabilità di una funzione.
Innanzitutto occorre notare che i problemi decidibili sono solo una minima parte dei problemi definibili, dove per definibile si intende un qualsiasi problema che possa essere formalizzato.
In pratica, un problema è decidibile (e una funzione è computabile) se e solo se esiste una mdT che lo risolva. Spesso non ci interessa nemmeno sapere la soluzione o conoscere nel dettaglio il funzionamento di quella mdT, ci basta sapere che essa esiste. Ad esempio, il problema di stabilire se nell'universo ci siano 10^999 molecole, è un problema decidibile, anche se non ne conosciamo la risposta; infatti sappiamo che esiste una mdT che contando una a una le molecole, prima o poi ci dirà se avessimo ragione o meno.
Siamo giunti al fulcro della discussione: il problema dell'arresto. Esso si domanda se, data una mdT (dato un algoritmo), e un input finito, sia sempre possibile determinare se la mdT termini oppure continui la sua esecuzione all'infinito (vada "in loop") con ingresso quel dato input.
Il problema è indecidibile; e lo si dimostra ragionando per assurdo. La dimostrazione è davvero stuzzichevole, spero di riuscire a renderne evidente la genialità!
Immaginiamo esista una mdT H tale che, ricevuto in ingresso l'algoritmo a e un input finito x su cui calcolarlo, ci ritorni TRUE se la macchina termina la computazione, o FALSE se invece va in loop.
H(a, x): if (loop) then return false; else return true;
Possiamo pensare di passare ad H, come input finito, a stesso! Già, poiché per la nostra mdT esso è solo una sequenza indistinta di simboli. Staremmo quindi calcolando H(a, a), chiedendoci se l'algoritmo a termini o meno con input a.Ora inventiamoci una ulteriore mdT K che vada in loop se e solo se H(a, a) restituisce TRUE, altrimenti ritorna FALSE.
K(a): if H(a, a) then loop; else return false;
Proviamo infine a passare come input a K, K stesso, calcolando K(K). Dunque se H(K, K) termina, K(K) va in loop; altrimenti restituisce FALSE.
K(K): if H(K, K) then loop; else return false;
Ma H(K, K) dovrebbe proprio dirci se K(K) termina o meno!Siamo giunti alla contraddizione: infatti questo algoritmo termina solo se l'algoritmo K, con input K, non termina. Ossia K(K) termina se e solo se K(K) non termina.
Se qualche carissimo lettore avesse superato lo scoglio della dimostrazione sano e salvo, e si stesse chiedendo “e quindi?”, vorrei puntualizzare l'importanza di questa dimostrazione: immaginate se fosse vero il contrario, ossia se fosse possibile conoscere a priori se un determinato algoritmo termini o meno dato un input. Penso sia evidente lo straordinario potenziale che si creerebbe in una situazione simile: sapremmo con certezza se quel programmino che macina da 20 giorni si sia bloccato o se invece stia ancora computando. Potremmo risolvere congetture come quella di Goldbach, tuttora aperte.
Insomma avremmo tra le mani uno strumento incommensurabilmente potente; ma, per fortuna o purtroppo, esso ci è negato. Insomma, accontentiamoci di cercare di capire se il nostro algoritmo sia andato in loop o meno leggendo attentamente il codice, invece di poterci affidare a una comoda mdT che risolva il problema dell'arresto!
