ビリヤードボール・コンピュータとは？わかりやすく解説

ビリヤードボール・コンピュータ（英: Billiard-ball computer）は、ボールの力学的な運動を基にした可逆計算モデルである。エドワード・フレドキンとトマソ・トフォリによって1982年に提案された^[1]。エレクトロニクスによるコンピュータが電流電圧により情報を伝達し、またいわゆる能動素子^[2]を利用して論理演算を行うのに対し、ビリヤードボール・コンピュータでは摩擦のない理想的なビリヤードボールの慣性による等速直線運動と完全弾性衝突による反発が情報を運び論理演算を行う。可逆計算を考察する上で有用なモデルのひとつである。

概要

ビリヤードボール・コンピュータは、摩擦のない理想的なビリヤードボールの慣性による等速直線運動と完全弾性衝突による反発が情報を運び論理演算を行う。

論理回路は次のように構成する。ボールの通る道筋が回路にあたり、回線上の信号はボールがその場に存在するかどうかで表される。論理ゲートはボールの道筋の衝突する交点になる。特に、箱やパイプを適切に配置することでトフォリゲートを作ることができ、これを使って他のどのような可逆論理ゲートも構成することができる。つまり、適切に設計すればどのような計算でもビリヤードボール・コンピュータ上で行うことができる^[3]。

ビリヤードボール・コンピュータはチューリング完全である。したがって一見単純そうではあるけれども、（停止性問題の証明の方法などと同種の手法を利用することで）複雑なコンピュータでは、ある地点をボールが通過することが起こり得るか起こり得ないかは決定不能かもしれない。

応用

セルオートマトン上でビリヤードボールコンピュータをシミュレートすることができる。シミュレーションを行うことのできるのはブロックセルオートマトン（英語版）や二次セルオートマトン（英語版）と分類されるもので、まとめて可逆セルオートマトン（英語版）と呼ばれる。このシミュレータ下ではボールは一定のスピードで常に軸に並行に進む。ボールや論理ゲートはそれぞれに対応したパターンの生きたセルとして配置され、それらが死んだ空のセルの間を移動することで計算を進める^[4]。

以下は似た原理を利用するものに関してであるが、必ずしも可逆ではない。

カニコンピュータ

神戸大学と西イングランド大学（英語版）の研究で、ビリヤードボールの代わりにカニを使って論理ゲートを実現したというものがある^[5]^[6]^[7]。実験に使われたカニは西表島に生息するミナミコメツキガニの仲間(Myctiris guinotae)で、英語で兵隊ガニと呼ばれ、群れて同じ方向に移動する習性がある。群れがぶつかり合流したとき方向が一定に定まることを利用して、論理演算を行うことができる。仕切りで作った交差点に群れを同時に追い立てることで計算を実行する。演算の結果はカニが交差点の先のどの終端にたどり着いたかでわかる。

サンドボックスゲーム

Minecraftのようなサンドボックスゲームや、スーパーマリオメーカーのようなゲームマップコンストラクションソフト等の世界内に論理演算などを実装する際に、ゲーム内でのオブジェクトの衝突など、ビリヤードボール・コンピュータに似た原理が利用される。^[8]

脚注

^ 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 657156
^ トランジスタなどのこと。厳密にはダイオード論理方式（en:Diode logic）などを使えば論理演算自体は受動素子でもできるが、増幅作用のあるトランジスタの併用が必要なため、能動素子を全く使わないコンピュータはあまり現実的ではない。
^ 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日閲覧。
^ https://www.youtube.com/watch?v=bpgiUUFY73g

[1] 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 657156

[2] トランジスタなどのこと。厳密にはダイオード論理方式（en:Diode logic）などを使えば論理演算自体は受動素子でもできるが、増幅作用のあるトランジスタの併用が必要なため、能動素子を全く使わないコンピュータはあまり現実的ではない。

[3] Durand-Lose, Jérôme (2002), “Computing inside the billiard ball model”, in Adamatzky, Andrew, Collision-Based Computing, Springer-Verlag, pp. 135–160 .

[4] 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 .

[5] 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

[6] Solon, Olivia (April 14, 2012), “Computer Built Using Swarms Of Soldier Crabs”, Wired .

[7] Aron, Jacob (2012年4月12日). “Computers powered by swarms of crabs”. New Scientist 2012年4月15日閲覧。

[8] ttps://www.youtube.com/watch?v=bpgiUUFY73g

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

ビリヤードボール・コンピュータとは？わかりやすく解説