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

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

Модель більярдного логічного елемента "І" Фредкіна та Тоффолі. Якщо одна більярдна куля потрапляє у вхід 0 або вхід 1, вона безперешкодно проходить через пристрій і виходить через вихід 0 або вихід 1. Але якщо більярдні кулі прибувають одночасно через обидва входи, то вони стикаються між собою у верхньому лівому кутку пристрою і змінюють траєкторії руху так, щоб знову зіткнутися в нижньому правому кутку. Потім одна з куль виходить через вихід 1, а інша - через нижній вихід "І". Таким чином, куля, що виходить із виходу "І", моделює роботу логічного елемента "І" входами якого є вхід 0 та вхід 1.

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

Опис

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

Моделювання

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

Також більярдний комп'ютер можна реалізувати з використанням як більярдних куль живих крабів-солдатів виду Mictyris guinotae^{[en][4][5][6]}.