Amarcord Turing

Cento anni fa nasceva l'ideatore della Macchina di Turing che, nonostante la sua semplicità, è tuttora il computer più potente al mondo.

Alan Turing, chi era costui? Beh, probabilmente agli utenti dell'informatica di oggi (fatta non tanto solo di click, ma di tag, di tweet e di post) questo personaggio dirà ben poco. Ma chi ha masticato computer non solo sotto il profilo pratico ma anche sotto quello teorico, non può che togliersi il cappello davanti a cotanto genio.

Ricorre proprio oggi, 23 giugno 2012, il centenario della sua nascita. Non visse, purtroppo, a lungo: all'età di soli 41 anni fu ritrovato senza vita, suicida, nel suo letto. Accanto a lui una mela morsicata che pare ispirò - esistono varie teorie... - i giovanissimi Steves (Jobs e Wozniak) nella scelta del logo della neonata Apple, sul finire degli anni settanta. Che storie... :-)

Per chi non lo sapesse (immagino, o per meglio dire spero, ben pochi dei miei lettori) la macchina ipotizzata e studiata negli anni trenta da Alan Turing - si tratta, badabèn, di un modello teorico! - è SEMPLICEMENTE il computer più potente al mondo, nonostante sia in grado di effettuare solo semplicissime operazioni (leggere, scrivere, spostarsi a destra o a sinistra sul nastro e cambiare il suo stato interno) su altrettanto semplici dati: normali caratteri.

La Macchina di Turing - questo il suo nome - ha però dalla sua un paio di dettagli non secondari, che da una parte la fa essere il computer più potente (continuo a scriverlo tra virgolette, tra un po' dirò anche il perché) mai ipotizzato, dall'altra che non potrà mai essere realmente costruita (esercitazioni tecnologiche finite a parte, vedi qui) per la non certo trascurabile caratteristica di disporre di una memoria infinita: il suo nastro non ha mai fine. È proprio a questo che deve la sua potenza di calcolo altrettanto no-limits.

Chiaramente qui ragioniamo nell'ambito delle funzioni calcolabili da N (l'insieme dei numeri naturali) in N (idem), ma a ben guardare qualsiasi programma in esecuzione su qualsiasi computer (da Word al videogame spara-spara più esaltato che c'è, passando per qualsiasi altra applicazione grafica, musicale, ingegneristica, contabile, ecc. ecc. ecc.) può essere assimilata a una funzione matematica (calcolabile) da un numero naturale a un altro numero naturale. Qualche esempio? In Word il numero naturale in ingresso potrebbe essere semplicemente la sequenza di tutti i comandi impartiti sin dalla creazione dei documento (caratteri del testo digitati... inclusi!), e quelli in uscita il flusso - altrettanto numerico naturale - inviato alla stampante per una l'ottenimento di una copia su carta, o più semplicemente il file salvato su disco o inviato via mail al destinatario. Per un videogame, in ingresso la sequenza (certamente codificabile numericamente) dei comandi impartiti via joystick e in uscita il risultato, altrettanto assimilabile a un numerone, dei pixel generati a seguito delle nostre azioni.... videoludiche!

Velocità di esecuzione a parte (nella teoria della calcolabilità non contano certo i tempi d'esecuzione ma esclusivamente IL FATTO se una determinata cosa sia calcolabile o meno) per quanto possa sembrare strano, ripeto, qualsiasi programma eseguito è una funzione matematica da N in N (i computer trattano in ingresso e in uscita comunque solo ed esclusivamente numeri), e in quanto tale può essere calcolata dalla Macchina di Turing.

Almeno questa è la Tesi di Church, a tutt'oggi non contraddetta da alcuna dimostrazione. Per dirla alla Zia Wiki: la classe delle funzioni calcolabili coincide con quella delle funzioni calcolabili da una macchina di Turing; per dirla alla AdP: una funzione in generale calcolabile è sinonimo di calcolabile con una macchina di Turing o più semplicemente Turing-calcolabile. Come dire: le cose, secondo alcuni-per-non-dire-tutti, stanno teoricamente così e nessuno è riuscito ancora a dimostrare il contrario! Forse nemmeno ci prova...

Bello, no?!?

AdP