Computación reversible

Computación reversible es un modelo de computación en el que el proceso computacional es, hasta cierto punto, reversible. En un modelo que usa transiciones deterministas de un estado de la máquina abstracta a otro, una condición necesaria para la reversibilidad es que el diagrama de relación desde un estado (con probabilidades distintas a cero) a sus sucesores debe ser de uno a uno. La computación reversible es una forma de computación no convencional.

Reversibilidad

Hay dos formas principales, y estrechamente relacionadas, de reversibilidad que son de particular interés para este propósito: reversibilidad física y reversibilidad lógica.​

Se dice que un proceso es físicamente reversible si no produce un incremento de entropía, siendo por tanto isoentrópico. Existe un estilo de diseño de circuitos que presenta esta propiedad, llamado lógica con recuperación de carga, circuito adiabático, o computación adiabática. Aunque en la práctica ningún proceso físico no estático puede ser exactamente reversible o isoentrópico, no hay un límite conocido para la aproximación a una reversibilidad perfecta, en sistemas suficientemente aislados de interacciones con entornos externos desconocidos, en los que las leyes físicas que describen la evolución del sistema se conocen con precisión.

Probablemente la mayor motivación para el estudio de tecnologías enfocadas a la implementación de una computación reversible es que ofrecen la que se considera única forma potencial de mejorar el rendimiento energético computacional más allá del límite impuesto por el principio de Landauer​ que establece el mínimo aumento de entropía posible en una operación de bit no reversible. Aunque el límite de Landauer estaba millones de veces por debajo del consumo de las computadoras en los años 2000, y miles de veces en los años 2010,​ los partidarios de la computación reversible argumentan que la diferencia es atribuible en gran parte a efectos acumulados de la arquitectura que magnifican el impacto del límite de Landauer en los diseños prácticos de circuitos, de manera que puede ser difícil para la tecnología práctica el progreso hacia mayores niveles de eficiencia energética sin recurrir a los principios de la computación reversible.​

Relación con la termodinámica

Tal como argumentó por primera vez Rolf Landauer de IBM,​ para que un proceso computacional sea físicamente reversible también debe ser lógicamente reversible. El principio de Landauer es la observación rigurosamente válida de que el borrado de n bits de información conocida debe incurrir siempre en un coste de nkT ln 2 en entropía termodinámica. Se dice que un proceso computacional discreto y determinista es lógicamente reversible si la función de transición que conecta los estados computacionales viejos con los nuevos es una función inyectiva, esto es, los estados lógicos de salida determinan de forma única los estados lógicos de entrada de la operación computacional.

En procesos computacionales no deterministas (en el sentido de que sean probabilísticos o aleatorios), la relación entre estados viejos y nuevos no es una correspondencia unívoca, y la condición para obtener la reversibilidad física se hace más débil, concretamente que el tamaño de un conjunto dado de posibles estados computacionales iniciales no disminuya, en promedio, a medida que la computación progresa.

Reversibilidad física

El principio de Landauer (y de hecho la propia segunda ley de la termodinámica) se pueden entender como una consecuencia lógica directa de la reversibilidad física subyacente, como se refleja en la formulación general hamiltoniana de la mecánica, y más específicamente en el operador unitario de evolución temporal de la mecánica cuántica.

Así pues, la implementación de la computación reversible implica entender cómo caracterizar y controlar la dinámica física de los mecanismos para llevar a cabo operaciones computacionales de forma tan precisa que nos quede una cantidad despreciable de incertidumbre sobre el estado físico completo del mecanismo, para cada operación lógica efectuada. En otras palabras, se necesitaría un seguimiento preciso de la energía activa implicada al llevar a cabo operaciones computacionales dentro de la máquina, y diseñar la máquina de tal forma que la mayoría de esta energía se recupere de forma que se pueda usar para efectuar operaciones subsiguientes, en lugar de permitir que se disipe en forma de calor.

Aunque el logro de este objetivo presenta un desafío importante, implicando el diseño, fabricación y caracterización de nuevos mecanismos computacionales físicos ultra-precisos, no existe actualmente ninguna razón fundamental para pensar que no se pueda lograr este objetivo, el cual permitiría algún día construir computadoras que generen mucho menos de 1 bit de entropía física (y disipar mucho menos de kT ln 2 de energía en forma de calor) para cada operación lógica útil que lleven a cabo internamente.

Actualmente este campo está respaldado por un cuerpo considerable de literatura académica. Una amplia variedad de conceptos de dispositivos reversibles, puertas lógicas, circuitos electrónicos, arquitecturas de procesador, lenguajes de programación y algoritmos se han diseñado y han sido analizados por físicos, ingenieros eléctricos e informáticos teóricos.

