Billiard-ball computer

Billiard-ball Computerという計算モデルがあると知った。
Billiard-ball computer - Wikipedia, the free encyclopedia
ボールの存在で1と0をあらわし、うまく衝突させることで論理回路を作るというものである。チューリング完全性があるらしい。

具体的には、摩擦がなく完全弾性衝突するという条件下で、二つのボールを入力とみなせば、以下のような衝突でANDを構成することができる。
f:id:wkwkes:20150719021709p:plain

あと、NOTがほしいが、これらはANDほど単純には構成できない。
Conservative logic - Springerを見るとFredkin gateと呼ばれる回路を使えばいいらしい。

そのためにまず、Switch gateと呼ばれる以下の回路を考える。*1
f:id:wkwkes:20150719021925p:plain

左から入力し、右へ出力する時をオレンジで、右から入力し、左へ出力する時を青で表した。

これを4つ用いると以下のようにFredkin gateが構成出来る。
f:id:wkwkes:20150720212255p:plain

代入すると確かめられるが、Fredkin gateの真ん中の出力は、

  • Q=0 のとき (C\wedge P) \vee (\neg C \wedge Q) = C \wedge P
  • P=0 かつ Q = 1のとき (C\wedge P) \vee (\neg C \wedge Q) = \neg C

などとなる。
2つ目の性質からNOTが得られる。

以上でANDとNOTが構成できたので、Billiard-ball Computerがチューリング完全であることが確かめられた。

3DCGを作る環境があったので以上のこと使って、NOTとXORをCGでシミュレートしようと試みた。

物理演算でやろうとしたところ、回路が長くなるとどうしても思い通りの挙動を取らなかったため、シミュレーションは諦めて、理想上のモデルの動く様子を動画にした。

それぞれNOTに対して、1と0を入力した様子を表す。

Fredkin gate を4つ合わせて作ったXORに1と0を入力した様子を表す。レンダリングのミスで見にくいが、たしかに1を出力している。

*1:Switch gateとFredkin gateの構成は一例にすぎず、同じ挙動をとればどんな構成でもいいみたい。