Alan Turing: il matematico che invento' il computer · il matematico che invento il computer Fellow...

Alan Turing (1912-1954)il matematico che invento il computer

Fellow della Royal Society, 29 marzo 1951

Questo file contiene i lucidi usati per la conferenza “Alan Turing: il matematico che invento il computer”, tenuta presso la Fondazione Universita di Mantova, il giorno 14 ottobre 2005, daG. Rosolini, DISI, Universita di Genova. Piuttosto che scorrere le pagine una dopo l’altra, e piu opportuno navigarle: facendo click sulla foto di Alan Turing si passa all’indice principale, dall’indiceprincipale si passa a ciascun argomento, facendo click sul puntino rosso in basso a destra si torna all’indice principale. Infine, le parole in blu sono collegate a foto.

The “computable” numbers may be describedbriefly as the real numbers whose expressions asa decimal are calculable by finite means.

Although the subject of this paper is ostensiblythe computable numbers, it is almost equally easyto define and investigate computable functions ofan integral variable or a real computable variable,computable predicates, and so forth.

The fundamental problems involved are, however,the same in each case, and I have chosen thecomputable numbers for explicit treatment asinvolving the least cumbrous technique.

I hope shortly to give an account of the relationsof the computable numbers, functions, and soforth to one another. This will include adevelopment of the theory of functions of a realvariable expressed in terms of computablenumbers.

According to my definition, a number iscomputable if its decimal part can be writtendown by a machine.

I numeri “calcolabili” possono essere descritti inbreve come quei numeri reali la cui espressionedecimale si puo determinare con strumenti finiti.

Sebbene l’argomento di questo lavoro sianoesplicitamente i numeri calcolabili, e quasialtrettanto facile definire e studiare le funzionicalcolabili di variabile intera o di variabile realecalcolabile, i predicati calcolabili, e cosı via.

I problemi fondamentali sono, comunque, glistessi in ogni caso, ed ho scelto i numericalcolabili per una trattazione esplicita percherichiedono la tecnica meno complicata.

Spero di trattare nel prossimo futuro le relazioniche intercorrono tra numeri calcolabili, funzioni evia di seguito. Questo includera lo sviluppo dellateoria delle funzioni di una variabile reale espressein termini dei numeri calcolabili.

Nella mia definizione, un numero e calcolabile sela sua parte decimale puo essere scritta da unamacchina. •

Computing machines

. . . For the present I shall only say that thejustification lies in the fact that the humanmemory is necessarily limited.

We may compare a man in the process ofcomputing a real number to a machine which isonly capable of a finite number of conditionsq1, q2, . . . , qR which will be called“m-configurations”.

The machine is supplied with a “tape”, (theanalogue of paper) running through it, anddivided into sections (called “squares”) eachcapable of bearing a “symbol”.

At any moment there is just one square, say ther-th, bearing the symbol S(r) which is “in themachine”.

We may call this square the “scanned square”.The symbol on the scanned square may be calledthe “scanned symbol”.

The “scanned symbol” is the only one of whichthe machine is, so to speak, “directly aware”.

Le macchine che calcolano

. . . Per il momento, diro soltanto che lagiustificazione sta nel fatto che la memoriaumana e necessariamente finita.

Possiamo paragonare un uomo nell’atto dicalcolare un numero reale a una macchina che ein grado di considerare soltanto un numero finitodi condizioni q1, q2, . . . , qR che chiameremo“configurazioni-macchina”.

La macchina e provvista di un “nastro”,(l’analogo della carta) che scorre attraverso diessa ed e diviso in sezioni (chiamate “quadrati”)ciascuna in grado di riportare un “simbolo”.

In ogni istante c’e esattamente un quadrato,diciamo l’r-esimo, che riporta il simbolo S(r)che e “all’interno della macchina”.

Possiamo chiamare questo il “quadrato inlettura”. Il simbolo nel quadrato in lettura puovenir chiamato il “simbolo in lettura”.

Il “simbolo in lettura” e l’unico di cui la macchinasia, per cosı dire, “a diretta conoscenza”. •

Computing machines

/o/o/o

qi�O�O�O

�O�O�O

J 1 0 1 0 1 0 1 I

S(r) = 1

Le macchine che calcolano

. . . Per il momento, diro soltanto che lagiustificazione sta nel fatto che la memoriaumana e necessariamente finita.

