La macchina di Turing

Salve a tutti e bentornati nella rubrica di scienza e tecnologia, io sono sempre GCP e oggi trattiamo un argomento fondamentale per l’informatica, caro a tutti gli studiosi, e rintracciabile oggi nei nostri computer super moderni! Sto parlando della famosa (forse un po di più dopo oggi): macchina di Turing.

Oggi scopriremo in modo semplice come funziona nel dettaglio, e perché è così importante per l'informatica. Darò solo un'infarinatura generale necessaria sul contesto e sul personaggio di Turing, anche per spiegare meglio il funzionamento della macchina. 

Turing: l’informatico che svoltò il corso della WWII

Durante la seconda guerra mondiale, una delle armi letali dei nazisti, oltre alla guerra lampo, era sicuramente la loro capacità di rendersi invisibili, criptando i propri messaggi. Il dispositivo usato dall’ esercito per criptare e decriptare i suoi messaggi era la celeberrima macchina: Enigma. Il governo inglese ci aveva visto  lungo quando decise che sarebbe stata una mossa più che vincente provare a decriptarla. L’uomo che il governo scelse per questo lavoro fu Alan Mathison Turing, insieme ad altri matematici e crittografi. Il governo chiamò lui perché anni prima nel ‘35 aveva scioccato la comunità matematica con la sua idea teorica per la risoluzione di un problema considerato impossibile: proprio servendosi dell'applicazione della logica della macchina di Turing. In questo articolo, però, non parleremo di come ha decifrato Enigma, con la sua “bomba”. Potrebbe essere argomento di un articolo futuro, intanto se vi interessa approfondire, vi rimando al bellissimo film con un incredibile Benedict Cumberbatch (nel ruolo di Turing): “The imitation game”. Uno dei miei film preferiti.

La macchina di Turing: il rullo infinito e la simpatica testina…

La macchina di Turing fu creata per risolvere il problema logico matematico più difficile dell’ epoca, a cui allora nessuno ancora aveva trovato soluzione. Turing propose una soluzione mai vista: voleva coinvolgere una macchina che si occupasse di elaborare il problema. Così nasce la Turing Machine. Immaginate un rullo di carta infinito  diviso in “celle” uguali. Ogni cella può contenere un dato proveniente da un insieme finito. Con questo intendo che le celle possono ospitare qualsiasi elemento di un gruppo finito, come ad esempio l’alfabeto, l’insieme N dei numeri o, esempio più comune, un gruppo composto solo dai numeri: 1 e 0, in alternativa possono anche rimanere vuote. Ora abbiamo un rullo di carta che ci dice delle cose e nasconde dei segreti, ma ancora non sappiamo interpretarlo…

Per risolvere qualunque cosa ci sia scritta sul nostro rullo, dovremmo trovare ed eseguire un algoritmo: ovvero una serie finita di step, che contengono determinate istruzioni, che possono portare alla risoluzione di più problemi (o meglio tutti i problemi di una stessa classe). Un esempio di algoritmo matematico che tutti (bene o male) conosciamo è la divisione in colonna. Qui entra in gioco il sistema automatico di Turing. Le varie istruzioni infatti sono eseguite da una testina totalmente meccanica in grado di leggere il nastro e scriverci dati, per l'appunto, secondo quello che dice l’algoritmo programmato in essa. La testina legge una casella e esegue il primo step dell’ algoritmo, quest'ultimo di solito le pone una condizione (tipo: se nella casella hai 0 fai…) e a seconda del risultato (si o no, vero o falso) le dice se spostarsi a destra o a sinistra oppure se cancellare il contenuto della casella e scrivere qualcos’altro. Una volta finito ciò, alla testina è dato l’ordine di passare al prossimo, o ad un determinato, step dell’ algoritmo. Quest'ultima operazione di transizione ta step si usa ancora oggi: ovvero il famoso go to scritto in corretta sintassi: goto, che si usa visual basic: un linguaggio di programmazione. Un esempio di istruzioni per il primo step di un algoritmo può essere 

step 1: 

{se (if) nella casella hai 0: cancella e vai allo step 2 

altrimenti (else) muoviti a destra e passa allo step tre}. In questo piccolo esempio dello step 1 di un algoritmo, la testina potrà accedere allo step 2 solo e solo se nella casella in esame troviamo uno zero, altrimenti dovrà passare allo step 3!

Questo è il modo in cui i nostri computer ancora oggi ragionano logicamente e eseguono complessi calcoli condizionali, infatti se un algoritmo oggi è molto stabile e efficiente, ottiene il titolo di Turing completo, ovvero che può essere riprodotto dalla macchina di Turing.  

Turing: il genio che si è spento troppo presto

Alan M. Turing, come abbiamo visto, ha dato un contributo fondamentale allo sviluppo della scienza informatica e il suo lavoro ci permette ogni giorno di usare i nostri calcolatori nel modo più efficiente. Dopo la decifrazione di Enigma, Turing continuò le sue ricerche in campo informatico, finché le autorità non scoprirono la sua omosessualità, per cui dovette essere castrato chimicamente (l’ altrenativa era la galera). Turing, dal dolore e dall’umiliazione provocatagli, cadde in depressione e si suicidò all'età di 42 anni, senza riuscire a portare a termine i suoi brillanti studi, che sarebbero risultati oggi in un maggiore progresso. Questa è la dimostrazione di come le convinzioni rozze e meschine che ci hanno portato via Turing non sono solo bigotte, ma anche controproducenti e talvolta ostacolanti del progresso e del progressismo. Spero che la brutta fine di questa storia, e tutto quello che ci siamo persi, sia una plateale dimostrazione di questo; di finali come quello di Turing, la storia ne è piena. Chissà quante cose ci siamo persi per via del bigottismo?!

Dal vostro GCP è tutto, ci vediamo al prossimo articolo, chissà: viaggeremo ancora nel tempo o resteremo ad ammirare e spiegare il progresso del presente? Fino ad allora, come sempre, restate curiosi! 

Saluti da GCP.

P.S.: dedicato alla mia amica Lilla che mi ha sopportato, ascoltandomi, nel mio tentativo di rendere il più semplice possibile questo argomento, un pochino complesso.