…da von Neumann al
computer quantistico
architettura dell’elaboratore
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: not (p) = 1 – p
congiunzione: p1 and p2 = p1 . p2
disgiunzione: p1 or 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
Turing allo stesso modo si chiese se
esistesse un algoritmo in grado di
decidere se, data una funzione
computabile, questa si arrestasse o no.
In poche parole, data f e dato x, esiste un
algoritmo che è in grado di stabilire se,
dopo un numero finito di passi, otteniamo
f(x) ?
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
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
Il primo computer
Il lavoro di Shannon permise di
sostituire le schede forate con
circuiti elettrici, migliorando
considerevolmente le prestazione
delle macchine. Questo contributo
diede una forte spinta alla ricerca ,
tanto che nel1946 venne creato il
primo computer programmabile:
ENIAC
Questi primi computer potevano eseguire compiti differenti, ma per cambiare la
loro funzione necessitavano di tecnici che praticamente agissero sulla
macchina, ad esempio spostando cavi.
Nel 1946 viene completato il primo elaboratore fondato sull’ idea di “programma
memorizzato” del matematico ungherese John Von Neumann.
Questo tipo di macchina contiene tutte le istruzioni operative, immagazzinate
sotto forma di impulsi elettronici e possono venir modificate senza dover operare
fisicamente sull’elaboratore.
La macchina di von Neumann
Input
Cpu
Memoria
Bus
Output
Input/Output
Questi dispositivi gestiscono lo scambio di informazioni fra il computer e il
mondo esterno. Hanno inoltre il compito di eseguire la conversione
analogico-digitale, o viceversa.
INPUT
indica i dispositivi con i
quali è possibile
immettere informazioni
nel computer. Se
necessario opera la
trasformazione da
segnale analogico a
digitale, e infine a codice
binario.
OUTPUT
rappresenta gli strumenti
con i quali il computer
può dare informazioni al
mondo esterno.
In generale trasforma il
codice binario in forme
che possono essere
comprensibili o utilizzate
dall’esterno.
Esempi: tastiera, mouse,
CD,scanner, microfono…
Esempi: schermo,
stampante, casse…
La memoria
La memoria è l’elemento in cui è possibile conservare informazioni. A differenza
delle macchine precedenti, nel modello di von Neumann non vi sono solo i dati
necessari al funzionamento ma anche le operazioni da eseguire.
ROM (Read Only Memory)
E’ una memoria permanente sulla
quale si può agire solamente
leggendo i dati che vi sono
conservati. In essa sono
contenute le operazioni
fondamentali necessarie per
l’avvio e l’uso del computer.
RAM (Random Access Memory)
E’ una memoria temporanea, sulla
quale possiamo scrivere e leggere
dati, che però verranno persi allo
spegnimento del computer. Viene
usata per salvare dati utilizzati
durante un elaborazione, ma che
possono poi essere cancellati.
Possiamo considerare la memoria come una serie di caselle ciascuna contente
un dato (espresso come serie di bit) e individuata da un preciso indirizzo.
La Cpu
La Cpu è il “cervello” del computer, dove cioè vengono analizzate ed elaborate le
informazioni. Ha il compito di decodificare ed eseguire le istruzioni di un
programma, e più in generale di controllare e gestire tutti gli eventi del computer.
Arithmetic Logic Unit (ALU)
La ALU esegue le operazioni
logiche o matematiche , si
fonda sui circuiti ideati da
Shannon, ed è un elemento
presente anche nelle
macchine precedenti a quella
di von Neumann.
Control Unit (CU).
La CU viene introdotta sulla
macchina di Von Neumann con il
compito di organizzare il traffico
dei dati e verificare che le
operazioni pianificate dal
programma memorizzato
vengano eseguite correttamente.
Il processore esegue le operazioni in modo sequenziale: inizia l'operazione
successiva solo al compimento di quella attualmente in corso.
Il ritmo con cui la cpu lavora dipende da un segnale periodico, detto clock,
necessario alla sincronizzazione dei processi. La durata di ciascuna operazione
viene misurata in periodi, cioè come multiplo del tempo che passa da uno
“scatto” del clock al successivo.
Il bus
Il bus è lo strumento che permette il collegamento fra gli elementi precedenti,
gestisce il passaggio di informazioni all’interno del computer.
La velocità massima con la quale una macchina può operare dipende
notevolmente dall’efficienza del Bus: la frequenza di clock con la quale
lavora la cpu deve essere compatibile con il tempo necessario a trasmettere
l’informazione.
Input
Cpu
Memoria
ADC
Bus
Output
Input
Cpu
Memoria
Istruzione 1
Istruzione 2
…
Istruzione n
Istruzione 1
Istruzione 2
…
…
Istruzione n
Bus
Output
Input
Cpu
Memoria
Istruzione 1
Istruzione 2
…
Istruzione n
Dato 1
Dato 2
…
Dato m
Dato 1
Dato 2
…
…
Dato m
Bus
Output
Input
Cpu
Memoria
Istruzione 1
Istruzione 2
…
Istruzione n
Dato 1
Dato 2
…
Dato m
RISULTATO
Bus
Output
Input
Cpu
Memoria
Istruzione 1
Istruzione 2
…
Istruzione n
Dato 1
Dato 2
…
Dato m
RISULTATO
Bus
Output
Limiti del modello di Von Neumann
Collo di bottiglia.
Le prestazioni della macchina di von Neumann dipendono dalla quantità di
dati che possono venire trasferiti dalla memoria alla cpu nel tempo.
Può succedere quindi che il computer lavori a ritmi molto più bassi rispetto a
quelli sui quali potrebbe ancora operare la cpu per la lentezza con cui
vengono passati i dati dalla memoria, si crea quindi una coda di “attesa” che
rallenta i processi di calcolo.
Tempi di elaborazione.
Nonostante l’evoluzione tecnologica che ha portato il computer a lavorare a
velocità altissime, esistono ancora algoritmi teoricamente risolubili che non
lo sono tuttavia dal punto di vista pratico. Questa contraddizione dipende
dal fatto che i tempi necessari alla loro risoluzione sono troppo grandi.
Funzioni casuali?
I valori “casuali” forniti dal computer derivano da un algoritmo che parte da
un numero detto seed, che viene scelto in maniera deterministica.
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), possiamo associare a questi stati i valori 1 e 0.
Quindi, un atomo potrebbe codificare uno 0 nello stato
elettronico fondamentale e un 1 in uno stato eccitato.
Intervenendo sull’atomo con una giusta dose di energia
(con un laser ad esempio) possiamo far variare lo stato in
cui si trova.
Vantaggi…
Generazione di numeri effettivamente
casuali: con una giusta quantità di energia
l'elettrone può anche permanere in uno stato
intermedio, ma nel momento in cui si va a fare la
misura ("guardiamo in che stato è"), l'elettrone
finisce in uno dei sue stati possibili,1 o 0, con la
stessa probabilità di ½.
Velocità: un computer quantistico eseguirebbe
tutti i calcoli possibili in una sola volta
(parallelismo quantistico). Ciò potrebbe essere
sfruttato per scomporre rapidamente numeri
molto grandi.
… e problemi realizzativi
La natura stessa degli atomi: considerando
che per realizzare un computer che possa
competere con un computer tradizionale gli
atomi in gioco sono migliaia (o milioni), basta
disturbare anche uno solo per compromettere la
coerenza quantistica del sistema
Correzione degli errori: attualmente vengono
utilizzati sistemi che richiedono la misurazione
del bit, in un calcolatore quantistico porterebbe a
perdita di coerenza
conclusioni
Computer ad enzimi
Computer molecolari
Computer quantistici
…ma la logica legata alla trasmissione
dell’informazione è sempre la stessa:
quella immaginata da Turing
note
http://ironphoenix.org/tril/tm/
Le scienze: quaderni n. 121 settembre
2001
Frixione – Palladino: Funzioni, macchine,
algoritmi – Carocci editore
Wikipedia