Possiamo paragonare un uomo nell’atto dicalcolare un numero reale a una macchina che ein grado di considerare soltanto un numero finitodi condizioni q1, q2, . . . , qR che chiameremo“configurazioni-macchina”.

La macchina e provvista di un “nastro”,(l’analogo della carta) che scorre attraverso diessa ed e diviso in sezioni (chiamate “quadrati”)ciascuna in grado di riportare un “simbolo”.

In ogni istante c’e esattamente un quadrato,diciamo l’r-esimo, che riporta il simbolo S(r)che e “all’interno della macchina”.

Possiamo chiamare questo il “quadrato inlettura”. Il simbolo nel quadrato in lettura puovenir chiamato il “simbolo in lettura”.

Il “simbolo in lettura” e l’unico di cui la macchinasia, per cosı dire, “a diretta conoscenza”. •

The possible behaviour of the machine at anymoment is determined by the m-configuration qn

and the scanned symbol S(r). This pairqn, S(r) will be called the “configuration”: thusthe configuration determines the possiblebehaviour of the machine.

In some of the configurations in which thescanned square is blank (i.e. bears no symbol)the machine writes down a new symbol on thescanned square: in other configurations it erasesthe scanned symbol.

The machine may also change the square whichis being scanned, but only by shifting it one placeto right or left.

In addition to any of these operations them-configuration may be changed.

Il comportamento possibile della macchina adogni istante e determinato dallaconfigurazione-macchina qn e dal simbolo inlettura S(r). Questa coppia qn, S(r) sarachiamata “configurazione”: in altre parole, laconfigurazione determina il comportamento dellamacchina.

In configurazioni in cui il quadrato in lettura enon scritto (cioe non riporta nessun simbolo) lamacchina puo scrivere un simbolo nel quadrato inlettura, in altre configurazioni puo cancellare ilsimbolo in lettura [o scriverne un altro].

La macchina puo anche cambiare il quadrato inlettura, ma soltanto spostandolo di un posto adestra o a sinistra.

In aggiunta a queste operazioni, laconfigurazione-macchina puo essere cambiata. •

/o/o/o

qn�O�O�O

�O�O�O

J 1 0 1 0 1 0 1 I





configurazione comportamentostato lettura

/o/o/o

qn�O�O�O

�O�O�O

J 1 0 0 1 0 1 I





configurazione comportamentostato lettura scrittura

/o/o/o

qn�O�O�O

�O�O�O

J 1 0 0 0 1 0 1 I






/o/o/o

qn�O�O�O

�O�O�O

J 1 0 0 0 1 0 1 I

/o/o/o

qn�O�O�O

�O�O�O

J 1 0 0 0 1 0 1 I






/o/o/o

qn�O�O�O

�O�O�O

J 1 0 0 0 1 0 1 I

�O�O�O

o/ o/ o/

qn�O�O�O

J 1 0 0 0 1 0 1 I





configurazione comportamentostato lettura scrittura movimento

/o/o/o

qn�O�O�O

�O�O�O

J 1 0 0 0 1 0 1 I

�O�O�O

o/ o/ o/

qn�O�O�O

J 1 0 0 0 1 0 1 I

�O�O�O

o/ o/ o/

qn �O�O�O

J 1 0 0 0 1 0 1 I





configurazione comportamentostato lettura scrittura movimento

/o/o/o

qn�O�O�O

�O�O�O

J 1 0 0 0 1 0 1 I

�O�O�O

o/ o/ o/

qn�O�O�O

J 1 0 0 0 1 0 1 I

�O�O�O

o/ o/ o/

qm �O�O�O

J 1 0 0 0 1 0 1 I





configurazione comportamentostato lettura scrittura movimento nuovo stato

Esempi

Una macchina per scrivere il numero . 010101010101010 . . .

configurazione comportamentostato lettura scrittura movimento nuovo statoq0 . . destra q0

q0 0 destra q1

q1 1 destra q0

Una macchina per scrivere il numero. 0101101110 1111︸︷︷︸

n

0 11111︸︷︷︸n+1

0 11 . . .︸︷︷︸n+2

configurazione comportamentostato lettura scrittura movimento nuovo statoq0 . . destra q0

q0 0 destra q1

q1 1 destra q2

q2 0 destra q3

q3 1 destra q4

q4 1 destra q5

q5 0 sinistra q6

