Life Game

広い空間と長い時間を使えば, Life Gameで計算機がシミュレート出来るという話は聞くが, そう簡単には納得できない.

Winning Waysを読んでいたら, 記憶装置の実現法が書いてあった. こういう方式らしい.

A, B, C, などが記憶場所で, その上方にブロックを置き, そのブロックまでの距離を記憶している値とする. 従って書き込むにはその数値の分だけブロックを遠ざける手続きを繰り返す. また読み出すにはブロックを近づけ, 0になるまでの回数で知る.

近づけたり塔ざけたりには, いつものようにグライダーを使う. 上の図の縦方向は, 実はグライダーの飛ぶ斜め方向である.

ブロックを近づける方法はこうだ.



左上からA, B2機のグライダーがブロックに近づく. この図をクロック0としよう. 目的はブロックを左上へ動かすことである.

その後, クロック10になると, ブロックに衝突したAがブロックを少し移動して下の図になる.



ブロックの元の位置は赤い枠で示したとおりで, 左へ2, 上へ1移動した. 左と上の距離が違うので, もう一度Bをブロックに衝突させる. その結果が次の図だ. (クロック18)



ブロックの位置は, 上へも左へも3移動した.

一方, ブロックを遠ざけるのは簡単ではない.



上の図(クロック0)では, グライダーは左下から右上へ向かっている. 従ってブロックを右上に動かしたい.

グライダーは10機描いてあるが, 2つの編隊になっている. 第1編隊はA, B, C, D, Eで, 最初にブロックに近づくAのミッションは, ブロックに衝突し, 蜂の巣(beehive)4個からなる養蜂場(bee farm)の形にすることだ.

下がクロック24で, Aの衝突の結果, 養蜂場になったところである.



そこへ近づくB, C, Dの3機のミッションは, それぞれ下, 右, 左の蜂の巣と消滅衝突をすることである. 最後のEが近づき, 上に残った蜂の巣に衝突し, ブロックにする.

クロック77になると, 衝突が治まり, ブロックになるが, 赤い枠の元の位置からは左へ1, 上へ２移動した.



すぐ近くに第2編隊のF, G, H, I, Jが接近している. これらは前の編隊とは左下から右上に掛けての45度の線について対称である. Fが養蜂場を作り, G, H, Iが余分の蜂の巣を片付け, 最後にJがブロックに戻す. (164クロック)



これでブロックは右上に(1,1)だけ移動した. しかし先に書いた近づける方は(3,3)だけ移動したので, 遠ざける方は同じことをあと2回やらなければならない. つまり30機をもって押し返すという筋書きである.

ところで, 遠ざける方の最初の図だが, Winning Ways第4巻953ページにある図は, シミュレートしてみると, うまく行かないのである. いろいろテストしてみて, CとEを元の図より1ピクセル下へ, HとJは1ピクセル左へ移動してある. これならうまくいくことがシミュレーションで確認してある.

Life Game

前回のこのブログでは, キックバックを利用した希薄銃の実現法を述べた. その少し先にConwayはグライダーの列から連続する3機のグライダーを消滅させる方法を書いている.

120クロック毎に打ち出されるグライダーの列があるとする.

(i)   1機目のグライダーが別のグライダーでキックバックされ, 元の方向へ戻る．
(ii)  2機目が戻ってきた1機目と正面衝突し, ブロックを生じる.
(iii) 3機目がこのブロックに衝突して消える.

これを読んでなるほどと思ってもよいが, やはりシミュレートしてみたい.



この図はグライダーの列が右上から左下へ飛んでいるところで，先頭のaがまさにキッバックされる位置にいる. 後続のbとcは120クロック離れている．dはキックバックを仕掛けるグライダーで, 左上から右下へ飛んでいる. その先にイーターEを置く.

この時点のクロックを0としよう.

次の図は, クロック8で, キックバックが終わり，1機目(a)が向きを反転したところである.



この2つの図の間の様子は前回のブログのキックバックの遷移図の0から8である.

その後しばらくしてクロック60では1機目(a)と2機目(b)があわや衝突寸前になる.



クロック66でこの2機はブロックになる.



次はクロック172で, 3機目(c)がブロックに迫る.



クロック176ではブロックと機体の破片だけになり, 次のクロックでは何もなくなる.



この図で右上に見えるeはちょうどキックバックのグライダーが来るのでなければ, 消えることなく左下へ進む.

