ビリヤードボール・コンピュータ

ビリヤードボール・コンピュータ（）は、ボールの力学的な運動を基にした可逆計算モデルである。エドワード・フレドキンとトマソ・トフォリによって1982年に提案された。エレクトロニクスによるコンピュータが電流電圧により情報を伝達し、またいわゆる能動素子を利用して論理演算を行うのに対し、ビリヤードボール・コンピュータでは摩擦のない理想的なビリヤードボールの慣性による等速直線運動と完全弾性衝突による反発が情報を運び論理演算を行う。可逆計算を考察する上で有用なモデルのひとつである。
概要.
ビリヤードボール・コンピュータは、摩擦のない理想的なビリヤードボールの慣性による等速直線運動と完全弾性衝突による反発が情報を運び論理演算を行う。
論理回路は次のように構成する。ボールの通る道筋が回路にあたり、回線上の信号はボールがその場に存在するかどうかで表される。論理ゲートはボールの道筋の衝突する交点になる。特に、箱やパイプを適切に配置することでトフォリゲートを作ることができ、これを使って他のどのような可逆論理ゲートも構成することができる。つまり、適切に設計すればどのような計算でもビリヤードボール・コンピュータ上で行うことができる。
ビリヤードボール・コンピュータはチューリング完全である。したがって一見単純そうではあるけれども、（停止性問題の証明の方法などと同種の手法を利用することで）複雑なコンピュータでは、ある地点をボールが通過することが起こり得るか起こり得ないかは決定不能かもしれない。
応用.
セルオートマトン上でビリヤードボールコンピュータをシミュレートすることができる。シミュレーションを行うことのできるのはやと分類されるもので、まとめてと呼ばれる。このシミュレータ下ではボールは一定のスピードで常に軸に並行に進む。ボールや論理ゲートはそれぞれに対応したパターンの生きたセルとして配置され、それらが死んだ空のセルの間を移動することで計算を進める。
以下は似た原理を利用するものに関してであるが、必ずしも可逆ではない。
カニコンピュータ.
神戸大学との研究で、ビリヤードボールの代わりにカニを使って論理ゲートを実現したというものがある。実験に使われたカニは西表島に生息するミナミコメツキガニの仲間("Myctiris guinotae")で、英語で兵隊ガニと呼ばれ、群れて同じ方向に移動する習性がある。群れがぶつかり合流したとき方向が一定に定まることを利用して、論理演算を行うことができる。仕切りで作った交差点に群れを同時に追い立てることで計算を実行する。演算の結果はカニが交差点の先のどの終端にたどり着いたかでわかる。
サンドボックスゲーム.
Minecraftのようなサンドボックスゲームや、スーパーマリオメーカーのようなゲームマップコンストラクションソフト等の世界内に論理演算などを実装する際に、ゲーム内でのオブジェクトの衝突など、ビリヤードボール・コンピュータに似た原理が利用される。