L'importanza duratura di Turing

Quando Alan Turing nacque 100 anni fa, il 23 giugno 1912, un computer non era una cosa: era una persona. I computer, la maggior parte dei quali erano donne, sono stati assunti per eseguire calcoli ripetitivi per ore e ore. La pratica risale al 1750, quando Alexis-Claude Clairaut reclutò due colleghi astronomi per aiutarlo a tracciare l'orbita della cometa di Halley. L'approccio di Clairaut è stato quello di suddividere il tempo in segmenti e, utilizzando le leggi di Newton, calcolare i cambiamenti nella posizione della cometa al passaggio di Giove e Saturno. La squadra ha lavorato per cinque mesi, ripetendo il processo ancora e ancora mentre tracciavano lentamente il corso dei corpi celesti.

Oggi chiamiamo questo processo simulazione dinamica; I contemporanei di Clairaut lo chiamavano un abominio. Desideravano una scienza delle leggi fondamentali e delle belle equazioni, non tabelle e tavole di numeri. Tuttavia, il suo team ha fatto una previsione accurata del perielio della cometa di Halley. Nel corso del secolo e mezzo successivo, i metodi computazionali arrivarono a dominare l'astronomia e l'ingegneria.

Questa storia faceva parte del nostro numero di marzo 2012

• Vedi il resto del problema
• sottoscrivi

Quando Turing entrò al King's College nel 1931, i computer umani erano stati impiegati per un'ampia varietà di scopi, e spesso erano assistiti da macchine calcolatrici. Le schede perforate venivano utilizzate per controllare i telai e tabulare i risultati del censimento americano. Le chiamate telefoniche sono state commutate utilizzando numeri composti su uno squillo e interpretati da una serie di relè a 10 passi. I registratori di cassa erano onnipresenti. Un milionario non era solo una persona molto ricca: era anche un calcolatore meccanico in grado di moltiplicare e dividere con sorprendente velocità.

Tutte queste macchine erano fondamentalmente limitate. Non erano solo più lenti, meno affidabili e drammaticamente più poveri di memoria rispetto ai computer di oggi. Fondamentalmente, le macchine calcolatrici e commutatrici degli anni '30 - e quelle che sarebbero state introdotte per molti anni a venire - furono costruite ciascuna per uno scopo specifico. Alcune macchine potevano eseguire manipolazioni con la matematica, alcune potevano persino seguire una sequenza variabile di istruzioni, ma ogni macchina aveva un repertorio finito di operazioni utili. Le macchine non erano di uso generale. Loro non erano programmabile.

Cose recensite

• Cattedrale di Turing: le origini dell'universo digitale

  George Dyson
  Pantheon Libri, 2012

• Quando i computer erano umani

  David Alan Grier
  Princeton University Press, 2005

  
  
  

• Alan Turing: L'enigma

  Andrew Hodges
  Simon & Schuster, 1983

Nel frattempo, la matematica era nei guai.

All'inizio degli anni '20 il grande matematico tedesco David Hilbert aveva proposto di formalizzare tutta la matematica in termini di un piccolo numero di assiomi e di una serie di dimostrazioni coerenti. Hilbert ha immaginato una tecnica che potrebbe essere utilizzata per convalidare affermazioni matematiche arbitrarie: prendere un'affermazione come x + y = 3 e x - y = 3 e determinare se fosse vera o falsa. Questa tecnica non farebbe affidamento sull'intuizione o sull'ispirazione da parte del matematico; doveva essere ripetibile, insegnabile e abbastanza semplice da essere seguito da un computer (nel senso di Hilbert della parola). Un tale sistema di dimostrazione sarebbe davvero qualcosa di potente, poiché molti aspetti del mondo fisico possono essere facilmente descritti come un insieme di equazioni. Se si fosse in grado di applicare una procedura ripetibile per scoprire se un'affermazione matematica è vera o falsa, allora le verità fondamentali sulla fisica, la chimica, la biologia - persino la società umana - sarebbero scoperte non attraverso esperimenti in laboratorio ma dai matematici alla lavagna .

Ma nel 1931, un logico austriaco di nome Kurt Gödel presentò il suo devastante teorema di incompletezza. Ha mostrato che per ogni utile sistema di matematica, è possibile creare affermazioni che sono vere ma non possono essere dimostrate. Poi è arrivato Turing, che ha guidato la puntata finale attraverso il progetto di Hilbert e, così facendo, ha tracciato la strada per il futuro dell'informatica.

Come ha mostrato Turing, il problema non è solo che alcune affermazioni matematiche non sono dimostrabili; infatti, nessun metodo può essere escogitato che possa determinare in tutti i casi se una data affermazione è dimostrabile o meno. Cioè, qualsiasi affermazione sulla lavagna potrebbe essere vera, potrebbe essere falsa, potrebbe essere indimostrabile... ed è spesso impossibile determinare quale. La matematica era fondamentalmente limitata, non dalla mente umana ma dalla natura stessa della matematica.