q6 1 1 sinistra q6

q6 0 0 destra q7

q6 . 1 destra q10

q10 1 . destra q8

q10 0 0 destra q4

q4 1 1 destra q4

q7 1 . destra q8

q8 1 1 destra q8

q8 0 0 destra q8

q8 1 sinistra q11

q11 1 1 sinistra q11

q11 0 0 sinistra q6

Ogni macchina ha una descrizione standard come numero decimale.


Infatti,


Infatti, prendiamo ad esempio

q0 . . destra q0

q0 0 destra q1

q1 1 destra q0



q0 . . destra q0

q0 0 destra q1

q1 1 destra q0

La mettiamo in linea:q0 q. . dq0 q; q0 qxy0dq1 q; q1 qxy1dq0 q;



q0 . . destra q0

q0 0 destra q1

q1 1 destra q0


Riscriviamo i segni .

��O�O�O�O

xy

��O�O�O

q

��O�O�O

q

��O�O

d

��O�O

s

��O�O�O

;

��O�O�O

2 3 4 5 6 7 8



q0 . . destra q0

q0 0 destra q1

q1 1 destra q0



��O�O�O�O

xy

��O�O�O

q

��O�O�O

q

��O�O

d

��O�O

s

��O�O�O

;

��O�O�O

2 3 4 5 6 7 8

Otteniamo il numero405226405840530641584153164058



q0 . . destra q0

q0 0 destra q1

q1 1 destra q0



��O�O�O�O

xy

��O�O�O

q

��O�O�O

q

��O�O

d

��O�O

s

��O�O�O

;

��O�O�O

2 3 4 5 6 7 8

Otteniamo il numero405226405840530641584153164058

che possiamo scrivere in notazione binaria

1 . . . . . . . . . . . . 0︸︷︷︸98 cifre

The universal computing machine

It is possible to invent a single machine which canbe used to compute any computable sequence.

If this machine I is supplied with a tape on thebeginning of which is written the standarddescription of some computing machine M,then I will compute the same sequence as M.

. . . The behaviour of the computer at anymoment is determined by the symbols which heis observing and his “state of mind” at thatmoment.

. . . Every such operation consists of somechange of the physical system consisting of thecomputer and his tape.

. . . It is always possible for the computer tobreak off from his work, to go away and forget allabout it, and later to come back and go on withit. If he does this he must leave a note ofinstructions (written in some standard form)explaining how the work is to be continued. Thisnote is the counterpart of the “state of mind”.

La macchina di calcolo universale

E’ possibile inventare una singola macchina chepuo essere usata per calcolare qualunquesuccessione calcolabile.

Se si fornisce tale macchina I con un nastroall’inizio del quale sta scritto la descrizionestandard di una qualche macchina di calcolo M,allora I calcolera la stessa successione di M.

. . . In ogni istante, il comportamento di uncalcolatore e determinato dal simbolo che staosservando e dal suo “stato mentale” inquell’istante.

. . . Ogni tale operazione risulta in qualchemodifica del sistema fisico che consiste delcalcolatore e del suo nastro.

. . . E’ sempre possibile che il calcolatore vogliainterrompere il proprio lavoro, andarsene edimenticare tutto, per poi ritornare e continuarlo.Se fa questo, egli deve lasciare una nota diistruzioni (scritte in qualche modo standard) chespieghino come si deve continuare il lavoro. Talenota e la controparte dello “stato mentale”. •

Segreti

• Arrivo a Bletchley Park, 4 settembre 1939

• Progetto con G. Welchman della Bombe inglese, gennaio 1940

• Risultati quasi nulli per tutto il 1940

• Turing sviluppa tecniche probabilistiche per migliorare la ricerca delle Bombe, gennaio 1941

• Scoprono che le navi tedesche d’osservazione meteorologica sono munite di macchine Enigma,marzo-aprile 1941

• Cattura della Munchen, 7 maggio 1941

• Abbordarggio dell’U-110, 9 maggio 1941

• Traffico tedesco letto quotidianamente, dal giugno 1941

• Attacco alle navi rifornimento della Bismarck, giugno 1941

• Le decrittazioni diventano ULTRA SECRET, giugno 1941

• Churchill visita Bletchley Park, incontra Turing, luglio 1941

• Turing richiede personale direttamente a Churchill, 21 ottobre 1941

