ビリヤードボールコンピュータ
FredkinとToffoliによるANDゲートのビリヤードボールモデル。1つのビリヤードボールが入力0-inまたは1-inからゲートに到達すると、デバイスを遮ることなく通過し、0-outまたは1-outから出力されます。しかし、0-inのビリヤードボールが1-inのビリヤードボールと同時に到着した場合、それらはデバイスの左上隅で衝突し、互いの方向を変えてデバイスの右下隅で再び衝突します。その後、一方のボールは1-outから出力され、もう一方のボールは下のAND出力から出力されます。したがって、 AND出力から出力されているボールの存在は、 0-inと1-inのボールの存在を入力として受け取るANDゲートの出力と論理的に一致しています

ビリヤードボールコンピュータは、保存論理回路の一種であり、ニュートン力学に基づく可逆機械コンピュータの理想化されたモデルであり、1982年にエドワード・フレドキンとトマソ・トフォリによって提唱された。[ 1 ]従来のコンピュータのように電子信号を使用する代わりに、ビリヤードボールが緩衝材で作られた摩擦のない環境において、ボールが完璧に跳ね返る球状のビリヤードボールの動きを利用する。これは、計算と物理学における可逆過程の関係を調査するために考案された。

ビリヤードボールを使った回路シミュレーション

このモデルは、ブール回路をシミュレートするために使用できます。ブール回路では、回路の配線はボールが移動する経路に対応し、配線上の信号はその経路上のボールの有無によってエンコードされ、回路のゲートはボールの経路が交差する点でのボールの衝突によってシミュレートされます。特に、ボールの経路とその周囲のバッファを設定することで可逆的なトフォリゲートを形成することができ、そこから他のブール論理ゲートをシミュレートできます。したがって、適切に構成されたビリヤードボールコンピュータは、あらゆる計算タスクを実行するために使用できます。[ 2 ]

他の計算モデルでビリヤードボールをシミュレートする

ビリヤードボールコンピュータは、ブロックセルオートマトンや2次セルオートマトンなど、いくつかの種類の可逆セルオートマトン上でシミュレートできます。これらのシミュレーションでは、ボールは軸に平行な方向に一定速度でのみ移動することが許されます。これは、ビリヤードボールモデルを用いて論理回路をシミュレートする際に既に存在していた仮定です。これらのセルオートマトンシミュレーションでは、ボールとバッファは特定のパターンの生細胞によってシミュレートされ、ボールが移動するフィールドは死細胞領域によってシミュレートされます。[ 3 ]

ビリヤードボールコンピュータ設計に基づく論理ゲートは、ビリヤードボールの代わりにミクティリス・ギノタエという種の生きたソルジャーガニを使って動作するようにも作られている。 [ 4 ] [ 5 ] [ 6 ]

チューリング完全性

2025年、数学者のエヴァ・ミランダとアイザック・ラモスは、2次元ビリヤードがチューリング完全であることを示す論文を発表しました。[ 7 ] [ 8 ]

この研究では、ボールが 1 つだけの古典的な平面ビリヤード システムでも、汎用的な計算が可能であることを示しています。

参照

参考文献

  1. ^ Fredkin, Edward ; Toffoli, Tommaso (1982)、「保守的論理」、International Journal of Theoretical Physics、21 ( 3– 4): 219– 253、Bibcode : 1982IJTP...21..219F、doi : 10.1007/BF01857727、MR  0657156、S2CID  37305161。
  2. ^ Durand-Lose, Jérôme (2002)、「ビリヤードボールモデル内部のコンピューティング」、Adamatzky, Andrew (編)、『衝突ベースコンピューティング』、Springer-Verlag、pp.  135– 160、doi : 10.1007/978-1-4471-0129-1_6、ISBN 978-1-4471-0129-1。
  3. ^ Margolus, N. (1984)、「物理学に似た計算モデル」、Physica D: Nonlinear Phenomena、10 ( 1–2 ): 81–95、Bibcode : 1984PhyD...10...81M、doi : 10.1016/0167-2789(84)90252-5. Wolfram, Stephen (1986) 『セルオートマトン理論と応用』、複雑系に関する先進シリーズ第1巻、World Scientific、pp.  232– 246に転載、 Bibcode : 1986taca.book.....W。
  4. ^郡司幸雄＝ペジオ、西山雄太、アダマツキー・アンドリュー（2011）、「ロバストなソルジャークラブボールゲート」、複雑系、20（2）：93–104、arXiv：1204.1749、Bibcode：2012arXiv1204.1749G、doi：10.25088/ComplexSystems.20.2.93、S2CID 14365421 。
  5. ^ソロン、オリビア（2012年4月14日）「ソルジャーカニの群れを使って作られたコンピューター」Wired。
  6. ^ Aron, Jacob (2012年4月12日)、「カニの群れで動くコンピューター」、New Scientist 、 2012年4月13日時点のオリジナルよりアーカイブ。
  7. ^ミランダ、エヴァ; ラモス、アイザック (2024)、古典ビリヤードは計算できる、arXiv : 2512.19156v2。
  8. ^ Cutts, Elise (2026年1月8日). 「2025年12月の論文まとめ：ビリヤードの計算、ありえない雰囲気、そしてローマ建築：科学の最前線における大きな疑問に関する論文を、毎月手作業でキュレーション」 ReviewerToo . 2026年1月14日閲覧。。
「 https://en.wikipedia.org/w/index.php?title=ビリヤードボールコンピュータ&oldid =1332952510」より取得