Percorsi Strani

Un calcolo o computazione (dal latino computare, “contare”, “tagliare”), è la rappresentazione astratta di un processo fisico in termini di stati, e di transizioni fra stati o eventi.

La definizione degli stati e degli eventi possibili è formulata in un modello di calcolo, come la macchina di Turing o l’automa a stati finiti. Per esempio, lo stato di una macchina di Turing è la sequenza completa dei simboli sul suo nastro più la posizione della testa ed il suo simbolo interno, ed un evento è il movimento fra due stati successivi, definito deterministicamente in termini di movimenti elementari di lettura, scrittura, spostamento a sinistra o a destra.

Per eseguire una computazione, una corrispondenza dotata di una certa robustezza è innanzitutto stabilita fra un modello di calcolo ed un sistema fisico, ciò significa che gli stati e gli eventi nel modello sono usati per identificare degli stati e degli eventi osservati nel sistema, e che la corrispondenza scelta è abbastanza stabile in relazione a vari tipi di perturbazione.

Il sistema è quindi preparato in uno stato iniziale ed è lasciato evolvere attraverso un percorso di eventi nello spazio degli stati, fino a raggiungere uno stato definito come finale. La dinamica discreta dello spazio computazionale può essere rappresentata con un grafo orientato, i cui nodi sono degli stati possibili del sistema e gli archi sono degli eventi che trasformano uno stato in un altro.

Dinamica computazionale irreversibile Cliccare l’immagine per ingrandire1

Reversibilità logica

Una funzione è detta reversibile (dal latino revertere, ‘rovesciare’) se, data la sua uscita, si può sempre determinare la sua entrata, ciò che accade quando esiste una relazione biiettiva fra stati di ingresso e di uscita. Se lo spazio degli stati è finito, tale funzione è una permutazione. La reversibilità logica implica la conservazione dell’informazione.

Se più stati di ingresso corrispondono ad uno stesso stato di uscita, la funzione è irreversibile, in quanto conoscendo il solo stato di uscita non è possibile determinare qual era lo stato di ingresso. In algebra di Boole, la funzione NOT è reversibile, mentre SET TO ONE è irreversibile. Le funzioni booleane a due variabili come AND, OR, XOR sono ugualmente irreversibili, dato che fanno corrispondere 2² stati di ingresso con 2¹ stati di uscita, cosicché dell’informazione viene perduta nella fusione dei cammini, come si vede nel grafo seguente di una computazione NAND, la cui evoluzione inversa non è più deterministica.

Il lato destro tenta di rappresentare la corrispondenza inversa del lato sinistro

Reversibilità fisica

Le leggi fisiche conosciute sono reversibili. Ciò è vero sia per la meccanica classica, basata sulla dinamica lagrangiana/hamiltoniana, che per la meccanica quantistica standard, in cui i sistemi chiusi evolvono secondo trasformazioni unitarie, che sono biiettive ed invertibili. In conseguenza, quando un sistema fisico effettua una computazione irreversibile, la corrispondenza con il modello di calcolo indica che il sistema non può rimanere chiuso.

Più precisamente, dato che una computazione irreversibile riduce lo spazio degli stati fisici portatori di informazione, la loro entropia deve diminuire aumentando l’entropia degli stati non portatori di informazione, che rappresentano la parte termica del sistema.

Nel 1961 Landauer studiò questo argomento termodinamico, e propose il principio seguente : se un sistema fisico effettua una computazione classica logicamente irreversibile, allora deve aumentare l’entropia dell’ambiente con una quantità minima di calore liberato di kT x ln(2) per ciascun bit perduto (dove k è la costante di Boltzmann e T la temperatura, cioè circa 3 x 10^-21 joules a temperatura ambiente),² che mette in risalto due fatti :

• l’irreversibilità logica di una computazione implica l’irreversibilità fisica del sistema che l’effettua (”l’informazione è fisica”);
• i calcoli logicamente reversibili possono essere almeno in principio intrinsecamente non dissipativi (in rapporto con il teorema di Carnot sui motori termici, che mostra che i motori più efficienti sono reversibili, ed il teorema di Clausius, che attribuisce un cambiamento di entropia nullo ai processi reversibili).

Inclusione reversibile di calcoli irreversibili

Landauer notò anche che ogni computazione irreversibile può essere trasformata in una computazione reversibile, includendola in una computazione più ampia nella quale nessuna informazione viene perduta, replicando ogni uscita nell’ingresso (aggiunta di sorgenti) ed ogni ingresso nell’uscita (aggiunta di pozzi).

Per esempio, la funzione irreversibile NAND vista sopra può essere incorporata nella biiezione seguente, conosciuta anche come porta di Toffoli³ (la funzione iniziale è contrassegnata in rosso) :

