La Macchina di Turing
Durante il secondo Congresso internazionale di Matematica, svoltosi a Parigi l’8 Agosto del 1900, prese la parola il noto matematico tedesco David Hilbert. La parte più importante del suo discorso consisteva nell’esposizione all’elite matematica presente, di ventitrè problemi irrisolti a quella data. Hilbert lancia così la sfida: risolvere quei problemi. L’obiettivo del matematico era di fondare in modo sicuro la matematica, restituendole l’antica reputazione di verità incontestabile.
Nel 1928, al termine di una straordinaria carriera che lo aveva portato a essere un’autorità assoluta, Hilbert rinnovò la sfida che aveva lanciato quasi trenta anni prima quando aveva individuato ventitrè punti sui quali la matematica e i matematici avrebbero dovuto confrontarsi in futuro. Le questioni che rilanciò si concentrarono sugli aspetti fondamentali della matematica, soffermandosi su tre problemi ancora irrisolti: quello della coerenza, quello della completezza e quello della decidibilità o entscheidungsproblem.
I primi due furono risolti da Gödel. Il terzo da Alan Turing, alla sua maniera, inventando una macchina immaginaria. La domanda a cui dare una risposta era questa: esiste sempre un modo rigoroso di stabilire se un enunciato matematico sia vero o falso?
La Macchina di Turing permette di risolvere il problema della decisione attraverso la costruzione di un processo eseguito da una macchina astratta. La macchina, è costituita da un nastro di carta scorrevole diviso in caselle, un pennino e un apparecchio che ha la possibilità di compiere quattro operazioni: far scorrere il nastro in avanti, indietro, segnare una casella vuota con una x, oppure cancellarne una quando la incontra. Tutto qui. Turing intuì che una macchina così fatta, opportunamente istruita dal suo costruttore, ossia programmata, poteva effettuare una infinità di operazioni poiché era in grado di imparare, anzi, la macchina di Turing poteva risolvere qualsiasi calcolo che fosse calcolabile in maniera meccanica cioè in un numero finito di passi utilizzando un numero finito di simboli. In altre parole, la straordinaria intuizione di Turing fu che una macchina come quella che lui aveva immaginato poteva effettuare qualunque operazione fosse rappresentabile mediante un algoritmo. Insomma era una macchina universale. Il moderno concetto di computer come noi lo intendiamo era appena nato. La macchina di Turing poteva mettere delle crocette su un nastro di carta ma poteva anche giocare a scacchi, analizzare frasi e anche dare una risposta al quesito di Hilbert. Turing dimostrò che esistevano una classe di problemi matematici sulla quale la macchina non sarebbe stata in grado di dare una risposta; o meglio, che esistevano una categoria di affermazioni matematiche per le quali era impossibile sapere in anticipo se il calcolatore si sarebbe fermato per dare una risposta o avrebbe continuato per un tempo indefinito. Hilbert aveva ottenuto la sua risposta: se per il calcolatore, che poteva rappresentare il linguaggio della matematica, esistevano problemi “indecidibili”, allora la risposta al quesito era NO, non è possibile stabilire in maniera certa e meccanica la verità o la falsità di tutti gli enunciati matematici.
L’intuizione del giovane Turing rappresentò un traguardo importantissimo e il successo che ne derivò fu indiscusso e immediato,
Comments are closed