Бильярдный компьютер

Бильярдный компьютер (англ. Billiard-ball computer) — логическая модель для проведения обратимых вычислений, механический компьютер, основанный на законах движения Ньютона и предложенный в 1982 году Эдвардом Фредкиным и Томмазо Тоффоли[1].

Fredkin and Toffoli Gate billiard ball model of an AND gate. When a single billiard ball arrives at the gate through input 0-in or 1-in, it passes through the device unobstructed and exits via 0-out or 1-out. However, if a 0-in billiard ball arrives simultaneously as a 1-in billiard ball, they collide with each other in the upper-left-hand corner of the device and redirect each other to collide again in the lower-right-hand corner of the device. One ball then exits via 1-out and the other ball exits via the lower AND-output. Thus, the presence of a ball being emitted from the AND-output is logically consistent with the output of an AND gate that takes the presence of a ball at 0-in and 1-in as inputs.

Вместо использования электронных сигналов, как в обычном компьютере архитектуры фон Неймана, он применяет принципы движения бильярдных шаров при отсутствии трения. Бильярдный компьютер может быть использован для изучения связей между обратимыми вычислениями и обратимыми процессами в физике.

Описание

Бильярдный компьютер моделирует булевы логические схемы, используя вместо проводов пути, по которым движутся шары, ограниченные стенками: сигнал кодируется наличием или отсутствием шаров на путях, а логические вентили моделируются при помощи столкновений шаров на пересечениях путей. В частности, можно так подобрать пути шаров, чтобы получить вентиль Тоффоли, универсальный обратимый логический вентиль, с помощью которого можно получить любой другой обратимый логический вентиль. Это означает, что правильно подобранный бильярдный компьютер способен провести любые вычисления[2].

Моделирование

Бильярдный компьютер можно моделировать, используя различные типы обратимых клеточных автоматов, включая блочные и второго порядка. В таких моделях шары движутся с постоянной скоростью вдоль осей координат, чего достаточно для моделирования логических схем. Как шары, так и стенки соответствуют некоторым группам живых (содержащих 1) ячеек, а объемлющее поле заполнено мёртвыми (содержащими 0) ячейками[3].

Также бильярдный компьютер может быть реализован с использованием живых крабов-солдат вида Mictyris guinotae в качестве бильярдных шаров[4][5][6].

Примечания
  1. Fredkin, Edward & Toffoli, Tommaso (1982), Conservative logic, International Journal of Theoretical Physics Т. 21 (3-4): 219–253, DOI 10.1007/BF01857727.
  2. Durand-Lose, Jérôme (2002), Computing inside the billiard ball model, in Adamatzky, Andrew, Collision-Based Computing, Springer-Verlag, с. 135–160, ISBN 978-1-4471-0129-1.
  3. Margolus, N. (1984), Physics-like models of computation, Physica D: Nonlinear Phenomena Т. 10: 81–95, DOI 10.1016/0167-2789(84)90252-5. Reprinted in Wolfram, Stephen (1986), Theory and Applications of Cellular Automata, vol. 1, Advanced series on complex systems, World Scientific, с. 232–246.
  4. Gunji, Yukio-Pegio; Nishiyama, Yuta & Adamatzky, Andrew (2011), Robust Soldier Crab Ball Gate, Complex Systems Т. 20 (2): 93–104, <http://www.complex-systems.com/abstracts/v20_i02_a02.html>.
  5. Solon, Olivia (April 14, 2012), Computer Built Using Swarms Of Soldier Crabs, Wired, <https://www.wired.com/wiredenterprise/2012/04/soldier-crabs/>.
  6. Aron, Jacob (April 12, 2012), Computers powered by swarms of crabs, New Scientist, <https://www.newscientist.com/blogs/onepercent/2012/04/researchers-build-crab-powered.html>.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.