I bit di informazione aggiuntivi, come dei fili di Arianna, assicurano la possibilità di invertire ogni percorso computazionale: essi sono i rifiuti del percorso in avanti ed il programma del percorso a ritroso. Invece di perderli nell’ambiente, sono conservati nello spazio computazionale controllato.

Le porte di Toffoli sono delle funzioni primitive reversibili ed universali, ciò significa che tutte le funzioni reversibili possono essere costruite in termini di porte di Toffoli. La porta di Fredkin è un altro esempio di funzione primitiva reversibile ed universale. Essa scambia i suoi due ingressi in funzione dello stato di un terzo ingresso di controllo, permettendo di incorporare qualsiasi computazione in un itinerario condizionale di segnali conservati.

Alcuni scambi ferroviari sono reversibili

Modelli di calcolo reversibile

Il modello balistico, inventato da Fredkin e Toffoli,⁴ fu uno dei primi modelli di calcolo centrati sull’attuazione con dei componenti fisici reversibili. Basato sulle leggi della meccanica classica, è equivalente al formalismo della teoria cinetica dei gas perfetti. La presenza di sfere rigide in movimento in dei punti specificati è definita come 1, la loro assenza come 0. Delle interazioni di collisione ad angolo retto permettono la costruzione di varie funzioni primitive, come per esempio la seguente porta universale a 2 ingressi e 3 uscite introdotta da Feynman,⁵ che propose anche con Ressler una versione balistica della porta di Fredkin.

Porta di Feynman

Nella pratica, una computazione effettuata da queste sfere sarebbe molto inaffidabile, in quanto l’instabilità risultante dalle più piccole perturbazioni genererebbe rapidamente delle deviazioni caotiche, producendo una uscita saturata di errori. Gli errori possono essere corretti (per esempio, aggiungendo dei potenziali per stabilizzare i percorsi), tuttavia il processo di correzione degli errori è lui stesso irreversibile e dissipativo - visto che deve cancellare l’informazione errata. Pertanto, la correzione degli errori sembra essere l’unico aspetto della computazione che definisca un limite inferiore alla dissipazione di energia.

Un approccio più stabile è quello del modello di calcolo Browniano,⁶ dove il rumore termico è al contrario autorizzato ad interagire liberamente con un sistema computazionale vicino all’equilibrio. Delle barriere di energia potenziale definiscono i cammini di uno spazio computazionale, nel quale il sistema si sposta casualmente fino a raggiungere uno stato finale. L’RNA polimerasi, l’enzima implicato nella trascrizione del DNA, è un esempio di macchina browniana che effettua una “copia di nastro” in modo logicamente reversibile. Il processo di replicazione del DNA segue un meccanismo simile, ma aggiunge una logica irreversibile di correzione di errori.

Rovesciamento di Lecerf-Bennett

Il metodo di inclusione è tuttavia insufficiente per costruire un calcolatore universale fisicamente reversibile, dato che la quantità crescente di informazione riprodotta per ciascun evento saturerebbe ogni memoria finita. A quel punto, la computazione terminerebbe - a meno che la memoria non sia irreversibilmente cancellata, ma in tal caso la dissipazione sarebbe semplicemente rinviata, e non evitata.

Ciò sembrava escludere la possibilità di costruire dei calcolatori reversibili, fino a che Bennett ⁷ non trovò una soluzione notevole (un lavoro precedente di Lecerf⁸ ne aveva anticipato il metodo formale), mostrando che è possibile almeno in principio di effettuare una quantità illimitata di calcoli senza alcuna dissipazione di energia.

Il sistema reversibile deve calcolare la funzione inclusiva due volte: la prima volta “in avanti” per ottenere e registrare il risultato, e la seconda volta “a ritroso”, come una computazione immagine speculare della funzione inversa, che annulla il passo precedente e riporta il sistema chiuso nel suo stato iniziale.

M. C. Escher, Cigni (1956).
Tutte le opere di M.C. Escher (c) 2007 The M.C. Escher Company - the Netherlands.
Tutti i diritti riservati. Riprodotto con autorizzazione. www.mcescher.com
Cliccare l’immagine per ingrandire

L’irreversibilità logica ed il diavoletto di Maxwell

Nel 1867 Maxwell propose un’esperienza di pensiero riguardante un “diavoletto” finito e microscopico, capace di osservare i movimenti delle singole molecole. Questo diavoletto sorveglia una piccola porta che separa due contenitori riempiti di gas alla stessa temperatura. Quando una molecola si avvicina, il diavoletto verifica la sua velocità ed apre o chiuda la porta, in modo da inviare le molecole lente in un contenitore (che si raffredda), e le molecole rapide nell’altro contenitore (che si scalda), in violazione apparente della seconda legge della termodinamica.

