Modelo de bola de billar de Fredkin y Toffoli de una compuerta AND . Cuando una sola bola de billar llega a la compuerta a través de la entrada 0-in o 1-in , pasa a través del dispositivo sin obstrucciones y sale a través de 0-out o 1-out . Sin embargo, si una bola de billar 0-in llega simultáneamente como una bola de billar 1-in , chocan entre sí en la esquina superior izquierda del dispositivo y se redirigen entre sí para chocar nuevamente en la esquina inferior derecha del dispositivo. Luego, una bola sale a través de 1-out y la otra bola sale a través de la salida AND inferior . Por lo tanto, la presencia de una bola que se emite desde la salida AND es lógicamente consistente con la salida de una compuerta AND que toma la presencia de una bola en 0-in y 1-in como entradas.
Una computadora de bolas de billar , un tipo de circuito lógico conservativo , es un modelo idealizado de una computadora mecánica reversible basada en la dinámica newtoniana , propuesta en 1982 por Edward Fredkin y Tommaso Toffoli . [1] En lugar de utilizar señales electrónicas como una computadora convencional , se basa en el movimiento de bolas de billar esféricas en un entorno libre de fricción hecho de amortiguadores contra los cuales las bolas rebotan perfectamente. Fue ideada para investigar la relación entre la computación y los procesos reversibles en física.
Simulación de circuitos con bolas de billar
Este modelo se puede utilizar para simular circuitos booleanos en los que los cables del circuito corresponden a trayectorias por las que puede viajar una de las bolas, la señal en un cable se codifica por la presencia o ausencia de una bola en esa trayectoria y las puertas del circuito se simulan por colisiones de bolas en los puntos donde se cruzan sus trayectorias. En particular, es posible configurar las trayectorias de las bolas y los amortiguadores que las rodean para formar una puerta Toffoli reversible , a partir de la cual se puede simular cualquier otra puerta lógica booleana. Por lo tanto, se pueden utilizar computadoras de bolas de billar configuradas adecuadamente para realizar cualquier tarea computacional. [2]
Simulación de bolas de billar en otros modelos de computación
Es posible simular computadoras de bolas de billar en varios tipos de autómatas celulares reversibles , incluidos los autómatas celulares de bloque y los autómatas celulares de segundo orden . En estas simulaciones, las bolas solo pueden moverse a una velocidad constante en una dirección paralela al eje, suposiciones que en cualquier caso ya estaban presentes en el uso del modelo de bola de billar para simular circuitos lógicos. Tanto las bolas como los amortiguadores se simulan mediante ciertos patrones de células vivas, y el campo a través del cual se mueven las bolas se simula mediante regiones de células muertas, en estas simulaciones de autómatas celulares. [3]
También se han diseñado puertas lógicas basadas en diseños de computadoras con bolas de billar para que funcionen utilizando cangrejos soldados vivos de la especie Mictyris guinotae en lugar de las bolas de billar. [4] [5] [6]
^ Durand-Lose, Jérôme (2002), "Computación dentro del modelo de bola de billar", en Adamatzky, Andrew (ed.), Computación basada en colisiones , Springer-Verlag, págs. 135-160, doi :10.1007/978-1-4471-0129-1_6, ISBN978-1-4471-0129-1.
^ Margolus, N. (1984), "Modelos de computación similares a los de la física", Physica D: Nonlinear Phenomena , 10 (1–2): 81–95, Bibcode :1984PhyD...10...81M, doi :10.1016/0167-2789(84)90252-5. Reimpreso en Wolfram, Stephen (1986), Teoría y aplicaciones de los autómatas celulares , Serie avanzada sobre sistemas complejos, vol. 1, World Scientific, págs. 232–246, Bibcode :1986taca.book.....W.
^ Solon, Olivia (14 de abril de 2012), "Computadora construida con enjambres de cangrejos soldados", Wired.
^ Aron, Jacob (12 de abril de 2012), "Computadoras alimentadas por enjambres de cangrejos", New Scientist , archivado desde el original el 13 de abril de 2012.
