Alessandro Ciccarelli Università degli Sudi di Torino Corso di Laurea in Biotecnologie Industriali...
-
Upload
arrigo-monti -
Category
Documents
-
view
218 -
download
0
Transcript of Alessandro Ciccarelli Università degli Sudi di Torino Corso di Laurea in Biotecnologie Industriali...
Alessandro Ciccarelli Università degli Sudi di Torino
Corso di Laurea in Biotecnologie Industriali Facoltà di S.M.F.N
ALAN TURING :
LE INTUIZIONI MATEMATICHE
E BIOLOGICHE
Anno Accademico 2002-2003
VitaVita
FolkloreMatematicaSpionaggioInformaticaIntelligenza artificialeChimica
Date importantiDate importanti 1926-31: Sherborne School 1930: Morte dell’amico Christopher Morcom 1931-34: Laurea al King's College, Cambridge University 1932-35: Meccanica quantica , probabilità, logica 1912 (23 June): Nascita, Paddington, London 1935: Eletto fellow of King's College, Cambridge 1936: The Turing machine, computabilità, macchina universale 1936-38: Princeton University. Ph.D. Logica, algebra, teoria dei numeri 1938-39: Ritorno a Cambridge. Aprocio alla economica macchina tedesca Enigma 1939-40: La Bomba, macchina per decriptazione Enigma 1939-42: Decriptazione dell U-boat Enigma, salvando così la battaglia sull’Atlantico 1943-45: Capo Anglo-American crypto consulente.lavori elettronici 1945: National Physical Laboratory, London 1946: Computer e Software si affacciano sul mondo. 1947-48: programmazione di reti neurali e intelligenza artificiale. 1948: Manchester University 1949: Primo serio uso del computer 1950: The Turing Test per l’intelligenza delle macchine 1951: Eletto FRS. Teoria non lineare della crescita biologica 1952: arrestato come omosessuale, 1953-54: Incompleto lavoro su fisica e biologia 1954 (7 June): Morte (suicidio) con cianuro, Wilmslow, Cheshire.
Le Macchine di TuringLe Macchine di Turing
Le Macchine di TuringLe Macchine di Turing
Alan Turing propose nel 1936 l'idea di una “macchina immaginaria” che potesse effettuare ogni tipo di calcolo su numeri e simboli
Una Macchina di Turing (MdT) è definita da un insieme di regole che definiscono il comportamento della macchina su un nastro di input/output
Le Macchine di TuringLe Macchine di Turing
Nastro di lunghezza infinita diviso in celle; ogni cella contiene un simbolo oppure è vuota
… A B C ...
Le Macchine di TuringLe Macchine di Turing
Una MdT ha una testina che si sposta lungo il nastro leggendo, scrivendo e cancellando simboli nelle celle del nastro
La macchina analizza il nastro, una cella alla volta, iniziando da quella che contiene il simbolo più a sinistra nel nastro
Le Macchine di TuringLe Macchine di Turing
Ad ogni passo la macchina in accordo al suo stato interno ed al simbolo che sta leggendo (simbolo in lettura)
(1) cambia il suo stato interno e
(2) scrive un simbolo sul nastro e
(3) sposta eventualmente la testina di una posizione a destra o a sinistra
Le Macchine di TuringLe Macchine di Turing
Il comportamento di una MdT può essere programmato definendo un insieme di quintuple della forma:
(stato, simbolo letto, nuovo stato, simbolo scritto, direzione)
Esempi di quintuple:
(0, A, 1, B, -) (1, B, 0, B, >)(S, C, END, -, -) (1, -, 1, A, <)
Le Macchine di TuringLe Macchine di Turing
In un insieme di quituple che definisce una MdT ad ogni coppia
(stato, simbolo letto)
può essere associata al più una azione, ovvero al più una coppia
(nuovo stato, simbolo scritto, direzione)
Le Macchine di TuringLe Macchine di Turing
Esempio:
... ...A D B
3
(2, C, 3, D, -)(2, C, 3, D, -)
(3, D, 3, D, >)(3, D, 3, D, >)
A C B
2
A D B
3
A C B
2
A D B
3
Le Macchine di TuringLe Macchine di Turing
Come “calcola” una MdT?Inizialmente:
– Il nastro contiene una sequenza finita di simboli (celle non vuote) detta stringa di ingresso
– La MdT si trova nello stato iniziale 0 con la testina sul simbolo più a sinistra sul nastro
... ...A A B B
0
Le Macchine di TuringLe Macchine di Turing
Partendo da questa configurazione iniziale, la MdT effettua una serie di mosse seguendo rigorosamente quanto definito dall’insieme delle sue quintuple
Se la macchina raggiunge una configurazione tale che non esiste nessuna quintupla che associa una azione alla coppia (stato interno, simbolo letto) allora la MdT si ferma e termina la sua computazione
EsempioEsempio
Una MdT che scrive la sequenza di caratteri CIAO su un nastro vuoto
(0,-,1,C,>)(0,-,1,C,>)(1,-,2,I,>)(1,-,2,I,>)(2,-,3,A,>)(2,-,3,A,>)(3,-,4,O,>)(3,-,4,O,>)
... ...
0
C
1
I
2
A
3
O
4
EsempioEsempio
Una MdT che modifica una sequenza di A e di B scambiando ogni A con una B e viceversa
... ...
(0,A,0,B,>)(0,A,0,B,>)(0,B,0,A,>)(0,B,0,A,>)(0,-,F,-,-)(0,-,F,-,-)
0
A B AB AB AAAB
0
B A
0
B A AB
0
A B
F
B A B
Esempi pratici con “la Macchina di Turing “
Test di TuringTest di Turing “Se la persona non è in grado di distinguere quando sta interloquendo con una
macchina e quando con un operatore umano, allora la macchina è intelligente. “ Eliza, programma scritto nel 1966 da Joseph Weizenbaum
paziente: gli uomini sono tutti uguali computer: in che senso paziente: ci fregano sempre in qualche modo computer: puoi fare un esempio specifico paziente: un mio amico mi ha fatto venire qui computer: un tuo amico ti ha fatto venire qui paziente: dice che sono quasi sempre depressa computer: mi dispiace sentire che sei depressa paziente: è vero sono infelice computer: credi che venire qui ti aiuterà a non essere infelice paziente: ho bisogno di aiuto, questo è sicuro computer: cosa intendi come aiuto paziente: forse potrei riuscire ad andare d'accordo con mia madre computer: parlami di tua madre
•A.L.I.C.E
TEST con A.L.I.C.E. (Artificial Linguistic Internet
Computer Entity)
La macchina ENIGMALa macchina ENIGMA
La macchina EnigmaLa macchina Enigma
Componenti : * una tastiera per digitare il messaggio; * una tastiera con lettere lampeggianti per visualizzare i caratteri
(de)cifrati; * un dispositivo di scambio dei caratteri formato da tre ruote rotanti
(detti rotori ed un'unitá denominata riflettore; * un dispositivo, detto steckerboard per scambiare ulteriormente un
carattere non appena venga digitato e prima che venga mostrato sulla tastiera con le lettere lampeggianti;
* una batteria. The ENIGMA MACHINE on-line
macchina Enigma
Turing e processi bilogiciTuring e processi bilogici
Understanding biological complexity: lessons from the past.Weiss JN, Qu Z, Garfinkel A.FASEB J. 2003 Jan;17(1):1-6.
Turing e i processi biologiciTuring e i processi biologici
Computer a DNAComputer a DNA
Leonard Adleman = ha usato delle strisce di DNA come nastro in una macchina di Turing ed ha ottenuto operazioni di lettura e scrittura utilizzando strumenti prodotti con ingegneria genetica.
FINE