Calcolo
Il concetto di calcolo costituisce uno dei più importanti fondamenti teorici delle discipline informatiche. Così come nelle discipline meccaniche non si possono comprendere le caratteristiche dei motori senza conoscere a fondo i principi della termodinamica, e nelle discipline elettroniche lo sviluppo di nuovi dispositivi non può prescindere dalla conoscenza delle leggi dell'elettromagnetismo, nelle discipline informatiche gli sviluppi metodologici e tecnologici si fondano imprescindibilmente sui presupposti teorici del calcolo. Secondo la definizione che è contenuta nel Rapporto finale sull'informatica dell'Association for Computing Machinery (ACM), stilato nel 1989 e successivamente approvato dall'ACM Education Board, la disciplina del c. si occupa prevalentemente dello studio sistematico di processi algoritmici che descrivono e trasformano l'informazione, e in particolare la loro teoria, l'analisi, il progetto, l'efficienza, l'implementazione e la loro applicazione. Alla base della nozione di c. vi sono quindi diversi modelli, sviluppati nel corso dei vari decenni, che descrivono in dettaglio come l'informazione può essere rappresentata e trasformata, e che hanno costituito il costante riferimento concettuale di tutti i progressi scientifici e tecnologici avvenuti nelle scienze informatiche. Tra i principali di essi si possono citare sia quelli ispirati dalle prime architetture degli elaboratori elettronici, come il modello di von Neumann, sia i modelli astratti sviluppati già a partire dagli anni Trenta del 20° secolo. È interessante osservare che molti di questi modelli e paradigmi di c. hanno cercato di ispirarsi al modo in cui la natura, includendo ovviamente in essa anche il genere umano, è in grado di effettuare operazioni e c. sui dati su cui normalmente opera. Senza voler entrare in sofisticate discussioni su come alcuni processi naturali possano essere interpretati o meno come effettivi processi di 'calcolo', basti ricordare l'origine e l'astrazione di alcuni modelli introdotti nel passato: per es., nel definire il suo modello di c., la macchina di Turing, A. Turing volle esplicitamente modellare le operazioni di c. effettuate da un impiegato di banca, mentre successivamente W.S. McCullock, W. Pitts e S.C. Kleene gettarono le fondamenta della teoria degli automi a stati finiti tentando di modellare il comportamento dei neuroni e delle reti neuronali. Anche se risalgono agli albori delle discipline informatiche, è sorprendente osservare che molti di tali modelli di c., e in particolar modo il modello di von Neumann, siano ancora alla base di gran parte delle moderne architetture degli elaboratori. Il loro successo e la loro longevità in una disciplina caratterizzata da un tasso di obsolescenza altrimenti elevato, possono essere spiegati, almeno in parte, con la loro aderenza a paradigmi di c. basati sulle tecnologie elettroniche a semiconduttori, che da vari decenni sono oramai alla base di tutti i dispositivi elettronici e in particolare delle piattaforme di calcolo.
Negli ultimi anni però sono risultati più evidenti i limiti delle attuali tecnologie elettroniche. Per es., già nel 2001 l'International Technology Roadmap for Semiconductors (2001 ITRS) affermava che entro i prossimi 5÷10 anni gran parte delle tecnologie elettroniche conosciute avrebbero raggiunto i loro limiti fisici. Questo ha stimolato la ricerca di nuovi modelli di c., basati su tecnologie alternative a quelle tradizionali, e in grado di rispondere alla domanda di risorse di c. sempre più potenti, che emerge da molte applicazioni. Motivati soprattutto dai continui progressi nel settore delle nanotecnologie, tra i nuovi paradigmi proposti sembrano affermarsi soprattutto i modelli di c. basati sull'infinitesimamente piccolo, come il calcolo quantistico (quantum computing) e il calcolo molecolare (DNA computing). Ancora una volta, si puó osservare che in entrambi i casi si cerca di studiare, comprendere e modellare fenomeni di 'calcolo' che si verificano direttamente in natura: anche se profondamente diversi dai modelli di c. tradizionale, e in un certo senso estremamente innovativi rispetto a essi, da questo punto di vista sia il c. quantistico, sia il c. molecolare sembrano innestarsi perfettamente nella tradizione storica dei modelli di calcolo.
Il calcolo quantistico
L'estrema miniaturizzazione ottenibile con le moderne tecnologie è in grado di produrre componenti elettronici estremamente piccoli, dell'ordine di qualche frazione di micron: su tali dimensioni, i relativi processi di fabbricazione risentono di fenomeni di natura quantistica. A partire dal lavoro pionieristico di R.P. Feynman del 1982, sotto il continuo stimolo degli aspetti tecnologici, si è cominciato a studiare la nozione di c. quantistico, il suo potere di c., nonché la realizzabilità fisica di calcolatori quantistici. Per spiegare cosa può rendere un calcolatore quantistico così diverso da un calcolatore tradizionale, consideriamo l'unità di base dell'informazione: il bit. Dal punto di vista fisico, un bit è rappresentato da un sistema che può essere posto in uno tra due possibili stati corrispondenti a diversi valori logici: sì o no, vero o falso, 1 o 0. Nella tecnologia elettronica, un bit di informazione può essere rappresentato da opportuni valori della tensione elettrica. Per es., un condensatore è un componente elettronico che può trovarsi in due diversi stati: se è carico rappresenta il valore 1, mentre se è scarico rappresenta il valore 0. Nella continua ricerca di componenti sempre più piccoli, un bit di informazione potrebbe anche essere codificato da diversi sistemi, come due diverse polarizzazioni della luce, o due diversi stati elettronici di un atomo. Tuttavia, se scegliamo un atomo per rappresentare un bit di informazione, dobbiamo considerare anche fenomeni di natura quantistica: in particolare, la meccanica quantistica ci dice che, oltre a essere in due stati elettronici distinti, l'atomo può anche trovarsi in una sovrapposizione coerente dei due stati. Ciò implica che l'atomo può trovarsi contemporaneamente nello stato 0 e nello stato 1. In generale, un sistema quantistico a due stati, chiamato bit quantistico (quantum bit o qubit), può essere posto nella sovrapposizione dei suoi stati logici 0 e 1; quindi, a differenza di un bit tradizionale, un qubit può codificare a ogni istante sia il valore 0 sia il valore 1.
Consideriamo ora un registro composto da due bit fisici. Un registro classico a due bit può memorizzare a ogni istante soltanto uno tra quattro numeri, ovvero può trovarsi soltanto in una tra quattro possibili configurazioni: 00, 01, 10, oppure 11. Un registro quantistico a due qubit, invece, può memorizzare a ogni istante tutti e quattro i numeri (00, 01, 10 e 11) in una sovrapposizione quantistica. Se aggiungiamo un ulteriore qubit a un registro quantistico, a differenza di un registro tradizionale, ne aumentiamo quindi la sua capacità in maniera esponenziale: tre qubit possono memorizzare contemporaneamente 8 numeri distinti, quattro qubit possono memorizzare contemporaneamente 16 numeri distinti, e così via. In generale, n qubit possono memorizzare contemporaneamente 2n numeri distinti: ciò che è più importante, una volta che il registro quantistico contenga una sovrapposizione di numeri distinti, possiamo eseguire, nello stesso istante, la stessa operazione su tutti i numeri memorizzati nel registro. Per es., se i qubit sono atomi, opportuni impulsi laser sono in grado di modificare gli stati elettronici e far evolvere il sistema da una sovrapposizione iniziale di stati verso un'altra sovrapposizione di stati. Durante una tale evoluzione da una sovrapposizione all'altra, viene modificato ogni numero della sovrapposizione: tale processo è equivalente a un procedimento di c. parallelo, anche se non viene affatto effettuato con un'architettura parallela ma piuttosto con un unico dispositivo quantistico. Concettualmente, un elaboratore quantistico potrebbe quindi essere in grado di effettuare, in un solo passo di c., una stessa operazione su 2n numeri diversi, codificati in sovrapposizioni coerenti di n qubit. Per ottenere lo stesso risultato, un elaboratore classico dovrebbe invece ripetere la stessa operazione per 2n volte oppure utilizzare un'architettura parallela con 2n processori: in entrambi i casi, per eguagliare le prestazioni ottenibili tramite il c. quantistico, le risorse di cui l'elaboratore classico ha bisogno sarebbero esponenzialmente più grandi.
Vediamo adesso i passi che hanno portato all'introduzione di un modello di c. quantistico a partire dai modelli classici, come la macchina di Turing. In termini informali, una macchina di Turing è utile a descrivere e a simulare le azioni di un sistema di elaborazione, e tenta di astrarre il procedimento intrinseco con cui vengono effettuati i calcoli. Più formalmente, una macchina di Turing è composta da un nastro infinito e da un dispositivo posizionato su un qualche simbolo del nastro; il dispositivo è in grado di leggere (tramite una testina di lettura) il simbolo scritto nel nastro, di effettuare azioni in base al simbolo letto e allo stato interno in cui si trova, eventualmente di scrivere (tramite una testina di scrittura) modificando il simbolo nel nastro, e di spostarsi di una posizione a destra o a sinistra nel nastro. Pensiamo di modellare il processo con cui una persona effettua c.: intuitivamente, il nastro rappresenta le infinite risorse di carta a sua disposizione durante l'esecuzione dei c., per quanto complessi essi possano essere; durante il procedimento, la persona può scrivere i risultati intermedi su qualche foglio, modificarli e scriverne altri a suo piacimento, prima di scrivere il risultato finale del calcolo. Questo è esattamente il procedimento modellato nella sua essenzialità dal modello di Turing. Le testine di lettura e di scrittura di una macchina di Turing possono essere programmate con regole appropriate, così da avere risposte diverse dalla macchina in funzione del particolare simbolo letto sul nastro: come caso particolare, tali regole possono essere scritte inizialmente sul nastro della macchina e modificate durante il corso dell'elaborazione. Anche se Turing definì il suo modello vari anni prima della costruzione del primo elaboratore elettronico, vi sono notevoli analogie tra il nastro di una macchina di Turing e la memoria di un elaboratore elettronico, e tra le regole scritte sul nastro di una macchina di Turing e i programmi memorizzati nella memoria di un elaboratore elettronico.
È evidente che la macchina di Turing si basa sugli assiomi della fisica classica: per es., lo stato del nastro e della testina sono sempre univocamente individuabili, e gli spostamenti della testina sono sempre regolati dalle leggi classiche del moto. Una macchina di Turing quantistica deve invece rispettare i vincoli della meccanica quantistica, tra cui il principio di indeterminazione di Heisenberg e l'equazione di Schrödinger. Lo sviluppo di una macchina di Turing quantistica, e conseguentemente di un elaboratore quantistico, ha richiesto diversi passi intermedi. Innanzitutto, dato che la meccanica quantistica è reversibile, una macchina di Turing quantistica deve essere anch'essa reversibile: già nel 1973 C. Bennet dimostrò che è possibile costruire una macchina di Turing reversibile, mentre nel 1980 P. Benioff dimostrò che, visto che la meccanica quantistica è reversibile, la reversibilità è una condizione necessaria per realizzare una macchina di Turing quantistica. Nel 1982 Feynman pubblicò il suo famoso lavoro sui computer quantistici, in cui stabilì che una macchina di Turing è in grado di simulare un sistema quantistico soltanto al prezzo di un rallentamento esponenziale, mentre un computer basato sui bit quantistici non è affatto soggetto a tali limitazioni. Fu soltanto nel 1985, però, che si arrivò alla prima definizione di macchina di Turing quantistica, grazie al lavoro di D. Deutsch, che riuscì così a gettare le basi teoriche del c. quantistico.
Uno dei risultati più importanti del c. quantistico è l'algoritmo di P.W. Shor per la fattorizzazione (decomposizione in fattori primi) di numeri interi: nel 1994 Shor ha infatti dimostrato che nel modello di c. quantistico tale problema può essere risolto in tempo polinomiale, risultato che non viene ritenuto possibile in un modello di c. classico. Tale scoperta ha potenzialmente una grande valenza applicativa, dato che la difficoltà di decomporre in fattori un intero con un numero elevato di cifre è alla base della sicurezza di molti sistemi crittografici, come, per es., il sistema crittografico a chiave pubblica RSA (così denominato dalle iniziali dei suoi tre inventori, R.L. Rivest, A. Shamir e L.M. Adleman), diffusamente utilizzato per lo scambio sicuro dei dati tramite cifratura e per la firma digitale. Le potenziali ricadute dell'algoritmo quantistico di Shor hanno quindi dato vita a un nuovo impulso di studi su algoritmi quantistici e sulla realizzazione di calcolatori quantistici. Nonostante ciò, la realizzabilità fisica di un elaboratore quantistico rimane ancora un problema aperto, anche se con il passare degli anni vengono proposte sempre nuove tecnologie allo scopo e vengono scoperte nuove proprietà del c. quantistico. I primi prototipi di calcolatori quantistici furono costruiti nel 1997 nel centro di ricerca IBM di Almaden, in California, e da allora sono stati realizzati 'processori' a 5 e 7 qubit. Anche se non è ancora chiaro quando l'uomo riuscirà a costruire il primo elaboratore quantistico vero e proprio, la teoria quantistica del c. sembra già da ora in grado di poter giocare un ruolo fondamentale negli sviluppi futuri delle scienze e delle tecnologie dell'informazione e della comunicazione.
Il calcolo molecolare
Come nel caso del c. quantistico, il c. molecolare si basa sulla possibilità di scrivere, leggere ed elaborare dati utilizzando strumenti di c. estremamente miniaturizzati, ossia alcune particolari molecole, come per es. le molecole di DNA. Anche i fondamenti teorici del c. molecolare si basano sul lavoro pionieristico di Adleman, che in un esperimento del 1994 dimostrò come utilizzare frammenti del DNA per risolvere efficientemente un'istanza del complesso problema teorico della ricerca di un cammino hamiltoniano in un grafo orientato, problema che è NP-completo e quindi ritenuto di difficile soluzione nei modelli di c. e nelle architetture di elaborazione tradizionali.
L'idea fondamentale fu quella di utilizzare le molecole del DNA per codificare il grafo e di eseguire le operazioni e i calcoli su tale grafo per mezzo di enzimi e di reazioni biochimiche. Più in dettaglio, il metodo utilizzato nell'esperimento si basa sulla rappresentazione dei nodi di un grafo tramite sottosequenze molecolari del DNA: combinando queste sottosequenze tramite opportune reazioni biochimiche, si riesce a descrivere, con modalità statistiche, l'insieme di tutti i cammini nel grafo. Utilizzando strumenti biochimici, Adleman fu in grado di estrarre dai filamenti del DNA che descrivevano l'insieme dei cammini nel grafo la soluzione corretta del problema del cammino hamiltoniano. Questo primo esperimento di c. biomolecolare, e più in generale la possibilità di eseguire c. tradizionali attraverso l'utilizzo di strumenti molecolari, ha suscitato negli anni recenti molto interesse non solo nella comunità scientifica, ma anche nel mondo industriale, per le sue potenziali implicazioni economiche.
Per meglio comprendere il modello di c. molecolare, è importante tenere presente la struttura a doppia elica del DNA: intuitivamente, in tale modello un filamento (strand) del DNA viene utilizzato per memorizzare i dati, mentre l'altro filamento viene utilizzato come memoria di riserva (backup). Gli enzimi, invece, vengono utilizzati per ricercare, leggere e scrivere i dati contenuti nei filamenti del DNA. L'informazione su cui effettuare le operazioni viene di solito codificata in forma di soluzione chimica: se il DNA è in soluzione acquosa, i dati presenti nella soluzione trovano l'opportuno componente del DNA con cui legarsi. In tale processo, gli enzimi hanno il ruolo di favorire o rompere i legami tra i dati e componenti del DNA, e consentono quindi di scrivere, leggere e trasferire dati a livello molecolare, in maniera analoga a quanto avviene nei modelli di c. tradizionali. Questa descrizione, anche se molto semplicistica, dà un'idea intuitiva di come funzioni il c. molecolare. Dopo l'esperimento di Adleman, ulteriori esperimenti di c. molecolare, svolti in gran parte da R. Lipton e altri ricercatori della Princeton University, hanno dimostrato come l'approccio di Adleman possa essere esteso anche ad altre classi di problemi.
Negli anni, l'interesse verso il c. molecolare si è concentrato soprattutto sulla possibilità di eseguire ricerche, operazioni logiche e operazioni aritmetiche su grandi quantità di dati. Per comprendere intuitivamente le potenzialità realizzabili con le attuali tecnologie biochimiche, basti considerare che oggi si riescono a effettuare ricerche in un grammo di DNA in soluzione acquosa in un tempo limitato a pochissimi secondi: se sfruttate completamente, queste tecnologie sarebbero quindi in grado di effettuare ricerche in parallelo su moli di dati della dimensione di 108 terabyte in meno di tre secondi! La principale caratteristica del c. molecolare, che lo rende quindi interessante per le future applicazioni, risiede proprio nelle sue enormi potenzialità di parallelismo: esattamente come avviene nel caso degli elaboratori ad alte prestazioni attualmente utilizzati, un elaboratore molecolare sarebbe in grado di effettuare molte elaborazioni in parallelo e quindi di analizzare contemporaneamente molte soluzioni dello stesso problema. C'è però un'importante differenza con le tradizionali architetture di elaborazione, che è in grado di rendere il c. molecolare estremamente competitivo con le altre tecnologie: i frammenti di DNA utilizzabili in un procedimento di c. sono molto più piccoli e molto più numerosi, e di svariati ordini di grandezza (approssimativamente 1023), delle tradizionali unità di elaborazione (CPU) presenti negli attuali elaboratori elettronici ad alte prestazioni.
Nonostante le enormi potenzialità e l'interesse suscitato dal c. molecolare, rimangono però ancora molti aspetti e ostacoli che devono essere affrontati prima della possibile costruzione di un calcolatore molecolare. Molti di questi sono relativi agli attuali limiti delle tecnologie biochimiche, che sembrerebbero richiedere ulteriori progressi scientifici prima di poter essere sfruttate in un reale sistema di calcolo. Altri aspetti sono invece relativi alla realizzazione efficiente con tecnologie di biologia molecolare di alcune funzionalità tipiche delle architetture di elaborazione, come per es. i sistemi di ingresso/uscita e il sistema di controllo. Fino a che tali aspetti non saranno completamente risolti, il c. molecolare potrebbe rimanere di prevalente interesse teorico.
bibliografia
J. Brown, Minds, machines and the multiverse: the quest for the quantum computer, New York 2000.
Y. Benenson, T. Paz-Elizur, R. Adar et al., Programmable and autonomous computing machine made of biomolecules, in Nature, 2001, 414, 1, pp. 430-34.
American Mathematical Society, Quantum computation: a grand mathematical challenge for the twenty-first century and the millennium, ed. S.J. Lomonaco Jr, Washington 2002.
J. Eisert, M.M. Wolf, Quantum computing, New York 2004; M. Amos, Theoretical and experimental DNA computation, New York 2005.