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

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

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

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

Описание

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

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

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

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