Algoritmo, computabilità, macchina di Turing e nascita dell’informatica

MEDICINA ONLINE ALAN TURING SCIENZIATO LOGICO ANALISTA CRITTOGRAFO QUANTISTICA FISICA INFORMATICA ROBOTICA INTELLIGENZA ARTIFICIALE THE IMITATION GAME

Alan Mathison Turing negli anni ’50

Algoritmo e computabilità

Il termine “algoritmo” deriva dal nome del matematico arabo del IX secolo al-Khuwaritzmi. Per tutto il medioevo è stato usato per indicare procedure di calcolo standard da adottare per risolvere meccanicamente problemi matematici di tipo predefinito. È famoso, ad esempio, l’algoritmo euclideo delle divisioni successive, che permette di determinare il massimo comun divisore di due numeri naturali. In seguito l’uso del termine è stato esteso a indicare qualsiasi procedimento per risolvere meccanicamente, senza bisogno di inventiva, problemi, indipendentemente dal fatto che si tratti di problemi di calcolo o di altro genere. Intorno al 1930, ad opera di matematici e logici quali J.Herbrand, K. Godei, S.C. Kleene, E.L. Post, A.M. Turing, si è sviluppata la teoria generale degli algoritmi, che ha portato a precisare rigorosamente il concetto di computabilità e a stabilire con esattezza quali funzioni sono computabili, cioè risolvibili mediante algoritmi, e quali no.

La macchina di Turing

Allo scopo di disporre di un criterio per verificare se un problema è computabile o non, il matematico inglese Alan Mathison Turing (Londra, 23 giugno 1912 – Manchester, 7 giugno 1954) ideò una macchina in grado di eseguire qualsiasi algoritmo, che da lui prende il nome di macchina di Turing. Tale strumento è stato introdotto nel 1936 da Alan Turing per dare risposta all’Entscheidungsproblem (problema di decisione) proposto da Hilbert nel suo programma di fondazione formalista della matematica. Si tratta di un prototipo ideale, che di fatto non è stato costruito, ma che ha valore teorico. La macchina di Turing è piuttosto semplice. È fatta di una testina e di un nastro scorrevole, che si suppone infinito, diviso in caselle, in ognuna delle quali può figurare il numero 1 o il numero O. La macchina può compiere tre operazioni:

spostare il nastro a destra o a sinistra di una casella alla volta;
leggere il numero nella casella;
sostituire il numero nella casella con l’altro.

Una macchina così semplice è in grado teoricamente di fare tutte le cose che può fare qualsiasi altra macchina. In uno specifico compito un’altra macchina potrà essere più rapida, ma la macchina di Turing arriva lo stesso al risultato: è in parole povere un calcolatore universale, che assomma in sé le funzioni di tutti i calcolatori esistenti. Per sapere se un problema è computabile, non c’è quindi più bisogno di provare con tutte le macchine esistenti: basta la macchina di Turing, che rappresenta tutte le altre. Creiamo un algoritmo per risolvere il problema; se la macchina di Turing esegue con successo l’algoritmo, il problema è computabile. La macchina di Turing non è probabilmente così interessante da un punto di vista tecnico, ma ha contribuito in modo decisivo a rendere più chiaro il concetto di computabilità, facendolo uscire dal vago e rendendolo operativo.

Il padre dell’informatica

Il lavoro di Turing ebbe vasta influenza sulla nascita della disciplina dell’informatica, grazie alla sua formalizzazione dei concetti di algoritmo e calcolo mediante la sua omonima macchina, che a sua volta costituì un significativo passo avanti nell’evoluzione verso il moderno computer, tanto che Turing è solitamente considerato non solo il padre dell’informatica, ma anche dell’intelligenza artificiale, da lui teorizzate con vari decenni di anticipo rispetto ad altri matematici, già negli anni trenta del ‘900. Se ora state leggendo queste parole su un portatile o su uno smartphone, è anche grazie ad Alan Turing.

The Imitation Game

Oltre ad essere un brillante matematico, Turing fu anche uno dei più brillanti crittoanalisti che operarono nel Regno Unito durante la Seconda Guerra Mondiale, e lavorò – assieme ad altre menti brillanti – al centro di analisi di Bletchley Park alla decriptazione dei i messaggi scambiati da diplomatici e militari nazisti. Turing ideò una serie di tecniche innovative per violare i cifrari tedeschi, incluso l’utilizzo di una macchina elettromeccanica (chiamata “Bomba”) in grado di decodificare codici creati dalla macchina crittografica Enigma. Questa storia è narrata nel bel film del 2014 “The Imitation Game“, per la regia di Morten Tyldum, con Benedict Cumberbatch nel ruolo di Turing.

La triste fine del genio

Purtroppo il geniale matematico inglese morì suicida a soli 41 anni, in seguito alle persecuzioni subite da parte delle autorità e dell’ostracismo sociale a causa della sua omosessualità, all’epoca considerato un reato. Nel 52, infatti, fu condannato per omosessualità e costretto a scegliere tra una pena a due anni di carcere o la castrazione chimica mediante assunzione di estrogeni. Lo scienziato optò per la seconda alternativa, ma le terapie mediche e la vergogna sociale lo condussero alla depressione che, secondo molti, lo condusse al suicidio, il 7 giugno 1954.