ビリヤードボール・コンピュータ
ビリヤードボール・コンピュータ（英: Billiard-ball computer）とは、ニュートン力学に基づく可逆計算モデル。エドワード・フレドキンとトマソ・トフォリによって1982年に提案された[1]。通常のコンピュータは電子を回路に通すことで信号を伝えるが、ビリヤードボール・コンピュータでは摩擦のない理想的なビリヤードボールが衝突しながら運動することで信号を運ぶ。計算と可逆性の関係を考察する上で有用なモデルである。
目次 |
概要 [編集]
ビリヤードボール・コンピュータではビリヤードボールが完全弾性衝突を行うことで計算を実現する。ビリヤードボール・コンピュータは、チューリング完全であるため停止性問題を模倣できる。したがって、ある地点にボールが到達するかは、ニュートン力学の下では決定不能である。
ビリヤードボールを使って論理回路を構成することができる。ボールの通る道筋が回路にあたり、回線上の信号はボールがその場に存在するかどうかで表される。論理ゲートはボールの道筋の衝突する交点になる。特に、箱やパイプを適切に配置することでトフォリゲートを作ることができ、これを使って他のどのような可逆論理ゲートも構成することができる。つまり、適切に設計すればどのような計算でもビリヤードボール・コンピュータ上で行うことができる[2]。
応用 [編集]
セルオートマトン上でビリヤードボールコンピュータをシミュレートすることができる。シミュレーションを行うことのできるのはブロックセルオートマトンや二次セルオートマトンと分類されるもので、まとめて可逆セルオートマトンと呼ばれる。このシミュレータ下ではボールは一定のスピードで常に軸に並行に進む。ボールや論理ゲートはそれぞれに対応したパターンの生きたセルとして配置され、それらが死んだ空のセルの間を移動することで計算を進める[3]。
カニコンピュータ [編集]
神戸大学と西イングランド大学の研究で、ビリヤードボールの代わりにカニを使って論理ゲートを実現したというものがある[4][5][6]。実験に使われたカニは西表島に生息するミナミコメツキガニの仲間(Myctiris guinotae)で、英語で兵隊ガニと呼ばれ、群れて同じ方向に移動する習性がある。群れがぶつかり合流したとき方向が一定に定まることを利用して、論理演算を行うことができる。仕切りで作った交差点に群れを同時に追い立てることで計算を実行する。演算の結果はカニが交差点の先のどの終端にたどり着いたかでわかる。
関連項目 [編集]
脚注 [編集]
- ^ 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, MR657156
- ^ Durand-Lose, Jérôme (2002), “Computing inside the billiard ball model”, in Adamatzky, Andrew, Collision-Based Computing, Springer-Verlag, pp. 135–160.
- ^ 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, 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
- ^ Solon, Olivia (April 14, 2012), “Computer Built Using Swarms Of Soldier Crabs”, Wired.
- ^ Aron, Jacob (2012年4月12日). “Computers powered by swarms of crabs”. New Scientist 2012年4月15日閲覧。
