¿Qué tiene de malo el método de "guardar la entrada" de la computación reversible?

9

Soy un estudiante universitario que recién comienza a leer sobre informática reversible. Sé que, debido al principio de Landauer, los cálculos irreversibles disipan el calor (y los reversibles no). Lo mencioné con mi profesor, que nunca antes había oído hablar de la computación reversible, y estaba teniendo dificultades para entender por qué la teoría de la computación reversible no era trivial.

Su punto era que siempre puede guardar la entrada, es decir, para cualquier función que desee hacer reversible, defina una nueva función f r e v e r s i b l e : { 0 , 1 } n{ 0 , 1 } 2 n (o { 0 , 1 } 2 nF:{0 0,1}norte{0 0,1}norteFrmivmirsyosilmi:{0 0,1}norte{0 0,1}2norte y solo pone 0 s para los últimos n bits de la entrada) que devuelve la salida en los primeros n bits y la entrada en los otros n bits. Luego, para invertir f r e v e r s i b l e , simplemente descarte la salida y devuelva la entrada que guardó.{0 0,1}2norte{0 0,1}2norte0 0nortenortenorteFrmivmirsyosilmi

Mi objeción inmediata fue que esto requiere más memoria que la función original, aunque solo por un factor constante. Sin embargo, restringir la salida a bits parecería restablecer el interés del problema. ¿Es esto lo que generalmente se entiende por computación reversible?norte

Otra objeción parecía ser que cuando descartamos la salida, estamos haciendo algo irreversible que va a disipar el calor. Pero recuperamos correctamente el estado inicial, entonces, ¿cómo podría ser irreversible? No sé lo suficiente de física para entender si lo importante con calor es que todo el cálculo sea reversible, o si cada paso también debe ser reversible, o si esta idea está en el árbol equivocado .

Eli Rose - REINSTATE MONICA
fuente

Respuestas:

12

Hay dos características importantes de la computación reversible que faltan en su discusión sobre la computación reversible:

  1. Una función reversible tiene que ser una biyección, y
  2. La reversibilidad se define en el nivel de las puertas locales, no solo en el nivel global.

En particular, para su extensión de en { 0 , 1 } 2 n{ 0 , 1 } 2 n al copiar, no garantiza la biyección porque no explique qué sucede cuando los últimos n bits de entrada para su función no son 0 n .{0 0,1}norte{0 0,1}norte{0 0,1}2norte{0 0,1}2nortenorte0 0norte

En cuanto al segundo punto, esa es realmente la parte esencial de la computación reversible desde la perspectiva de la física. El proceso físico no puede simplemente "deshacer" el calentamiento a nivel global, por lo tanto, cada puerta debe ser reversible para que el circuito sea reversible en el sentido relevante para la física.

Finalmente, la teoría de la computación reversible no es irrazonablemente complicada, pero definitivamente no es trivial. En particular, hay algunos circuitos que pueden implementarse con estrictamente menos registros / cables de manera no reversible de lo que pueden ser reversiblemente. Sin embargo, el estallido al pasar de no reversible a reversible no es tan malo.

En general, rara vez escucho computación reversible en los cursos clásicos de CS, porque rara vez es relevante para la computación clásica. Sin embargo, es un tema importante en la computación cuántica porque todos los circuitos cuánticos son reversibles y porque uno tiene que manejar con cuidado lo que está en sus cables 'basura' para evitar enredos innecesarios.

Artem Kaznatcheev
fuente
Ajá. Entonces, ¿cuál es la afirmación formal de "cada puerta debe ser reversible"? ¿Requiere que la función de transición de la máquina de Turing sea inyectiva?
Eli Rose - REINSTATE MONICA
2
La computación reversible @EliRose se define en el modelo de puerta, no en el modelo TM. No estoy seguro de si hay una definición razonable en el modelo TM, pero probablemente al menos requeriría que el control finito sea reversible. Entonces, las puertas reversibles significan algo así como la puerta Toffoli .
Artem Kaznatcheev
1
@ArtemKaznatcheev: ¿qué pasa con las máquinas reversibles de Turing (enlace PDF) presentado por Bennett?
Niel de Beaudrap
Los circuitos combinatorios se pueden manejar fácilmente con lógica reversible, pero todos los dispositivos informáticos útiles requieren retroalimentación. Se podría usar una puerta Toffoli para calcular "A y no B", y dos puertas de este tipo se podrían usar para construir un pestillo, pero una vez que se pone en marcha la retroalimentación, la reversibilidad se va por la ventana.
supercat
¿Qué pasa con las TM cuánticas cuyas amplitudes permitidas solo pueden ser 0 o 1. Esa parece una forma razonable de definir una TM reversible.
Marcos Villagra