La cosa brillante e sorprendente è stata il modo in cui Turing ha svolto la sua dimostrazione. Ha inventato un formalismo logico che descriveva come un computer umano, a cui fosse stato insegnato a seguire un insieme complesso di operazioni matematiche, le avrebbe effettivamente eseguite. Turing non capiva come funzionasse la memoria umana, quindi la modellò come un lungo nastro che poteva muoversi avanti e indietro e sul quale i simboli potevano essere scritti, cancellati e letti. Non sapeva come funzionasse l'apprendimento umano, quindi l'ha modellato come un insieme di regole che l'essere umano avrebbe seguito a seconda del simbolo attualmente davanti a lei e di una sorta di stato mentale interno. Turing descrisse il processo in modo così preciso che alla fine non era nemmeno necessario un computer umano per eseguirlo: invece poteva farlo una macchina. Turing chiamò questa entità teorica macchina automatica o a-machine; oggi la chiamiamo macchina di Turing.

In un articolo del 1936, Turing dimostrò che l'a-machine poteva risolvere qualsiasi problema di calcolo che potesse essere descritto come una sequenza di passaggi matematici. Inoltre, ha mostrato che una macchina a può simulare un'altra macchina a. Ciò che dava alla macchina a questo potere era che il suo nastro poteva memorizzare sia dati che istruzioni. Nelle parole dello storico della scienza George Dyson, il nastro conteneva entrambi i numeri che significare cose e numeri che fare cose.

Il lavoro di Turing è stato trasformativo. Ha chiarito ai progettisti dei primi computer elettronici che le macchine calcolatrici non avevano bisogno di un enorme inventario di istruzioni o operazioni fantasiose: tutto ciò di cui avevano bisogno erano alcuni registri sempre disponibili (lo stato mentale) e un magazzino di memoria che potesse contenere sia i dati che il codice. I progettisti potevano procedere con la certezza matematica che le macchine che stavano costruendo sarebbero state in grado di risolvere qualsiasi problema programmato dagli umani.

Queste intuizioni hanno fornito la formulazione matematica per i computer digitali di oggi, sebbene sia stato John von Neumann a riprendere le idee di Turing ea cui è attribuito il design delle macchine. Il progetto di von Neumann aveva un nucleo centrale che recuperava sia le istruzioni che i dati dalla memoria, eseguiva operazioni matematiche, memorizzava i risultati e quindi ripeteva. La macchina potrebbe anche interrogare il contenuto di più posizioni in memoria, se necessario. Quella che oggi chiamiamo architettura von Neumann è il cuore di ogni microprocessore e mainframe del pianeta. È notevolmente più efficiente dell'a-machine, ma matematicamente è lo stesso.

Per inciso, questa caratteristica essenziale dei computer aiuta a spiegare perché la sicurezza informatica è uno dei problemi più preoccupanti dell'era moderna. Per prima cosa, Turing ha mostrato che tutte le a-macchine sono equivalenti l'una all'altra, che è ciò che rende possibile a un utente malintenzionato di prendere il controllo di un computer bersaglio e fargli eseguire un programma a scelta dell'attaccante. Inoltre, poiché non è sempre possibile discernere ciò che può essere dimostrato, una macchina di Turing non può, non importa quanta memoria, velocità o tempo disponga, valutare il progetto di un'altra macchina di Turing e determinare in modo affidabile se la seconda macchina, dopo aver ricevuto qualche input, finirà mai i suoi calcoli. Ciò rende impossibile il rilevamento perfetto dei virus. È impossibile per un programma valutare un software mai visto prima e determinare se è dannoso senza eseguirlo effettivamente. Il programma potrebbe essere benigno. Oppure può funzionare per anni prima di cancellare i file dell'utente. Non c'è modo di saperlo con certezza senza eseguire il programma.

Nel 1938 Turing iniziò a lavorare con il governo britannico e alla fine aiutò a progettare una serie di macchine per decifrare i codici usati dai tedeschi nella seconda guerra mondiale. La migliore fonte per quella storia è la biografia di Andrew Hodges Alan Turing: L'enigma. Sfortunatamente, alcuni dettagli sul lavoro di Turing in tempo di guerra non sono stati declassificati fino al 2000, 17 anni dopo il libro di Hodges (e quasi 50 anni dopo che Turing si è suicidato). Di conseguenza, i suoi contributi completi non sono stati ben raccontati.

Molte storie dell'informatica danno l'impressione che sia stato un insieme diretto di decisioni ingegneristiche utilizzare schede perforate, poi relè, poi tubi e infine transistor per costruire macchine informatiche. Ma non lo era. Le macchine per uso generale richiedevano l'intuizione fondamentale di Turing secondo cui dati e codice possono essere rappresentati allo stesso modo. E tieni presente che tutti i computer di oggi sono stati sviluppati con l'aiuto di computer più lenti, che a loro volta sono stati progettati con computer ancora più lenti. Se Turing non avesse fatto la sua scoperta quando lo ha fatto, la rivoluzione dei computer avrebbe potuto essere ritardata di decenni.

BAMBINI il redattore collaboratore Simson L. Garfinkel è professore associato di Informatica presso la Naval Postgraduate School. Le sue opinioni non rappresentano la politica ufficiale del governo degli Stati Uniti o del Dipartimento della Difesa.

nascondere