Il problema della fermata

No, questo post non parla ne di autobus ne di treni (anche se di problemi con questo tipo di fermate ce ne sono molti).
Una sera della scorsa settimana mi sono ritrovato in mezzo ad una discussione “quasi” tecnica tra un paio di bravi ingegneri elettronici con tanta voglia di bere birra e chiacchierare. Uno dei due ad un certo punto sfodera con ammirevole sicurezza una rassicurante verità:

Qualsiasi cosa tu abbia bisogno di calcolare, un computer può farlo. Basta conoscere l’algoritmo giusto e avere abbastanza tempo.

La leggerezza della conversazione e il mezzo litro di De Koninck ormai in dirittura di arrivo hanno persuaso il matematico che c’è in me dal contraddire questa affermazione a prima vista scontata.
Non è così facile da intuire, ma esistono problemi che un computer non può risolvere. Risposte che non possono essere calcolate.

Questo fatto, dimostrato da personalità come Alan Turing e Alonso Church nei primi decenni del Novecento, assieme al teorema di incompletezza di Gödel (che è, a ben vedere, una riformulazione dello stesso concetto), ha causato un terremoto nella matematica che, dagli anni ’30 in poi, non è stata più la stessa… Quello che più mi stupisce personalmente del risultato di Turing è la relativa facilità ed “eleganza” con cui sia possibile spiegarlo e comprenderlo, tanto che proverò a riassumerlo nelle poche righe di un articolo del mio blog.

Cominciamo mettendo in chiaro di cosa stiamo parlando. Cosa intendiamo per “risolvere un problema?”. Per noi ogni problema di calcolo è rappresentato da una funzione che per ogni valore in input assume un preciso valore di output. Risolvere il problema significa calcolare il valore della funzione a partire da un preciso input. Per fare ciò è necessario eseguire un algoritmo, ovvero una serie finita di istruzioni non ambigue che portano in un tempo finito al calcolo del risultato. La clausola “tempo finito” non è scontata. In effetti alcuni algoritmi, su alcuni input, possono non terminare mai, per esempio entrando in un ciclo infinito. In questo caso si dice che l’algoritmo diverge.

La prima cosa di cui dobbiamo renderci conto è che l’insieme di tutti gli infiniti possibili algoritmi è numerabile, ovvero ogni algoritmo è associabile biunivocamente ad un numero naturale. Dimostrare formalmente questo fatto è lungo e tedioso, ma possiamo rendercene conto pensando a come rappresentiamo nei calcolatori un algoritmo scritto in un qualche linguaggio di programmazione. Un file di testo contenente il codice sorgente dell’algoritmo cos’è se non un grosso numero naturale codificato in forma binaria?

Una volta capito ciò, un primo indizio del fatto che esistano problemi irrisolvibili, ovvero per i quali non esiste un algoritmo adatto, ci viene dalla teoria degli insiemi. Sappiamo infatti che l’insieme delle funzioni ha la cardinalità del continuo e quindi non è numerabile. In altre parole, non c’è una corrispondenza biunivoca tra problemi e algoritmi: i problemi possibili sono molti di più.
Questo però, non è un risultato facile da ottenere senza scrivere pagine e pagine su teoria degli insiemi e numeri cardinali, mentre io vi avevo promesso un ragionamento semplice e facilmente spiegabile. Inoltre, ragionare in questo modo non ci aiuta affatto a capire quali sono effettivamente i problemi che possiamo risolvere e quali no.

Per capire meglio la questione ci concentriamo ora su un problema specifico, il cosiddetto problema della fermata o Halting problem per gli amici anglosassoni. Si può formulare così: dato un algoritmo P e un input I, l’algoritmo termina con una risposta? Più precisamente vogliamo calcolare la seguente funzione:

Nota per i pignoli
Detta così non sembra una funzione . In realtà lo è, perché l’algoritmo P è, come abbiamo visto, codificabile da un numero naturale, e la coppia (P,I) è a sua volta codificabile da un numero naturale con la classica formula di Cantor , che fornisce una biezione tra numeri naturali e coppie di numeri naturali. Le risposte SI e NO ovviamente possono essere codificate con 1 e 0, 42 e 69, o qualsiasi cosa…
Fine della nota per i pignoli

Detto ciò, vediamo dove vogliamo arrivare. Vogliamo dimostrare che non esiste un algoritmo capace di calcolare la funzione H. Per farlo dovremmo fare un giro su noi stessi ottenendo una contraddizione. Se esistesse un tale algoritmo, allora potremmo scrivere un algoritmo con queste caratteristiche:

La funzione G, banale da implementare una volta ottenuto un algoritmo per H, restituisce NO se H riferisce che P(P) diverge, mentre diverge, ovvero entra in un ciclo infinito, in caso contrario. Quando scrivo P(P) intendo l’esecuzione dell’algoritmo P usando come input la codifica di se stesso.

Come si comportano le nostre due funzioni H e G messe assieme? Vediamo ad esempio cosa succede se valutiamo H(G,G). Che risposta possiamo ottenere? Entrambe sarebbero paradossali!

Infatti se ottenessimo SI, vorrebbe dire che G(G) termina, ma G(G) termina solo se H(G, G) risponde NO! Viceversa, se H(G, G) rispondesse NO vorrebbe dire che G(G) diverge. Ma G(G) diverge solo se H(G, G) risponde SI!

Ecco scovata la contraddizione. Guardando bene tutto il ragionamento ci accorgiamo che l’unica supposizione che abbiamo fatto è l’esistenza di un algoritmo per calcolare H, e abbiamo quindi dimostrato per assurdo che è impossibile.

Un problema non risolvibile come questo è detto indecidibile, e come questo ce ne sono infiniti altri. Il problema della fermata è stato il primo ad essere dimostrato tale da Turing, e riveste quindi una certa importanza storica, ma non solo. La dimostrazione di indecidibilità di moltissimi altri problemi si basa sulla riduzione di tali problemi all’halting problem. Se si dimostra che la soluzione di un problema risolverebbe anche l’halting problem, se ne deduce automaticamente che una tale soluzione non esiste.

In un certo senso è un bene che non abbia speso la serata in birreria a convincere i miei amici ingegneri di ciò che ho scritto in questo post. Una pagina web è senz’altro un posto migliore per questo genere di discorsi!

Per concludere in bellezza non posso non linkare questa geniale pagina, dove l’indecidibilità dell’halting problem è dimostrata… in quartine in rima!
Buona lettura