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))))