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

Перейти к навигацииПерейти к поиску
Модель бильярдного логического элемента "И" Фредкина и Тоффоли. Если один бильярдный шар попадает во вход 0 или вход 1 он беспрепятственно проходит через устройство и выходит через выход 0 или выход 1. Но если бильярдные шары прибывает одновременно через оба входа, то они сталкиваются друг с другом в верхнем левом углу устройства и изменяют траектории движения так, чтобы снова столкнуться в правом нижнем углу. устройства. Затем один из шаров выходит через выход 1, а другой шар выходит через нижний выход "И". Таким образом, шар, выходящий из выхода "И", моделирует работу логического элемента "И" входами которого являются вход 0 и вход 1.

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

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

Описание

Бильярдный компьютер моделирует булевы логические схемы, используя вместо проводов пути, по которым движутся шары, ограниченные стенками: сигнал кодируется наличием или отсутствием шаров на путях, а логические вентили моделируются при помощи столкновений шаров на пересечениях путей. В частности, можно так подобрать пути шаров, чтобы получить вентиль Тоффоли, универсальный обратимый логический вентиль, с помощью которого можно получить любой другой обратимый логический вентиль. Это означает, что правильно подобранный бильярдный компьютер способен провести любые вычисления[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, Bibcode:1982IJTP...21..219F, doi:10.1007/BF01857727, MR 0657156.
  2. Durand-Lose, Jérôme (2002), "Computing inside the billiard ball model", in Adamatzky, Andrew (ed.), Collision-Based Computing, Springer-Verlag, pp. 135—160, ISBN 978-1-4471-0129-1.
  3. Margolus, N. (1984), "Physics-like models of computation", Physica D: Nonlinear Phenomena, 10: 81—95, Bibcode:1984PhyD...10...81M, doi:10.1016/0167-2789(84)90252-5. Reprinted in Wolfram, Stephen (1986), Theory and Applications of Cellular Automata, Advanced series on complex systems, vol. 1, World Scientific, pp. 232—246.
  4. Gunji, Yukio-Pegio; Nishiyama, Yuta; Adamatzky, Andrew (2011), "Robust Soldier Crab Ball Gate", Complex Systems, 20 (2): 93—104, arXiv:1204.1749, Bibcode:2012arXiv1204.1749G, Архивировано 21 сентября 2017, Дата обращения: 30 сентября 2017 Источник. Дата обращения: 30 сентября 2017. Архивировано 21 сентября 2017 года..
  5. Solon, Olivia (2012-04-14), "Computer Built Using Swarms Of Soldier Crabs", Wired, Архивировано 14 марта 2014, Дата обращения: 30 сентября 2017 Источник. Дата обращения: 30 сентября 2017. Архивировано 14 марта 2014 года..
  6. Aron, Jacob (2012-04-12), "Computers powered by swarms of crabs", New Scientist, Архивировано 13 апреля 2012, Дата обращения: 30 сентября 2017 Источник. Дата обращения: 30 сентября 2017. Архивировано 13 апреля 2012 года..