• Arrivo di nuovo personale a Bletchley Park, 18 novembre 1941

•

The Imitation Game

I propose to consider the question, “Canmachines think?” This should begin withdefinitions of the meaning of the terms“machine” and “think”.The definitions might be framed so as to reflectso far as possible the normal use of the words,but this attitude is dangerous.If the meaning of the words “machine” and“think” are to be found by examining how theyare commonly used it is difficult to escape theconclusion that the meaning and the answer tothe question, “Can machines think?” is to besought in a statistical survey such as a Galluppoll. But this is absurd.Instead of attempting such a definition I shallreplace the question by another, which is closelyrelated to it and is expressed in relativelyunambiguous words.The new form of the problem can be described interms of a game which we call the “imitationgame”.

Il gioco d’imitazione

Propongo di considerare la domanda: “Lemacchine possono pensare?” Questo dovrebbeiniziare con le definizioni del significato deitermini “macchina” e “pensare”.Le definizioni potrebbero essere studiate in mododa riflettere il piu possibile l’uso comune delleparole, ma un tale metodo e pericoloso.Se si deve trovare il significato delle parole“macchina” e “pensare” esaminando comevengono usati normalmente e difficile evitare laconclusione che il significato e la risposta alladomanda “Le macchine possono pensare?”verranno trovati mediante un sondaggiostatistico. Ma questo e assurdo.Invece di provare a dare una tale definizione,cambiero la domanda con un’altra, che estrettamente connessa a quella e che si esprimein termini relativamente non ambigui.Si puo descrivere la nuova forma del problema intermini di un gioco che chiamiamo il “giocod’imitazione”. •

It is played with three people, a man (A), awoman (B), and an interrogator (C) who may beof either sex. The interrogator stays in a roomapart front the other two. The object of thegame for the interrogator is to determine whichof the other two is the man and which is thewoman. He knows them by labels X and Y, andat the end of the game he says either “X is A andY is B” or “X is B and Y is A.” The interrogatoris allowed to put questions to A and B.

. . .It is A’s object in the game to try and causeC to make the wrong identification.

. . .The object of the game for the third player(B) is to help the interrogator. The best strategyfor her is probably to give truthful answers.

. . .We now ask the question, “What will happenwhen a machine takes the part of A in thisgame?” Will the interrogator decide wrongly asoften when the game is played like this as hedoes when the game is played between a manand a woman? These questions replace ouroriginal, “Can machines think?”

Si gioca in tre: un uomo (A), una donna (B) eun interrogatore (C) che puo essere di sessoqualunque. L’interrogatore e in una stanza,separato dagli altri due. Lo scopo del gioco perl’interrogatore e quello di determinare chi sial’uomo e chi la donna. Li conosce come X e Y ealla fine del gioco deve dire che “X e A e Y e B”oppure che “X e B e Y e A.” L’interrogatore puofare domande ad A e B.

. . .Lo scopo di A nel gioco e di far in modo cheC sbagli le identificazioni.

. . .Lo scopo del gioco del terzo giocatore (B) edi aiutare l’interrogatore. La migliore strategiaper lei e probabilmente di dare risposte vere.

. . .Ora poniamo la domanda: “Che cosasuccede quando una macchina prende il posto diA nel gioco?” Le identificazioni erratedell’interrogatore saranno tante quante quellefatte nel gioco con un uomo e una donna?Queste domande sostituiscono l’originale“Le macchine possono pensare?” •

• La macchina universaleOn Computable Numbers, with an application to the Entscheidungsproblem

Proc. Lond. Math. Soc. 42 pp.230-265 (1936-7)correzioni ibid. 43, pp.544-546 (1937)

http://www.abelard.org/turpap2/turpap2.htm

http://www-csli.stanford.edu/hp/Logic-software.html

• La decrittazione di EnigmaMathematical theory of ENIGMA machine

Bletchey Park, 1940http://www.turing.org.uk/

http://agn-www.informatik.uni-hamburg.de/

• Il gioco d’imitazioneComputing Machinery and Intelligence

Mind 49, pp.433-460 (1950)http://www.abelard.org/turpap/turpap.htm

http://www.loebner.net/Prizef/TuringArticle.html

Alan Turing: il matematico che invento' il computer · il matematico che invento il computer Fellow...

Documents

Transcript of Alan Turing: il matematico che invento' il computer · il matematico che invento il computer Fellow...