これで安心して先が読める. この機構を利用し, グライダー列による情報を複製する話にるのだが,  それも結構複雑で, Life Gameは万能とはいえ素子があまり単純な故であろう.

うまく動くシミュレーションを眺めるのは楽しい.

Life Game

Life Gameはuniversalであるといわれる. つまり計算機を構築する部品がいろいろ考案され, それを組合せればよいという議論らしい. ただ, von Neumannの自己増殖機械みたいに, 縦何セル, 横何セル, 遺伝子のセル何個で出来るというような具体的な数値がないので, これで時間さえかければ解けるよね, といわれている程度にしか納得できない.

さて, そういう部品の一つに希薄銃(thin gun)というのがある. Life Gameで作る計算機の情報(信号)は, 2次元世界を飛び回わるグライダーだが, グライダー銃は30クロックごとにグライダー1個を発射し, これでは濃すぎる(多すぎる)ので, もっと間引いたグライダー列を作りたい. その機構が希薄銃である. 本当に出来るかなと思いやってみた.

次の図が希薄銃の様子を示す. これはProcessingのシミュレータで動いているもののある時点でのスナップショット(をPostScriptで書き直したもの)である.



赤い丸で数字を囲ったのが3個所あり, それぞれグライダー銃がグライダーを発射する場所だ. 左上のグライダー銃0は, 右下へグライダーを出し続ける. 図に見えるグライダーに先頭からa, b, c,...と標識を付ける.

(グライダー銃はもっと複雑な形だが, こんな大きなものをシミュレータに書き込むと, 広い面積が必要になるので, このシミュレーションでは, シミュレータがどのタイミングにどの位置でどの方向へグライダーを発射するかのシナリオに従ってグライダーを発生する.)

右端の中ほどに1番のグライダー銃があり, これは左上へグライダーを送る. こちらのグライダーをf, g, h,...とする.

これらグライダーの2列の間で, eというグライダーが右上に向っている. これはConwayのいうキックバックで, eは2つのグライダー列の間を右上と左下で往復する. eは間もなくfと接触し, eとfは消滅し, eと逆向きのグライダーが出現する.

そうして戻ってくるキックバックのグライダーは, タイミング的には0番のグライダー列のdと接触し, dを消し, また右上へキックバックする.

eが前回右上に向う前に, 左下へ向っていたグライダーはaの1機前のグライダーに衝突し, 右上へキックバックしていたのである. 0番のグライダー列は, したがって, a, b, cとキックバック地点を通過した後, dは消滅し, その後また3個通過し, 1個消滅する,...  を繰り返す.

左上へ進んでいる1番のグライダー列も, 4個に1個はキックバックで消えるが, 3個はキックバックされずに通過する. しかしキックバック後のグライダーは要らないから, Eと書いたイーターで吸い込む.

上の図には中央あたりに2番のグライダー銃があり, グライダーを左下へ発射している. そこへキックバックを回避してきた0番のグライダー列が近づく. この衝突は, 両者が消滅する位相であって右下へ通過するグライダーはないが, すでにキックバックで消えた0番グライダーに対応するホールでは, 2番のグライダーは衝突を免れ, 左下へ進む. 図の左下のグライダーiは, そのように抜けてきたものである. その後3機の2番のグライダーは, キックバックを免れた0番のグライダーのために消滅してホールになる. jはaの前のグライダーがホールだったため, 抜けてきたのである.

このようにして, キックバックで3/4になった0番のグライダー列により, 1/4に希薄になったグライダー列が発生出来る.

次は, キックバックの起こし方だ. グライダーの位置決めのため, ある方向に進むグライダーの4位相パターンのそれぞれに, 注目点を決めよう.



この右下へ移動するグライダーの図で, 左上, 右上, 左下, 右下が赤字のようにそれぞれ位相0,1,2,3で, 一番進行方向に近い場所を注目点とする. 位相0はいわゆるハッカーエンブレムの形で, 4クロック後には右へも下へも1セル分移動する.

Conwayの示すキックバック機構の図は以下の通り.



白黒を問わず, 丸が生きているセルである. 下の数字0から8は相対クロックだ. クロック0では上に左下へ進むグライダー, 下に右下へ進むグライダーが見える. 黒丸は次のクロックでも生き残るセル. 白丸は次には消えるセル, 点は今は死んでいるが, 次のクロックで生まれるセルだ.

