Roma II, 23 Novembre 2001
Universalità artificialità
computabilità
Per una storia del computer
Teresa Numerico
[email protected]
La macchina di Turing
Il modello della logica: universalità e
computabilità
Teoria della computabilità
• I teoremi di incompletezza di Gödel.
• Il fallimento del programma di Hilbert.
• La nozione di decidibilità come ultima
speranza del formalismo.
Un modello formale di calcolo
• Turing propone un modello formale
dell’attività di un essere umano che esegue
un calcolo di tipo algoritmico:
– un dispositivo astratto in grado di emulare la
funzione del calcolare, purché essa sia definita
attraverso una successione di operazioni
elementari.
MT universale
Turing (1939) definì così il risultato teorico:
“Si affermò che "una funzione è effettivamente
calcolabile se i suoi valori possono essere
trovati attraverso un processo puramente
meccanico". Possiamo prendere alla lettera
questa asserzione, intendendo per processo
puramente meccanico, un processo che può
essere portato a termine da una macchina. E'
possibile dare una descrizione matematica
delle strutture di queste macchine.”
Lo schema di una MT
|
|
Dispositivo di
lettura/scrittura/
spostamento sul nastro
secondo la tavola delle
istruzioni
La Macchina di Turing (MT)
• Un dispositivo astratto è una macchina nella
quale non vengono presi in considerazione i
vincoli necessari ad una sua realizzazione
pratica:
–
–
–
–
Dimensioni della memoria
Tempo di calcolo
Spazio di calcolo
Indipendenza dalla realizzazione fisica
• La MT si definisce per le relazioni funzionali
tra le sue parti, non per la sua realizzabilità.
Gli attributi della macchina
secondo la logica
• Infallibilità
• Prevedibilità
• Isolamento
• Illimitatezza delle risorse nel tempo e nello
spazio
• Formalismo del linguaggio
La macchina elettronica
Dal dispositivo a programma
memorizzato all’intelligenza artificiale
L’accelerazione della II GM
• La necessità di calcoli molto complessi era
particolarmente sentita in vari campi:
– La ricerca atomica: calcoli per misurare le
caratteristiche esatte dell’esplosione.
– La ricerca balistica: equazioni differenziali per
la misurazione delle tavole di lancio delle armi
a lunga gittata.
– La criptanalisi.
Due organismi centrali
• NDRC: National Defense Research Committee:
– L’organismo US voluto da Vannever Bush direttore
del OSRD (Office of Scientific Research and
Development) includeva i centri di ricerca militari e
civili.
• GC&CS: Government Code & Cypher School:
– L’organismo UK che si occupava di criptanalisi.
La Macchina di Von Neumann
Unità di controllo
Unità aritmetica
istruzioni
INPUT
MEMORIA
(Programmi e dati)
dati
OUTPUT
La II “macchina di Turing”
• Turing progettò ACE (Automated
Computing Engine) dal 1945.
• La programmazione era centrale +
dell’hardware.
• Si trattava di una macchina pensata per
manipolare informazione, non solo calcoli.
• Macchina come modello del cervello.
Un nuovo concetto di macchina
• La macchina pratica ha forti limiti spazio
temporali da considerare.
• La funzione dell’organizzazione della
conoscenza è centrale per un accesso rapido e
flessibile ai dati.
• E’ inutile e forse impossibile dimostrare
l’equivalenza tra macchine teoriche e pratiche.
• La somiglianza con la Macchina Universale:
entrambe sono basate sulla programmazione.
L’intelligenza artificiale
Macchine come sistemi
Organizzazioni complesse
La lettera di Turing a Ashby
• “Lavorando per l’ACE, sono più interessato
alla possibilità di produrre modelli
dell’azione della mente che alle applicazioni
pratiche dell’attività di calcolo. […] Sarebbe
possibile per la macchina sperimentare
variazioni del comportamento e accettarle o
rifiutarle. […] io sto sperando di fare in
modo che la macchina svolga proprio questi
compiti”.
La macchina non organizzata (MNO)
• “Se stiamo cercando di costruire una macchina
intelligente, e abbiamo deciso di seguire per quanto
è possibile il modello umano, dovremmo
incominciare con una macchina che abbia una
capacità minima di eseguire operazioni elaborate o
di reagire in modo disciplinato ai comandi (che
prendono la forma di interferenza). Nel seguito,
applicando un’interferenza adatta, simulando
l’educazione, dovremmo sperare di modificare la
macchina finché si possa fare affidamento sul suo
produrre azioni definite a certi comandi.”
Turing 1948
Caratteristiche della MNO
• Può commettere errori: non è completamente
affidabile.
• Può offrire risultati diversi allo stesso problema in
momenti diversi a causa degli effetti
dell’apprendimento.
• Il ruolo del mondo esterno è importante nel
processo di apprendimento.
• Acquisire conoscenza è un’attività sociale e
interattiva non un’attività solitaria da agente
onnisciente isolato, come nella logica.
La teoria degli automi di Von
Neumann
• La logica degli automi dovrà:
– Tener conto della lunghezza delle catene di
ragionamento.
– Trattare le operazioni logiche con procedimenti
che consentono eccezioni, con probabilità bassa,
ma non nulla.
– Creare una teoria la cui natura non sarà
rigidamente regolata dal “tutto o niente” come la
logica formale attuale.
L’autoriproduzione degli automi
• La logica degli automi è simile alla fisica teorica
in quella parte che manipola e misura
l’informazione.
• Gli organismi si riproducono senza diminuire di
complessità, anzi aumentandola.
• La complessità sotto un limite è degenerativa e
sopra si autoalimenta con l’autoorganizzazione.
I sistemi multiagente (MAS)
• Non c’è supervisione centrale centralizzata.
• Le decisioni si prendono a livello locale.
• Gli agenti non sono ristretti a un singolo
compito.
• Si pone il problema del coordinamento e
della comunicazione tra agenti.
Come sono gli agenti
• Flessibili
• Orientati agli obiettivi
• Autonomi
• Comunicativi
• Adattativi
• Si autoaccendono, interpretando i segnali
dell’ambiente
Cosa rappresenta il modello MAS
• L’interazione
• La negoziazione
• La comunicazione
• La cooperazione/competizione
• La dipendenza
• La fiducia
• La delega
Intelligenza collettiva e Web
• L’intelligenza collettiva si definisce come la l’abilità di
un gruppo di risolvere più problemi di quanti ne
risolvano i singoli membri, presi singolarmente.
• Gli ostacoli sono: i limiti cognitivi individuali e la
difficoltà di coordinamento.
• E’ forse possibile superare gli ostacoli creando una
mappa mentale collettiva condivisa definita come una
memoria esterna con accesso di lettura e scrittura,
rappresentazione di problemi, stati, azioni e
preferenze.
Francis Heylighen (2000) http://pespmc1.vub.ac.be/HEYL.html
Logica VS intelligenza sociale
• Il modello logico è:
– Prevedibile: non ha
nessuna creatività e non
impara
– Infallibile: non commette
mai errori
– Isolato: non interagisce
con l’esterno
– Illimitato: non considera i
limiti della realtà
• Il modello intelligenza
collettiva e distribuita è:
– Imprevedibile: è creativo,
complesso, dinamico,
apprende.
– Può commettere errori
– Sociale: c’è interazione
con l’ambiente e gli altri
agenti
– Tiene conto dei limiti
spazio temporali
Bibliografia
• Burattini, E. & Cordeschi, R. (2001) (a cura di) Intelligenza
artificiale, Carocci, Roma.
• Casti J.L. DePauli W. (2001) Gödel Raffaello Cortina Editore,
Milano.
• Cordeschi R. (1998) La scoperta dell’artificiale, Masson,
Milano.
• Dyson G.B.(2000) L’evoluzione delle macchine, Raffaello
Cortina Editore, Milano.
• Somenzi V., Cordeschi, R. (1994) La filosofia degli automi,
Bollati Boringhieri, Torino (II ed.)
• Von Neumann J. (1948) “La logica degli automi e la loro
autoriproduzione” trad. it. in Somenzi Cordeschi 1994, pp.151166.
Bibliografia Turing
•
Turing A.M. (1937), "On Computable numbers with an application to the Entscheidungsproblem", Proc. London Math.
Soc., (2) 42: 230-265,(1936-7); Ristampato in M. Davis The undecidable, (Raven Press, New York, 1965),116-154.
•
Turing A.M. (1939), "Systems of logic based on ordinals" Proc. Lond. Math. Soc., (2), 45: 161-228; Risatampato in M.
Davis The undecidable, (Raven Press, New York, 1965), 155-222.
•
Turing A.M. (1945), Proposal for the development in the Mathematical Division of an Automatic computing engine
(ACE), rapporto all'Executive Committee del National Physical Laboratory del 1945. Pubblicato in B.E. Carpenter e R.
N. Doran (a cura di) A.M. Turing's ACE report of 1946 and other papers, (MIT Press, Cambridge Mass. 1986), 20-105;
ora anche in Collected Works of A. M. Turing: mechanical intelligence, a cura di D. C. Ince, (North-Holland, Amsterdam
1992), 1-86; Parziale trad. it. in Turing A. M. Intelligenza meccanica, a cura G. Lolli, (Bollati Boringhieri, Torino,
1994), 29-62.
•
Turing A.M. (1947), "Lecture to the London Mathematical Society on 20 February 1947" in Collected Works of A. M.
Turing: mechanical intelligence, a cura di D. C. Ince, (North-Holland, Amsterdam 1992), 87-105; Trad. it. in Turing A.
M. Intelligenza meccanica, a cura G. Lolli, (Bollati Boringhieri, Torino, 1994), 63-87.
•
Turing A.M. (1948), "Intelligent Machinery" Report, National Physics Laboratory, in B. Meltzer D. Michie (Eds)
Machine intelligence, 5 (Edinburgh Univ. Press, 1969) pp.3-23; ora in Collected Works of A. M. Turing: mechanical
intelligence, a cura di D. C. Ince, (North-Holland, Amsterdam 1992), 107-127; trad. it. in Turing A. M. Intelligenza
meccanica, a cura G. Lolli, (Bollati Boringhieri, Torino, 1994), 88-120.
•
Turing A.M. (1950), "Computing Machinery and Intelligence", MIND, 59: 433-460. Ora in Collected Works of A. M.
Turing: mechanical intelligence, a cura di D. C. Ince, (North-Holland, Amsterdam 1992), 133-160; trad. it. in Turing A.
M. Intelligenza meccanica, a cura G. Lolli, (Bollati Boringhieri, Torino, 1994), 121-157.
Webliografia
• http://www.alanturing.net/
• http://www.turing.org.uk/turing/
• http://vmoc.museophile.sbu.ac.uk/
• http://www-groups.dcs.st-and.ac.uk/~history/
Mathematicians/Von_Neumann.html
• http://ei.cs.vt.edu/~history/VonNeumann.html