…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