Бильярдный компьютер
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/13/Toffoli_BilliardBall-ru.svg/400px-Toffoli_BilliardBall-ru.svg.png)
Бильярдный компьютер (англ. Billiard-ball computer) — логическая модель для проведения обратимых вычислений, механический компьютер, основанный на законах движения Ньютона и предложенный в 1982 году Эдвардом Фредкиным и Томмазо Тоффоли[англ.][1].
Вместо использования электронных сигналов, как в обычном компьютере архитектуры фон Неймана, он применяет принципы движения бильярдных шаров при отсутствии трения. Бильярдный компьютер может быть использован для изучения связей между обратимыми вычислениями и обратимыми процессами в физике.
Описание
[править | править код]Бильярдный компьютер моделирует булевы логические схемы, используя вместо проводов пути, по которым движутся шары, ограниченные стенками: сигнал кодируется наличием или отсутствием шаров на путях, а логические вентили моделируются при помощи столкновений шаров на пересечениях путей. В частности, можно так подобрать пути шаров, чтобы получить вентиль Тоффоли, универсальный обратимый логический вентиль, с помощью которого можно получить любой другой обратимый логический вентиль. Это означает, что правильно подобранный бильярдный компьютер способен провести любые вычисления[2].
Моделирование
[править | править код]Бильярдный компьютер можно моделировать, используя различные типы обратимых клеточных автоматов, включая блочные и второго порядка. В таких моделях шары движутся с постоянной скоростью вдоль осей координат, чего достаточно для моделирования логических схем. Как шары, так и стенки соответствуют некоторым группам живых (содержащих 1) ячеек, а объемлющее поле заполнено мёртвыми (содержащими 0) ячейками[3].
Также бильярдный компьютер может быть реализован с использованием живых крабов-солдат вида Mictyris guinotae в качестве бильярдных шаров[4][5][6].
Примечания
[править | править код]- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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 года..
- ↑ Solon, Olivia (2012-04-14), "Computer Built Using Swarms Of Soldier Crabs", Wired, Архивировано 14 марта 2014, Дата обращения: 30 сентября 2017 Источник . Дата обращения: 30 сентября 2017. Архивировано 14 марта 2014 года..
- ↑ Aron, Jacob (2012-04-12), "Computers powered by swarms of crabs", New Scientist, Архивировано 13 апреля 2012, Дата обращения: 30 сентября 2017 Источник . Дата обращения: 30 сентября 2017. Архивировано 13 апреля 2012 года..