この反応を経て, クロック6,7,8では右上へキックバックされるグライダーが形成され, 8が丁度0と180度逆転している. つまり, ターンで8クロックかかるわけだ.

グライダーの列は30クロック間隔なので, 向こうでもう一度キックバックされ, 30の倍数で戻ってくれば, 後続のグライダーとうまく衝突出来る. こちらのターンで8, 向こうで8かかると, 16クロック. 1歩進むのに4クロックかかるから, その距離往路と復路で8クロック. 16足す何倍かの8クロックの和で30の倍数になるのは,

30=16+8*1.75
60=16+8*5.5
90=16+8*9.25
120=16+8*13

だから, 最後のが解で13ステップの距離を往復し, 片側で120クロック毎にキックバックを起すことになる. 120はグライダー間隔30クロックも4倍なので, 4機に1機が犠牲になる.

この計算から分かるように, 240クロックでもグライダー間隔を28にすればキックバック出来る. Conwayの記述には, 1/Nに希釈出来るが, Nは4の倍数でなければならないとある.

先ほどの図で, グライダー0とキックバックしたとして, 次のグライダー1とのキックバックはどこだろうか. タイミング0の下のグライダーの注目点(下の3x3の正方形の右下)をx=0,y=0とすると, タイミング8の右上に出発しようとするグライダーの注目点はx=0,y=5である(yは上向きに測る.)

次の衝突のタイミング0は13セル間隔離れているから, x=13, y=18, つまりタイミング0の上のグライダーの注目点がそこである. 従って, その時点で1番のグライダーの注目点は, 0の下のグライダーと180度回転した形で, xが1少なく、yが4多い. x=12, y=22にグライダーがあれば良い. そのタイミングでグライダーを発射するように1番のグライダー銃を配置する. または, xとyを1ずつ遠ざけると, 発射の位相を4早める.

キックバックの図を描くプログラムを利用して, 2個のグライダー消滅の様子も描いてみよう.



この図のように, 左上から来るグライダー(下)と右上から来るの(上)とが, この位置で出会うと4クロック後に消滅する. 右上の2番から出続けるグライダーは, 左上のグライダーがあると消滅し, ないと飛び続けるから, これをNot回路という.

シミュレータを使うノウハウも結構たまったので, またいろいろ遊べそうだ.

Life Game

前回のブログの最後. Schemeの実装はTAOCPのアルゴリズムそのもののコピーで, 実はもっと関数プログラムらしく書きたかった. 書き直したのが以下のプログラムである. ある変数を後段で1回しか使わぬなら, 直接使う場所の書き込んである.

(define (b x- x x+)
 (define (and a b) (fix:and a b))
 (define (or a b) (fix:or a b))
 (define (xor a b) (fix:xor a b))
 (define (lsh a b) (fix:lsh a b))
 (let* ((a0 (and x- x+)) (b0 (xor x- x+)) (c0 (xor x b0))
   (d0 (lsh c0 -1)) (c1 (lsh c0 1)) (e0 (xor c1 d0))
   (f1 (or (and b0 e0) (and c1 d0))) (c4 (or (and x b0) a0))
   (b1 (lsh c4 1)) (c5 (lsh c4 -1)))
  (and (xor (or (and b1 c5) (or a0 f1))
  (or (and a0 f1) (or b1 c5)))
  (or (xor b0 e0) x))))

このプログラムは, fixnumでも動くが, fixnumは24ビットしかないので, 実用的には長さが自由なbit-string型の方を使いたい. それに対処すべく, 上のプログラムでは, and, or等は別に定義してある.

MIT Schemeのreference manualでBit Stringを見ると, bit-string-and, bit-string-or, bit-string-xorはあるが, シフトはない. そこでシフトはbit-substringとbit-string-append使って実装することになる.

