…da von Neumann al
computer quantistico
architettura dell’elaboratore
Come funziona un computer ?
• Input: inserimento dei dati
Come funziona un computer ?
• Input: inserimento dei dati
• Elaborazione (?)
Come funziona un computer ?
• Input: inserimento dei dati
• Elaborazione (?)
• Output: risultato
La macchina analitica di Babbage
(1837)
Ideata (ma, forse, mai realizzata)
dal matematico Charles Babbage
per risolvere problemi generali
di calcolo. Aveva una architettura
molto simile ai moderni elaboratori.
Era formata da: un “magazzino” (store/memoria);
un mulino (mill/unità di elaborazione) e un lettore
di schede perforate (dispositivo di input). Le schede
perforate venivano utilizzate già dai primi dell’ottocento
nei telai Jacquard, dove i fori rappresentavano i punti in
cui l’ago avrebbe attraversato la stoffa per la
realizzazione del disegno.
Boole e l’algebra di…(1847)
ovvero come la logica filosofica diventa
matematica
“L’analisi matematica della logica”
• p è vera = 1
• p è falsa = 0
• negazione non (p) = 1 – p
• congiunzione p1 e p2 = p1 . p2
• disgiunzione p1 o p2 = p1 + p2
La logica proposizionale viene ridotta ad un
semplice calcolo … ma quanto fa 1 + 1 = ?
Il teorema di incompletezza di
Godel (1931)
In ogni formalizzazione coerente della
matematica che sia sufficientemente potente da
poter assiomatizzare la teoria elementare dei
numeri naturali — vale a dire, sufficientemente
potente da definire la struttura dei numeri
naturali dotati delle operazioni di somma e
prodotto — è possibile costruire una
proposizione sintatticamente corretta che non
può essere né dimostrata né confutata all'interno
dello stesso sistema (1° teorema di Godel)
Il problema della fermata
Touring allo stesso modo si chiese se
esistesse un algoritmo in grado di
decidere se una funzione computabile si
arrestasse oppure no
La macchina di Turing (1936)
• un sistema di memorizzazione
• un dispositivo di lettura
e di scrittura di tali dati
• un meccanismo di controllo per stabilire le
azioni da intraprendere.
Funzionamento della MT
• Il sistema di memorizzazione è immaginato
come un nastro virtualmente infinito suddiviso in
celle
• Il dispositivo di scrittura e lettura è una testina
che può spostarsi sulle singole celle in entrambe
le direzioni e può scrivere, cancellare o sostituire
nella cella su cui è posizionata dei simboli di un
alfabeto
• La macchina può assumere un numero di “stati”
finito. Lo stato in cui si trova la macchina in un
dato istante dipende dagli eventi precedenti del
processo di calcolo
Operazioni di una MT
Ogni operazione può essere scomposta in un numero finito
delle seguenti operazioni:
• Sostituzione del simbolo osservato con un altro simbolo
• Spostamento della testina su una delle celle
immediatamente attigue al nastro
• Cambiamento dello stato interno della macchina
• http://ironphoenix.org/tril/tm/
La macchina universale di Turing
è una macchina che riesce ad eseguire tutti i programmi
eseguibili da una qualsiasi macchina di Turing. Cessa di
essere una macchina specificatamente dedicata a
svolgere una operazione e diventa universalmente
programmabile. Non appena la macchina raggiunge una
massa critica, che le permette di decodificare istruzioni
codificate numericamente e simularle passo passo, essa
diventa in grado di eseguire qualunque compito
codificabile da un insieme finito di istruzioni. Questo
avviene se la macchina è in grado di eseguire le
operazioni fondamentali, cioè le leggi della logica
elementare.
Arriva l’elettronica (1938)
Shannon tradusse l’algebra di Boole in termini di circuiti
elettrici:
• 1 viene identificato con il passaggio di corrente elettrica
attraverso un filo
• 0 viene identificato dall’assenza di corrente
La negazione e la congiunzione corrispondono ad interruttori
che:
• fanno passare la corrente solo se arriva da entrambi i fili
(congiunzione)
• fanno passare la corrente se arriva da uno dei fili
(disgiunzione)
• accendono la luce se è spenta, la spengono se è accesa
(negazione)
AND
OR
NOT
…e finalmente von Neumann
(1946)
•
•
•
•
•
INPUT
MEMORIA
CPU
BUS
OUTPUT
La memoria
La Cpu
La Alu
Il bus
La memoria
Cosa ci riserva il futuro ?
• Abbiamo assistito negli ultimi anni ad una
crescita della velocità di calcolo, della
quantità di memoria disponibile, alla
riduzione dei componenti utilizzati, ma la
logica che c’è dietro il funzionamento di un
computer è sostanzialmente la stessa di
sessant’anni fa, e cioè quella di essere in
grado di calcolare le funzioni calcolabili…
ma i limiti fisici dei circuiti integrati
comincia a farsi sentire.
Il computer quantistico
• L’utilizzo di componenti sempre più piccoli porta a dover
fare i conti non più sul comportamento della materia, ma
su come si comportano aggregati di singoli atomi. Di
conseguenza la descrizione del loro funzionamento deve
essere formulata in termini quantistici. Partendo dal fatto
che gli atomi possono trovarsi soltanto in stati di energia
discreti: un atomo quando passa da uno stato di energia
ad un altro, assorbe ed emette energia in quantità fisse
(quanti). Quindi, un atomo potrebbe codificare uno 0
nello stato elettronico fondamentale e un 1 in uno stato
eccitato (con un fascio laser).
Vantaggi…
… e problemi realizzativi
conclusioni