格子状のセルと単純な規則からなる、離散的計算モデルである。 計算可能性理論、数学、理論生物学などの研究で利用される。 非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。 (wikipedia 2011/12/18)
百聞は一見にしかず，プログラムでセルオートマトンの美しさを体験してみましょう．
セルオートマトンのプログラムを書くには，CellTurtleを使います。以下のプログラムを実行して，タートルの動きを見てみましょう．
1: /* 2: * CellSample.java 3: * 1次元セルオートマトンのサンプルプログラム 4: * Created on 2011/12/16 5: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 6: */ 7: public class Cell1DSample extends Turtle { 8: 9: public static void main(String[] args) { 10: Turtle.startTurtle(new Cell1DSample()); 11: } 12: 13: public void start() { 14: window.setSize(800, 600); 15: hide(); 16: 17: // セルタートル, 赤いタートル 初期位置(10, 10) 右向き 18: CellTurtle ct = new CellTurtle(10);// 大きさ10 19: 20: // 種の行を書く 21: ct.fd(10); 22: ct.mark(); 23: ct.bk(10); 24: ct.right(1); 25: 26: // 五行の処理を行う 27: for (int j = 0; j < 5; j++) { 28: // 一行の処理を行う 29: for (int i = 0; i < 20; i++) { 30: if (!ct.isMarked(7) && !ct.isMarked(4) && ct.isMarked(1)) { 31: ct.mark(); 32: } 33: ct.fd(1); 34: } 35: ct.bk(20); 36: ct.right(1); 37: } 38: } 39: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、Cell1DSampleプログラムが実行できます。
タートルの操作は基本的には同じですが，fd(x)の命令では，１ドットではなくて，１コマ進みます． １コマの大きさは，new CellTurtle(x)のところのxで指定します．
セルオートマトンの１行目は「種」です．一つだけ黒いセルを作ります. mark()メソッドで足元を黒いセルにすることができます．
2行目からの処理では，isMarkメソッドを使って前の行のセルが黒かどうか調べて，ルールにマッチするときにmarkをつけています．
isMarkメソッドの引数1, 4, 7については下記を参照のこと．
(「CellTurtleで利用できる命令＞位置について」にも同様の解説があります．)
１次元のセルオートマトンでは，前の行の3つのセルのパターンからそのセルが白か黒かを決めます． 3つのセルの組み合わせは2の3乗=8パターンあるので，その8パターンについてのルールが決まっている必要があります． それらのパターンは，例えば以下のような具合です．（各ルールに組み合わせの番号がついています）
上図の250番のルールで示されるセルオートマトンを，以下のプログラムで実装してみます．
1: /* 2: * CellSample.java 3: * 1次元セルオートマトンのサンプルプログラム 4: * Created on 2011/12/16 5: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 6: */ 7: public class Cell1DSample2 extends Turtle { 8: 9: public static void main(String[] args) { 10: Turtle.startTurtle(new Cell1DSample2()); 11: } 12: 13: public void start() { 14: window.setSize(800, 600); 15: hide(); 16: 17: int len = 21; 18: 19: // セルタートル, 赤いタートル 初期位置(10, 10) 右向き 20: CellTurtle ct = new CellTurtle(10);// 大きさ10 21: 22: // 種の行を書く 23: ct.fd(len / 2); 24: ct.mark(); 25: ct.bk(len / 2); 26: ct.right(1); 27: 28: // 五行の処理を行う 29: for (int j = 0; j < len; j++) { 30: // 一行の処理を行う 31: for (int i = 0; i < len; i++) { 32: if (ct.isMarked(7) && ct.isMarked(4) && ct.isMarked(1)) {// ■■■ 33: ct.mark(); 34: } else if (ct.isMarked(7) && ct.isMarked(4) && !ct.isMarked(1)) {// ■■□ 35: ct.mark(); 36: } else if (ct.isMarked(7) && !ct.isMarked(4) && ct.isMarked(1)) {// ■□■ 37: ct.mark(); 38: } else if (ct.isMarked(7) && !ct.isMarked(4) && !ct.isMarked(1)) {// ■□□ 39: ct.mark(); 40: } else if (!ct.isMarked(7) && ct.isMarked(4) && ct.isMarked(1)) {// □■■ 41: ct.mark(); 42: } else if (!ct.isMarked(7) && ct.isMarked(4) && !ct.isMarked(1)) {// □■□ 43: } else if (!ct.isMarked(7) && !ct.isMarked(4) && ct.isMarked(1)) {// □□■ 44: ct.mark(); 45: } else if (!ct.isMarked(7) && !ct.isMarked(4) 46: && !ct.isMarked(1)) {// □□□ 47: } 48: ct.fd(1); 49: } 50: ct.bk(len); 51: ct.right(1); 52: } 53: } 54: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、Cell1DSample2プログラムが実行できます。
8パターンのルールの組み合わせなので，全部で256パターンのルールがあることになります．
どうでしょう？似ていませんか？
セルオートマトンを２次元に拡張することができます。
２次元のセルオートマトンでは，あるセルの近傍にある４つのセル（上下左右）のパターンを読み取り，次のターンのそのセルの状態を決めます。
以下，すべてのセルに対して，黒いセルが見つかったらその近傍の４つのセルを反転させる例です．
1: /* 2: * Cell2DSample.java 3: * 2次元セルオートマトンのサンプルプログラム 4: * Created on 2011/12/18 5: * Copyright(c) 2011 Yoshiaki Matsuzawa, Shizuoka University. All rights reserved. 6: */ 7: public class Cell2DSample extends Turtle { 8: 9: public static void main(String[] args) { 10: Turtle.startTurtle(new Cell2DSample()); 11: } 12: 13: public void start() { 14: window.setKameSpeed("very fast"); 15: window.setSize(800, 600); 16: hide(); 17: 18: int cellCount = 11;// 縦横のマスの数 19: 20: CellTurtle ct = new CellTurtle(10); 21: 22: // 種を作る 23: ct.right(cellCount / 2); 24: ct.fd(cellCount / 2); 25: ct.mark(); 26: ct.bk(cellCount / 2); 27: ct.left(cellCount / 2); 28: 29: // 繰り返して更新する 30: while (true) { 31: // １ステップの前処理 32: sleep(0.1); 33: ct.beginNextTurn(); 34: 35: // １ステップの処理（すべてのマスを書き換える） 36: for (int j = 0; j < cellCount; j++) { 37: for (int i = 0; i < cellCount; i++) { 38: if (ct.isMarked()) { 39: ct.flip(2);// 黒白を反転する 40: ct.flip(4); 41: ct.flip(6); 42: ct.flip(8); 43: } 44: ct.fd(1); 45: } 46: ct.bk(cellCount); 47: ct.right(); 48: } 49: ct.left(cellCount); 50: } 51: } 52: }
ここ をクリックすると、プログラムをダウンロードできます。
下のボタンを押すと、Cell2DSampleプログラムが実行できます。
2次元セルオートマトンでは， 格子を書き換えていくので，書き換えのタイミングを教えてあげる必要があります． このCellTurtleライブラリでは，書き換えのタイミングでsleep(0.1)とbeginNextTurn()メソッドを呼んでください．
CellTurtleプログラムでは，mark()のほかに，位置を指定してセルをマークするmark(int location), 白いセルに戻すunmark(), unmark(int location)，白黒を反転するflip(), flip(int location)等も使えます．
タートルの位置を中心に３×３の範囲で，位置に番号がついています．markされているか（黒いセルかどうか）を調べることができます。
位置の番号は以下の図の通りです．(覚えやすいように携帯電話のボタン配列と同じにしました．）
１次元セルオートマトンの例題を改変して，いろいろなルールでオートマトンを試してみよう。
ルールを変えると，例えば以下のように模様が変わります。
大きさも増やしてみましょう（変数を使うといいですネ！）
好きなルールを見つけて、友達と比較しよう。
ファイル名は「Cell.java」とすること．
例題のままではルールを変更するのが多少ややこしいので，簡単にルールを変えられるようにルールをメソッドにしてみましょう。 具体的には，ルールを調べてmark()を読んでいる箇所について，
void mark(CellTurtle ct, int r1, int r2, int r3, int r4, int r5, int r6, int r7, int r8){...}
というメソッドを作り，例えば
mark(ct, 1, 0, 0, 1, 1, 1, 1, 1);
というように呼び出すことで特定のルールを適用できるようにしてみましょう．
ファイル名は「CellByMethod.java」とすること．
前問題について，ルール番号でmarkできるよう，すなわち，
void mark(CellTurtle ct, int rule){...}
というメソッドを作って，8つのルールに変換するメソッドを作ってみよう．
ちなみに中級以上では，これは１行で書いてほしい．（しかし，ビット演算とシフト演算が必要だ！）
ファイル名は「CellByMethod2.java」とすること．
２次元セルオートマトンを作ってみよう。
まず，4つの近傍のいずれかが黒いセルならば，自分を黒くするルールで次のひし形ができるかテストしてみよう。
次に，4つの近傍のうち，黒いセルの数が1または4の時，自分を黒くするルールで次の模様ができるかどうかテストしてみよう。
下のボタンを押すと、Cell2DSample2プログラムが実行できます。
ヒント：まず，4つの近傍のいくつがマークされているかを調べるメソッドを作ろう．
ファイル名は「TwoDCell.java」とすること．
前の課題で作ったルールを改変して，いろいろなルールでオートマトンを試してみよう。
好きなルールを見つけて、友達と比較しよう。
ファイル名は「MyTwoDCell.java」とすること．
セルオートマトンの応用例として，ライフゲームがある．
wikipediaのライフゲームの説明 を参考にして，ライフゲームを作ってみよう。
参考1:銀河
下のボタンを押すと、Galaxyプログラムが実行できます。
参考2:グライダー銃
下のボタンを押すと、Gliderプログラムが実行できます。
ファイル名は「LifeGame.java」とすること．
オートマトンの画像はStephen Wolfram，"A New Kind of Science", Wolfram Media Inc, 2002からお借りしました．
貝殻の画像はここからお借りしました．