(define (bit-string-lsh a c)
 (if (>= c 0)
  (bit-string-append (make-bit-string c #f)
   (bit-substring a 0 (- (bit-string-length a) c)))
  (bit-string-append
   (bit-substring a (- c) (bit-string-length a))
   (make-bit-string (- c) #f))))

(define bs (unsigned-integer->bit-string 12 #b111010010111))
 =>#*111010010111  ;12ビットのテスト用bit stringを作る.
(bit-string-lsh bs 2) => #*101001011100 ;左シフト
(bit-string-lsh bs -2) => #*001110100101 ;右シフト

こんな具合いである.

Life Game

前回の算法はセル1個ごとに次ステップの値を計算するものであった.

通常の計算機は, 1ビットCPUのconnection machineと違って, 語の処理が出来るから, セルの1行について計算したいとだれでも思うであろう.

前回の演習問題の後半はその行ごと処理である.

ある行xと上の行x^-と下の行x⁺からその行の次のステップの値が計算したい. 出来そうでもあり, 無理そうでもある. アルゴリズムは次の通り.

a←x^-&x⁺ (=z₃), b←x^-⊕x⁺ (=z₄), c←x⊕b, d←c»1 (=z₆),
c←c«1 (=z₂), e←c⊕d, c←c&d, f←b&e, f←f | c (=z₇), e←b⊕e (=z₈), c←x&b, c←c | a, b←c«1 (=z₅), c←c»1 (=z₁), d←b&c, c←b | c,
b←a&f, f←a | f, f←d | f, c←b | c,
f←f⊕c (=S₁(z₁,z₃,z₅,z₇)), e←e | x, f←f&e.
これをグライダーでやってみよう.


図のように, このグライダーは右下へ進む.
  001000 x^-
  000100 x
  011100 x⁺
  000000
xの行の計算は次のように進む.
a 001000 x^-&x⁺ (=z₃)
b 010100 x^-⊕x⁺ (=z₄)
c 010000 x⊕b (=x_nw⊕x_w⊕x_sw)
d 001000 c»1 (=z₆)
c 100000 c«1 (=z₂)
e 101000 c⊕d (=z₂⊕z₆)
c 000000 c&d (=z₂&z₆)
f 000000 b&e (=z₄&(z₂⊕z₆))
f 000000 f | c ((z₄&(z₂⊕z₆))∨(z₂&z₆)=z₇)
e 111100 b⊕e (=z₄⊕z₂⊕z₆=z₈)
c 000100 x&b (=x&(x^-⊕x⁺))
c 001100 c | a (=(x&(x^-⊕x⁺))∨(x^-&x⁺))
b 011000 c«1 (=z₅)
c 000110 c»1 (=z₁)
d 000000 b&c (S₁の計算開始 b=z₅ c=z₁ a=z₃ f=z₇)
c 011110 b | c
b 000000 a&f
f 001000 a | f
f 001000 d | f
c 011110 b | c
f 010110 f⊕c (=S₁(z₁,z₃,z₅,z₇)
e 111100 e | x (= x∨ z₈)
f 010100 f&e

1ステップ後の配列は以下の通り.
  000000
  010100
  001100
  001000

MIT Schemeのfixnum演算を使った実装は以下の通り.

(define (b x- x x+)
(let* ((a) (b) (c) (d) (e) (f))
 (set! a (fix:and x- x+)) (set! b (fix:xor x- x+))
 (set! c (fix:xor x b)) (set! d (fix:lsh c -1))
 (set! c (fix:lsh c 1)) (set! e (fix:xor c d))
 (set! c (fix:and c d)) (set! f (fix:and b e))
 (set! f (fix:or f c)) (set! e (fix:xor b e))
 (set! c (fix:and x b)) (set! c (fix:or c a))
 (set! b (fix:lsh c 1)) (set! c (fix:lsh c -1))
 (set! d (fix:and b c)) (set! c (fix:or b c))
 (set! b (fix:and a f)) (set! f (fix:or a f))
 (set! f (fix:or d f)) (set! c (fix:or b c))
 (set! f (fix:xor f c)) (set! e (fix:or e x))
 (set! f (fix:and f e)) f))

Life Game

この所 TAOCPのアルゴリズムの解説ブログの気味があるが....

John Conwayが発明したとされるLife Gameは, 1970年にMartin GardnerがScientific American誌で紹介し, 爆発的に広まった. 私もそのScientific American誌のコラムを読んだ時は興奮した. その時からしばらく, 多くの計算時間がグライダーやグライダーガンの発見に費やされたという.

要するにMoore近傍, 状態0と1のセルオートマトンで, 中央のセルが0の時, 周囲の和が3なら1, それ以外は0. 中央が1の時, 周囲の和が2か3なら1, それ以外は0という遷移規則である.もっとも研究されたセルオートマトンである.

TAOCPでのLife Gameの記述に興味がある. まず遷移規則は(演習問題7.1.3-167)
f(x_nw,...,x,...,x_se)=[2<x_nw+x_n+x_ne+x_w+1/2x+x_e+x_sw+x_s+x_se<4]
である. xは中央のセル, x_nwはxの北西のセルのように読む.
[boole式]は, Iverson bracketで, 中のboole式が真なら1, 偽なら0を表す. xが0なら, 和が3の時だけ真だ. xが1なら, 1/2があるので, 和が2.5と3.5の時真になる; つまり周囲の和が2か3ということだ.

この遷移式fを26個のboole連鎖で表せるという. どうするか. 加算するには全加算器が必要. 全加算器
(z₁z₀)₂=x₁+x₂+x₃
は5個のboole演算で実現出来る. すなわち
x₄=x₁⊕ x₂,
z₀=x₅=x₃⊕ x₄;
x₆=x₃∧ x₄,
x₇=x₂∧ x₂,
z₁=x₆∨ x₇.
z₀はx₁, x₂, x₃の排他論理和だからこうであろう. z₁は, xの2つが1なら1なので, x₇はx₁x₂が共に1の時, x₄はx₁とx₂のいずれかが1だから, x₆はとx₃とx₁かx₂が共に1の時で, その論理和でz₁が得られる.

さて
(z₁z₂)₂=x_nw+x_w+x_sw,
(z₃z₄)₂=x_n+x_s,
(z₅z₆)₂=x_ne+x_e+x_se,
(z₇z₈)₂=z₂+z₄+z₆,
f=S₁(z₁,z₃,z₅,z₇)∧(x∨z₈),
where
S₁(x₁,x₂,x₃,x₄)=((x₁∨x₂)∨(x₃∧x₄))⊕((x₁∧x₂)∨(x₃∨x₄)).
でfが計算出来る. boole演算の個数は全加算器(5x3), 半加算器(2), S₁(7), それに最後の∧と∨で合計26になる.

これでfが計算出来る理由は次のようだ.
(z₁z₂)₂=x_nw+x_w+x_swからz₂は左の列のパリティである. z₁は左の列の1が2個か3個あることを示す. 同様にz₄は, 中の列の上下のセルのパリティ, z₃は, 中の列に1が2個あることを示す. z₆とz₅についても同様である.

(z₇z₈)₂=z₂+z₄+z₆から, z₈はxを除いた全体のパリティである. またz₇は, 各列のパリティの和が2か3かを示す.

ところで対称関数S₁は, 4個の引数のうち, 1が1個の時に限り1を返す. 従ってS₁(z₁,z₃,z₅,z₇)が1になるのは,
1. 左の列だけに1が2個か3個あるか,
2. 中の列に1が2個あるか,
3. 右の列に1が2個か3個あるか,
4. 列のパリティの和が2か3かのいずれかの時である.
1の場合なら, 左に1が2個か3個あるだけで, 他は0である.
2なら, 中に1が2個あるだけ, 3なら右の列に2個か3個あるだけだ.
4の場合はどうか. 他の列の1の数は0個か1個である. パリティの和が2以上だから, 1が1個の列が2列か3列あるわけで, やはり1の数は全体で2個か3個である.

xが1なら, 周りに2個か3個の1があればxは生きるからこれでOKだ. xが0なら, z₈のパリティが1なら, 周りに3個の1があることになり, xは1になれる.
これがこの計算のからくりであった.

私のSchemeでの実装は次の通り.

(define (f xnw xn xne xw x xe xsw xs xse)
  (define (and x y) (* x y))
  (define (or x y) (quotient (+ x y 1) 2))
  (define (xor x y) (modulo (+ x y) 2))
  (define (fa x1 x2 x3)
   (let* ((x4 (xor x1 x2)) (x6 (and x3 x4)) (x7 (and x1 x2)))
    (cons (or x6 x7) (xor x3 x4))))
  (define (ha x1 x2)
   (cons (and x1 x2) (xor x1 x2)))
  (define (s1 x1 x2 x3 x4)
   (xor (or (or x1 x2) (and x3 x4))
        (or (and x1 x2) (or x3 x4))))
  (let* ((z12 (fa xnw xw xsw)) (z1 (car z12)) (z2 (cdr z12))
         (z34 (ha xn xs)) (z3 (car z34)) (z4 (cdr z34))
         (z56 (fa xne xe xse)) (z5 (car z56)) (z6 (cdr z56))
         (z78 (fa z2 z4 z6)) (z7 (car z78)) (z8 (cdr z78)))
   (and (s1 z1 z3 z5 z7) (or x z8))))