Un primo passo importante verso la soluzione di questo paradosso controverso fu fatto nel 1929 da Szilard⁹ che, dopo aver evitato ogni trappola dualistica sostituendo il diavoletto intelligente con una semplice macchina, suggerì che il conteggio corretto dell’entropia viene restaurato nel processo di misurazione della posizione delle molecole. Questa spiegazione è diventata lo standard fino al 1981, quando Bennett mostrò⁶ che la fase fondamentalmente dissipativa non è sorprendentemente la misurazione (che può essere effettuata in modo reversibile) ma la fase logicamente irreversibile della cancellazione della memoria del diavoletto, per fare spazio alle misurazioni successive.

Reversibilità nella computazione quantistica

La computazione quantistica sfrutta gli effetti fisici di superposizione ed entanglement, che conducono ad un paradigma computazionale di tipo qualitativamente nuovo.¹⁰ Nei modelli di calcolo quantistico, tutti gli eventi si verificano secondo delle trasformazioni unitarie, cosicché tutte le porte logiche quantistiche sono reversibili.

I sistemi quantistici sono meno sensibili a certi tipi di errori che riguardano i calcoli classici, dato che il loro spettro discreto impedisce le traiettorie caotiche, dunque, per esempio, un modello balistico quantistico è più affidabile rispetto al suo omologo classico.

Tuttavia, i sistemi quantistici sono turbati da nuove sorgenti di errore, conseguenti alle interazioni con l’ambiente, come la perdita della coerenza quantistica. E’ possibile correggere degli errori quantistici generici fino ad un certo limite,¹¹ in modo da ricostruire uno stato quantistico esente da errori, al prezzo della cancellazione quantistica irreversibile dell’informazione quantistica errata.

Ringrazio Charles H. Bennett per i suoi commenti stimolanti sul manoscritto.

1. A. Wuensche, M. Lesser, “The global dynamics of cellular automata“, Ref Vol. I of the Santa Fe Institute Studies in the Sciences of Complexity. Addison-Wesley (1992) [Immagini di grafi di transizione di automai cellulari]. [↩]
2. R. Landauer, “Irreversibility and heat generation in the computing process“, IBM Journal of Res. and Dev., 5:3, 183 (1961) [Irreversibilità logica, principio di Landauer]. [↩]
3. T. Toffoli, “Reversible computing“, Tech. Memo MIT/LCS/TM-151, Mit Lab. for Comp. Sci. (1980) [Porta di Toffoli, automa reversibile]. [↩]
4. E. Fredkin, T. Toffoli, “Conservative logic“, International Journal of Theoretical Physics, 21:3-4, 219-253 (1982) [Modello di calcolo balistico]. [↩]
5. R. P. Feynman, “Feynman lectures on computation (1984-1986)”, Perseus Books (2000) [↩]
6. C. H. Bennett, “The thermodynamics of computation - a review“, International Journal of Theoretical Physics, 21:12, 905-940 (1982) [Modello di calcolo Browniano; irreversibilità logica e diavoletto di Maxwell]. [↩]
7. C. H. Bennett, “Logical reversibility of computation“, IBM Journal of Res. and Dev., 17:6 525 (1973). [In questo articolo, legato al problema del legame fra calcolo e generazione dei calore esplorato da Landauer, Bennett propose il metodo di “registrazione del risultato ed inversione” e provò che ogni calcolo irreversibile può essere simulato reversibilmente]. [↩]
8. Y. Lecerf, “Machines de Turing réversibles“, Comptes Rendus Hebdomadaires des Séances de L’académie des Sciences 257:2597-2600 (1963); traduzione inglese di M. Frank, “Reversible Turing Machines“. [In questo articolo matematico, non collegato al problema dell’irreversibilità fisica, Lecerf intese concepire una macchina di Turing reversibile. E’ il primo lavoro a proporre il metodo di registrazione della storia del calcolo in modo da “de-calcolarla” in seguito, anche se inizialmente ebbe poco impatto e fu ’scoperto’ solo dopo i risultati di Bennett, forse perché non fu pubblicato in inglese e perché non fu molto sostenuto dallo stesso Lecerf. Ha un difetto minore, cioè l’inverso di un quintuplo read-write-shift è un quintuplo di tipo diverso, cioè shift-read-write]. [↩]
9. L. Szilard, “Über die Entropieverminderung in einem thermodynamischen System bei Eingriffen intelligenter Wesen“, Journal Zeitschrift für Physik, 53, 840-856 (1929); trad. inglese “On the decrease of entropy in a thermodynamic system by the intervention of intelligent beings” in Behavioral Science, 9:4, 301-310 (1964). [↩]
10. D. Deutsch, “Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer“, Proc. Roy. Soc. Lond., A400, 97–117 (1985). [Fondation du modèle de calcul quantique, machine de Turing quantique universelle] [↩]
11. A. R. Calderbank, P. W. Shor, “Good quantum error-correcting codes exist“, Phys. Rev. A 54, 1098-1105 (1996). [↩]