Модель бильярдного шара Фредкина и Тоффоли вентиля И. Когда один бильярдный шар прибывает в ворота через вход 0-in или 1-in , он проходит через устройство беспрепятственно и выходит через 0-out или 1-out . Однако, если бильярдный шар 0-in прибывает одновременно с бильярдным шаром 1-in , они сталкиваются друг с другом в верхнем левом углу устройства и перенаправляют друг друга, чтобы снова столкнуться в нижнем правом углу устройства. Затем один шар выходит через 1-out , а другой шар выходит через нижний выход И. Таким образом, наличие шара, испускаемого из выхода И , логически согласуется с выходом вентиля И, который принимает наличие шара на 0-in и 1-in в качестве входов.
Эта модель может быть использована для моделирования булевых схем , в которых провода схемы соответствуют путям, по которым может перемещаться один из шаров, сигнал на проводе кодируется наличием или отсутствием шара на этом пути, а вентили схемы моделируются столкновениями шаров в точках, где их пути пересекаются. В частности, можно настроить пути шаров и буферы вокруг них так, чтобы сформировать обратимый вентиль Тоффоли , из которого может быть смоделирован любой другой логический вентиль Буля. Следовательно, соответствующим образом сконфигурированные компьютеры с бильярдными шарами могут использоваться для выполнения любой вычислительной задачи. [2]
Моделирование бильярдных шаров в других моделях вычислений
Можно моделировать бильярдные шары на нескольких типах обратимых клеточных автоматов , включая блочные клеточные автоматы и клеточные автоматы второго порядка . В этих симуляциях шарам разрешено двигаться только с постоянной скоростью в направлении, параллельном осям, предположения, которые в любом случае уже присутствовали при использовании модели бильярдных шаров для моделирования логических схем. И шары, и буферы моделируются определенными шаблонами живых клеток, а поле, по которому движутся шары, моделируется областями мертвых клеток в этих симуляциях клеточных автоматов. [3]
Логические вентили, основанные на компьютерных конструкциях с бильярдными шарами, также были созданы для работы с использованием живых крабов-солдат вида Mictyris guinotae вместо бильярдных шаров. [4] [5] [6]
^ Дюран-Лоз, Жером (2002), «Вычисления внутри модели бильярдного шара», в Adamatzky, Эндрю (ред.), Collision-Based Computing , Springer-Verlag, стр. 135–160, doi :10.1007/978-1-4471-0129-1_6, ISBN978-1-4471-0129-1.
^ Марголус, Н. (1984), «Физико-подобные модели вычислений», Physica D: Nonlinear Phenomena , 10 (1–2): 81–95, Bibcode : 1984PhyD...10...81M, doi : 10.1016/0167-2789(84)90252-5. Перепечатано в Вольфрам, Стивен (1986), Теория и применение клеточных автоматов , Расширенная серия по сложным системам, т. 1, World Scientific, стр. 232–246, Bibcode : 1986taca.book.....W.