Este campo de investigación espera el desarrollo detallado de una tecnología de dispositivos lógicos cuasi-reversibles de alta calidad y económicos, que incluya mecanismos de clocking y sincronización de alta eficiencia energética, o que evite la necesidad de éstos mediante un diseño asíncrono. Este tipo de progreso en la ingeniería será necesario para que el gran cuerpo de investigación teórica sobre la computación reversible encuentre aplicación, permitiendo una tecnología informática real que evite los distintos obstáculos a corto plazo que impiden aumentar la eficiencia energética, incluyendo el límite de Landauer. Esto sólo podrá lograrse mediante la computación reversible, debido a la segunda ley de la termodinámica.

Reversibilidad lógica

Para implementar la computación reversible, estimar los costes y juzgar sus límites, esta puede ser formalizada en términos de circuitos a nivel de puerta. En un modelo simplificado de tales circuitos las entradas (inputs) incurren en un consumo (pero nótese que en las puertas lógicas reales, tal como se implementan en, por ejemplo, elementos tipo CMOS, no ocurre esto). En este entorno de modelización, una puerta lógica NOT es reversible, porque puede ser «desandada». La puerta XOR es irreversible porque sus dos entradas no se pueden reconstruir de forma inequívoca a partir de su única salida. Sin embargo, es posible definir una versión reversible de la puerta XOR, la puerta cuántica CNOT (Controlled NOT), mediante la preservación de una de las entradas. La variante de tres entradas de la puerta CNOT se denomina puerta Toffoli. Esta puerta preserva dos de sus entradas a,b y sustituye la tercera c mediante $c\oplus (a\cdot b)$. Con $c=0$ realiza la función AND, y con $a\cdot b=1$ realiza la función NOT. Así pues, la puerta Toffoli es universal y con ella se puede implementar cualquier función booleana (necesitando un número suficiente de bits auxiliares puestos a cero). De forma más general, las puertas reversibles que consumen su señal de entrada no tienen más entradas que salidas. Un circuito reversible conecta puertas reversibles sin fanouts (múltiples conexiones de salida) ni bucles. Por tanto, tales circuitos contienen igual número de conductores de entrada y de salida, cada uno atravesando un circuito entero. De forma similar, en el modelo computacional de la máquina de Turing, una máquina de Turing reversible es aquella cuya función de transición es reversible, de forma que cada estado de la máquina tiene como mucho un predecesor.

Yves Lecerf propuso una máquina de Turing reversible en un artículo de 1963 al que se prestó escasa atención,​ pero, aparentemente desprevenido de la cuestión del principio de Landauer, no fue más lejos con el tema, dedicando el resto de su carrera básicamente a la etnolingüística. En 1973, Bennett, un investigador de IBM, mostró que se podía hacer una máquina de Turing universal que fuese reversible tanto lógica como termodinámicamente,​ y por tanto capaz, en principio, de realizar tantas operaciones de computación como se quiera por unidad de energía física disipada. Bennett puso la biosíntesis de ARN mensajero como ejemplo físico real de computación reversible. En 1982, Fredkin y Toffoli propusieron la computadora de bolas de billar, un mecanismo que usa esferas sólidas para realizar computaciones reversibles a velocidad finita sin disipar energía, pero que requiere un alineamiento inicial perfecto de las trayectorias de las bolas, y la reseña de Bennett​ consideraba estos paradigmas «brownianos» y «balísticos» para la computación reversible. Aparte de la motivación de una computación energéticamente eficiente, las puertas lógicas reversibles ofrecen mejoras prácticas en transformaciones con manipulación de bits en criptografía y gráficos. Desde los años 80 los circuitos reversibles han sido objeto de atención como componentes en algoritmos cuánticos, y más recientemente en tecnologías de computación fotónica y nanocomputación, en algunos de cuyos dispositivos de conmutación no hay ganancia de señal.

Hay disponibles estudios sobre circuitos reversibles, su construcción y optimización, así como investigaciones recientes.​​​​

Véase también

• Termodinámica de máxima entropía, sobre la interpretación de la incertidumbre en la segunda ley de la termodinámica
• Proceso reversible
• Puerta cuántica
• Computación cuántica
• Deshacer

Bibliografía

• Lange K.-J., McKenzie P., Tapp A. (2000), "Reversible space equals deterministic space", Journal of Computer and System Sciences, 60: 354–367, doi 10.1006/jcss.1999.1672.
• Perumalla K.S. (2014), Introduction to Reversible Computing, CRC Press.
• Vitanyi P.M.B. (2005), "Time, space, and energy in reversible computing", Proceedings of the 2nd ACM conference on Computing frontiers, 435–444. [Review of later theoretical work.]

Enlaces externos

• Introductory article on reversible computing
• First International Workshop on reversible computing
• Recent publications of Michael P. Frank
• Internet Archive backup of the "Reversible computing community Wiki" that was administered by Dr. Frank
• Recent Workshops on Reversible Computation
• Open-source toolkit for reversible circuit design

• Datos: Q185410