出典: フリー百科事典『ウィキペディア（Wikipedia）』
こ の 記 事 に は 参 考 文 献 や 外 部 リ ン ク の 一 覧 が 含 ま れ て い ま す が 、 脚 注 に よ る 参 照 が 不 十 分 で あ る た め 、 情 報 源 が 依 然 不 明 確 で す 。 適 切 な 位 置 に 脚 注 を 追 加 し て 、 記 事 の 信 頼 性 向 上 に ご 協 力 く だ さ い 。 ︵ 2 0 2 2 年 3 月 ︶
セル・オートマトンの一種ライフゲーム で、ゴスパー （英語版 ） グライダー銃 がグライダー を放っているところ[1]
セ ル ・ オ ー ト マ ト ン ︵ 英 : c e l l u l a r a u t o m a t o n 、 略 称 ‥ CA ︶ と は 、 格 子 状 の セ ル と 単 純 な 規 則 に よ る 、 離 散 的 計 算 モ デ ル で あ る 。 計 算 可 能 性 理 論 、 数 学 、 物 理 学 、 複 雑 適 応 系 、 数 理 生 物 学 、 微 小 構 造 モ デ リ ン グ な ど の 研 究 で 利 用 さ れ る 。 非 常 に 単 純 化 さ れ た モ デ ル で あ る が 、 生 命 現 象 、 結 晶 の 成 長 、 乱 流 と い っ た 複 雑 な 自 然 現 象 を 模 し た 、 驚 く ほ ど に 豊 か な 結 果 を 与 え て く れ る 。
正 確 な 発 音 に 近 い セ ル ラ ・ オ ー ト マ ト ン と も 呼 ば れ る こ と が あ る 。 セ ル は ﹁ 細 胞 ﹂ ﹁ 小 部 屋 ﹂ 、 セ ル ラ は ﹁ 細 胞 状 の ﹂ 、 オ ー ト マ ト ン は ﹁ か ら く り ﹂ ﹁ 自 動 機 械 ﹂ を 意 味 す る 。 他 に ﹁ セ ル 空 間 ﹂ ﹁ 埋 め 尽 く し オ ー ト マ ト ン ﹂ ﹁ h o m o g e n e o u s s t r u c t u r e ﹂ ﹁ t e s s e l l a t i o n s t r u c t u r e ﹂ ﹁ i t e r a t i v e a r r a y ﹂ と い っ た 呼 称 も あ る [ 2 ] 。
有 限 種 類 の ︵ 多 く は 2 か ら 数 十 種 類 の ︶ 状 態 を 持 つ セ ル ︵ 細 胞 の よ う な 単 位 ︶ に よ っ て セ ル ・ オ ー ト マ ト ン は 構 成 さ れ 、 離 散 的 な 時 間 で 個 々 の セ ル の 状 態 が 変 化 す る 。 そ の 変 化 は 、 あ る 時 刻 t に お い て の セ ル の 状 態 、 お よ び 近 傍 の セ ル の 内 部 状 態 に よ っ て 、 次 の 時 刻 t + 1 、 す な わ ち 新 た な ﹁ ジ ェ ネ レ ー シ ョ ン ﹂ ︵ 世 代 ︶ で の 各 セ ル の 状 態 が 決 定 さ れ る 。 初 期 状 態 ︵ 時 刻 t = 0 ︶ は 、 各 セ ル の 状 態 を 設 定 す る こ と で 選 択 さ れ る 。 次 の 世 代 ︵ t が 1 進 ん だ 状 態 ︶ は 、 事 前 に 設 定 さ れ た ﹁ 規 則 ﹂ ︵ 一 般 に 何 ら か の 数 学 的 関 数 ︶ に 従 っ て 初 期 状 態 で の そ の セ ル お よ び 近 傍 の 状 態 か ら 決 定 さ れ る 。 セ ル の 状 態 を 更 新 す る 規 則 は 一 般 に ど の セ ル で も 同 一 で あ り 、 途 中 で 変 更 さ れ ず 、 並 ん で い る 全 セ ル に 同 時 に 適 用 さ れ る 。 た だ し 確 率 的 セ ル ・ オ ー ト マ ト ン ︵ 英 語 版 ︶ や 非 同 期 セ ル ・ オ ー ト マ ト ン は 例 外 で あ る 。
そ の 概 念 は 1 9 4 0 年 代 、 ロ ス ア ラ モ ス 国 立 研 究 所 で 同 僚 だ っ た ス タ ニ ス ワ フ ・ ウ ラ ム と ジ ョ ン ・ フ ォ ン ・ ノ イ マ ン が 発 見 し た 。 そ の 後 細 々 と 研 究 さ れ て い た が 、 1 9 7 0 年 代 に 2 次 元 セ ル ・ オ ー ト マ ト ン の 一 種 ラ イ フ ゲ ー ム が 登 場 す る と 注 目 さ れ る よ う に な っ た 。 1 9 8 0 年 代 に は ス テ ィ ー ブ ン ・ ウ ル フ ラ ム が 1 次 元 セ ル ・ オ ー ト マ ト ン ま た は 基 本 セ ル ・ オ ー ト マ ト ン ︵ 英 語 版 ︶ を 体 系 的 に 研 究 し 、 一 部 の 規 則 群 が チ ュ ー リ ン グ 完 全 で あ る こ と を 示 し た 。 彼 が 2 0 0 2 年 に 出 版 し た A N e w K i n d o f S c i e n c e で は 、 セ ル ・ オ ー ト マ ト ン が 様 々 な 科 学 の 領 域 で 応 用 で き る と 主 張 し て い る 。
フ ォ ン ・ ノ イ マ ン 近 傍 ︵ D が P の 近 傍 ︶ 2 次 元 の ( つ ま り 面 状 の ) セ ル ・ オ ー ト マ ト ン の 例 と し て 、 無 限 に 広 が る 方 眼 紙 を 考 え る 。 方 眼 紙 の ひ と つ の マ ス 目 が セ ル に あ た る 。 そ れ ぞ れ の セ ル は ﹁ 黒 ﹂ と ﹁ 白 ﹂ の 2 つ の 内 部 状 態 を も つ 。 セ ル の ﹁ 近 傍 ﹂ と は 、 そ の セ ル の 周 辺 の セ ル 群 で あ り 、 通 常 は 隣 接 す る セ ル を 指 す 。 近 傍 に は 、 四 方 を 近 傍 と す る フ ォ ン ・ ノ イ マ ン 近 傍 ︵ 英 語 版 ︶ と 八 方 を 近 傍 と す る ム ー ア 近 傍 ︵ 英 語 版 ︶ と い う 2 種 類 の 典 型 的 な 定 義 が あ る [ 3 ] 。 前 者 は セ ル ・ オ ー ト マ ト ン の 考 案 者 の 名 を 冠 し て お り 、 直 交 し て 接 す る 4 つ の セ ル を 近 傍 と す る [ 3 ] 。 後 者 は フ ォ ン ・ ノ イ マ ン 近 傍 を 含 み 、 さ ら に 斜 め 方 向 の 4 つ の セ ル も 加 え た 中 心 の セ ル を 囲 む 8 つ の セ ル の 状 態 を 考 慮 す る [ 3 ] 。 ム ー ア 近 傍 の 場 合 、 そ れ ら 9 つ の セ ル が 取 る こ と が で き る 状 態 は 全 部 で 2 9 = 5 1 2 個 存 在 す る 。 セ ル ・ オ ー ト マ ト ン の 時 間 発 展 の 様 子 を 表 す ル ー ル は 表 で 与 え ら れ る 。 す な わ ち 次 の 時 間 ス テ ッ プ ︵ t + 1 ︶ で 、 中 心 の セ ル が ﹁ 黒 ﹂ ﹁ 白 ﹂ い ず れ に な る か は 、 現 在 の 時 間 ス テ ッ プ ︵ t ︶ で と り 得 る 5 1 2 個 の パ タ ー ン そ れ ぞ れ に つ い て の 一 覧 表 に よ り 決 定 さ れ る 。 ラ イ フ ゲ ー ム は こ の モ デ ル の 有 名 な 例 で あ る 。 も う 1 つ の よ く 知 ら れ て い る 近 傍 の 定 義 と し て ﹁ 拡 張 フ ォ ン ・ ノ イ マ ン 近 傍 ﹂ が あ り 、 直 交 す る 4 方 向 そ れ ぞ れ の 最 も 近 い 2 つ の セ ル を 近 傍 と し 、 全 部 で 8 つ の セ ル を 近 傍 と す る [ 3 ] 。 セ ル が と り う る 状 態 数 を k 、 次 の 状 態 を 決 定 す る の に 使 わ れ る 近 傍 の セ ル 数 ︵ 自 身 も 含 め る 場 合 が あ る ︶ を s と す る と 、 こ の よ う な シ ス テ ム の 規 則 は k k s と い う 式 で 表 さ れ る [ 4 ] 。 し た が っ て 2 次 元 の シ ス テ ム で ム ー ア 近 傍 の 場 合 、 考 え ら れ る オ ー ト マ ト ン の 総 数 は 2 2 9 ま た は 1 . 3 4 × 10 1 5 4 と な る 。
例 え ば 1 次 元 セ ル ・ オ ー ト マ ト ン で は 、 時 刻 ︵ ス テ ッ プ ︶ を t 、 位 置 を 1 次 元 の i と し た と き 、 セ ル x i t の 近 傍 は { x i − 1 t − 1 , x i t − 1 , x i + 1 t − 1 } と な る 。
2 次 元 の セ ル ・ オ ー ト マ ト ン で 最 も 有 名 な も の が ラ イ フ ゲ ー ム で あ る 。 ラ イ フ ゲ ー ム は 以 下 の よ う な ル ー ル で 記 述 さ れ る 。
● 誕 生 : 死 ん で い る セ ル ︵ ﹁ 白 ﹂ ︶ の 周 囲 に 3 つ の 生 き て い る セ ル ︵ ﹁ 黒 ﹂ ︶ が あ れ ば 次 の 時 間 ス テ ッ プ で は 生 き る ︵ ﹁ 黒 ﹂ に な る ︶ 。 ● 維 持 : 生 き て い る セ ル ︵ ﹁ 黒 ﹂ ︶ の 周 囲 に 2 つ か 3 つ の 生 き て い る セ ル ︵ ﹁ 黒 ﹂ ︶ が あ れ ば 次 の 世 代 で も 生 き 残 る ︵ ﹁ 黒 ﹂ の ま ま で あ る ︶ 。 ● 死 亡 : 上 以 外 の 場 合 に は 次 の 世 代 で は 死 ぬ ︵ ﹁ 白 ﹂ に な る ︶ 。 こ の ラ イ フ ゲ ー ム の ル ー ル は 細 菌 な ど の 生 物 の 繁 殖 の ア ナ ロ ジ ー で あ る 。 す な わ ち 、 孤 独 で も 人 口 過 密 で も 死 ん で し ま う 。 最 も 快 適 な 人 口 密 度 で は 子 孫 を 残 し 繁 栄 す る 性 質 を 持 つ 。 実 際 、 ラ イ フ ゲ ー ム は 生 物 の 増 殖 の よ う な 複 雑 で 多 様 な 振 舞 い を 示 す 。
一 般 に 各 セ ル は 同 じ 状 態 か ら 開 始 し 、 一 部 の 有 限 個 の セ ル だ け が そ れ 以 外 の 状 態 か ら 開 始 す る 。 こ れ を ﹁ コ ン フ ィ ギ ュ レ ー シ ョ ン ﹂ と 呼 ぶ [ 5 ] 。 ま た 、 全 体 が 周 期 的 な パ タ ー ン を 形 成 し 、 一 部 が そ の パ タ ー ン か ら 外 れ た 状 態 で 開 始 す る 場 合 も あ る 。 後 者 は 1 次 元 の セ ル ・ オ ー ト マ ト ン で は 一 般 的 で あ る 。
ト ー ラ ス 多 く の セ ル ・ オ ー ト マ ト ン の シ ミ ュ レ ー シ ョ ン で は 有 限 の 格 子 を 使 う 。 2 次 元 の 場 合 、 無 限 の 平 面 で は な く 、 有 限 の 四 角 形 で 表 さ れ る 。 有 限 の 格 子 で の 明 ら か な 問 題 は 端 の セ ル の 扱 い で あ り 、 端 の セ ル の 扱 い が 格 子 全 体 の セ ル の 状 態 に 影 響 を 与 え る た め 重 要 な 問 題 で あ る 。 1 つ の 手 法 は 、 端 の セ ル を 全 て 変 化 し な い 定 数 を 状 態 と し て 持 つ と す る 手 法 で あ る 。 別 の 手 法 は 端 の セ ル の 近 傍 を 一 般 の セ ル と は 違 う 内 容 に す る 手 法 で あ る 。 つ ま り 、 端 の セ ル の 近 傍 を 通 常 よ り 少 な く 定 義 で き る が 、 そ の 場 合 は 規 則 も 新 た に 定 義 す る 必 要 が あ る 。 別 の 手 法 と し て 、 2 次 元 の 場 合 に 四 角 形 の 平 面 の 端 の 上 下 と 左 右 を 繋 げ て 、 ト ー ラ ス 形 に す る 手 法 も あ る 。 こ れ は 、 あ る 意 味 で 無 限 の 平 面 が 同 じ 四 角 形 で 平 面 充 填 さ れ て い る 状 態 に 近 い 。 1 次 元 で あ れ ば 、 線 の 端 を 繋 い で ル ー プ に す る 空 間 に 相 当 す る 。 こ れ は 端 の 問 題 を 回 避 す る た め に 行 う が 、 モ ジ ュ ロ 演 算 関 数 を 使 っ て 容 易 に プ ロ グ ラ ム 可 能 と い う 利 点 も あ る 。
ロ ス ア ラ モ ス 国 立 研 究 所 の ID バ ッ ジ を つ け た ジ ョ ン ・ フ ォ ン ・ ノ イ マ ン 1 9 4 0 年 代 に ロ ス ア ラ モ ス 国 立 研 究 所 で 働 い て い た ス タ ニ ス ワ フ ・ ウ ラ ム は 結 晶 の 成 長 に つ い て 研 究 し て い た と き 、 モ デ ル と し て 単 純 な 格 子 ネ ッ ト ワ ー ク を 使 用 し て い た [ 6 ] 。 同 じ こ ろ ロ ス ア ラ モ ス で 一 緒 に 働 い て い た ジ ョ ン ・ フ ォ ン ・ ノ イ マ ン は 自 己 複 製 機 械 を 研 究 し て い た [ 7 ] 。 フ ォ ン ・ ノ イ マ ン は ま ず 、 あ る ロ ボ ッ ト の 記 述 に 基 づ い て 別 の ロ ボ ッ ト の 記 述 を 行 う と い う 設 計 を 考 え て い た 。 こ の 設 計 は 運 動 学 モ デ ル ︵ K i n e m a t i c m o d e l ︶ と 呼 ば れ て い る [ 8 ] [ 9 ] 。 設 計 を 進 め る に 連 れ 、 フ ォ ン ・ ノ イ マ ン は 、 複 製 を 作 る た め の ﹁ 部 品 の 海 ﹂ を ロ ボ ッ ト に 与 え る こ と の コ ス ト の 膨 大 さ や あ る ロ ボ ッ ト が 別 の ロ ボ ッ ト を 作 る と い う こ と を 記 述 す る 大 変 さ を 徐 々 に 理 解 し て い っ た 。 ノ イ マ ン は 1 9 4 8 年 の H i x o n S y m p o s i u m に て " T h e g e n e r a l a n d l o g i c a l t h e o r y o f a u t o m a t a " と 題 し た 論 文 を 読 む [ 7 ] 。 ま た ウ ラ ム は フ ォ ン ・ ノ イ マ ン に 自 己 複 製 の 還 元 主 義 的 モ デ ル と し て 離 散 系 を 使 っ て は ど う か と 示 唆 し た [ 1 0 ] [ 1 1 ] 。 N i l s A a l l B a r r i c e l l i は そ う い っ た モ デ ル を 使 っ て 人 工 生 命 を 研 究 し て い た 。
1 9 5 0 年 代 、 ウ ラ ム と ノ イ マ ン は 液 体 の 動 き を 計 算 す る 方 法 を 生 み 出 し た 。 そ の 中 心 と な っ た 考 え 方 は 液 体 を 離 散 的 単 位 の 集 ま り と み な す と い う こ と で 、 各 単 位 の 動 作 を そ の 近 傍 の 挙 動 に 基 づ い て 計 算 す る [ 1 2 ] 。 そ れ ら が 元 と な っ て セ ル ・ オ ー ト マ ト ン が 生 ま れ た 。 ウ ラ ム の 格 子 ネ ッ ト ワ ー ク の よ う に 、 フ ォ ン ・ ノ イ マ ン の セ ル ・ オ ー ト マ ト ン ︵ 英 語 版 ︶ は 2 次 元 で 、 そ の 中 に 自 己 複 製 機 械 が ア ル ゴ リ ズ ム 的 に 埋 め 込 ま れ た 。 こ れ が ユ ニ バ ー サ ル コ ン ス ト ラ ク タ ︵ 英 語 版 ︶ で あ り 、 近 傍 と し て 隣 接 す る 4 つ の セ ル の み ︵ ノ イ マ ン 近 傍 ︶ を 考 慮 し 、 1 つ の セ ル あ た り 29 の 内 部 状 態 を 持 っ て い る [ 1 3 ] 。 こ の モ デ ル で 彼 は 自 己 複 製 機 械 と し て 動 作 す る パ タ ー ン を 20 万 個 の セ ル を 使 っ て デ ザ イ ン し 、 そ れ が 無 限 に 自 己 複 製 を 繰 り 返 す こ と を 数 学 的 に 証 明 し た [ 1 3 ] 。 こ の 設 計 は 平 面 充 填 モ デ ル と し て 知 ら れ て い る [ 1 4 ] 。 1 9 6 8 年 、 エ ド ガ ー ・ F ・ コ ッ ド は 8 状 態 で 自 己 複 製 を 繰 り 返 す コ ッ ド の セ ル ・ オ ー ト マ ト ン を 考 案 し て い る 。
同 じ く 1 9 4 0 年 代 、 ノ ー バ ー ト ・ ウ ィ ー ナ ー と ア ル ト ゥ ー ロ ・ ロ ー ゼ ン ブ リ ュ ー ト ︵ 英 語 版 ︶ が セ ル ・ オ ー ト マ ト ン を 開 発 し 興 奮 性 媒 質 ︵ 英 語 版 ︶ の モ デ ル に 採 用 し た [ 1 5 ] 。 そ の 具 体 的 な 目 的 は 、 心 筋 に お け る イ ン パ ル ス 伝 導 の 数 学 的 説 明 で あ っ た 。 そ の 業 績 は 不 整 脈 や 興 奮 性 媒 質 に つ い て の 後 の 研 究 で よ く 引 用 さ れ て い る [ 1 6 ] 。
1 9 6 0 年 代 、 セ ル ・ オ ー ト マ ト ン は 力 学 系 の 特 殊 形 と し て 研 究 さ れ 、 数 学 の 一 分 野 で あ る 記 号 力 学 ︵ 英 語 版 ︶ と 関 連 し て 研 究 さ れ 始 め た 。 1 9 6 9 年 、 グ ス タ フ ・ A ・ ヘ ド ラ ン ド ︵ 英 語 版 ︶ は そ の 観 点 で 数 多 く の 成 果 を ま と め [ 1 7 ] 、 そ れ が セ ル ・ オ ー ト マ ト ン の 数 学 的 研 究 に お け る 重 要 な 論 文 と さ れ て い る 。
1 9 6 9 年 、 ド イ ツ の コ ン ピ ュ ー タ の パ イ オ ニ ア の 1 人 で あ る コ ン ラ ー ト ・ ツ ー ゼ は 、 著 書 C a l c u l a t i n g S p a c e の 中 で 、 宇 宙 の 物 理 法 則 は 本 質 的 に は 離 散 的 で あ り 、 宇 宙 全 体 が 一 種 の 巨 大 な セ ル ・ オ ー ト マ ト ン 上 の 決 定 的 な 計 算 の 結 果 で あ る と 主 張 し た 。 こ の 著 書 が 今 日 デ ジ タ ル 物 理 学 と 呼 ば れ て い る 分 野 の 基 礎 を 築 い た [ 1 8 ] 。
1 9 7 0 年 代 、 2 状 態 で 2 次 元 の セ ル ・ オ ー ト マ ト ン で あ る ラ イ フ ゲ ー ム が 特 に コ ン ピ ュ ー タ コ ミ ュ ニ テ ィ で よ く 知 ら れ る よ う に な っ た 。 ジ ョ ン ・ コ ン ウ ェ イ の 発 明 に よ る も の で 、 マ ー テ ィ ン ・ ガ ー ド ナ ー が サ イ エ ン テ ィ フ ィ ッ ク ・ ア メ リ カ ン 誌 ︵ 日 本 で は 日 経 サ イ エ ン ス 誌 ︶ で 紹 介 し た こ と で 有 名 と な っ た の で あ る [ 1 9 ] 。 ラ イ フ ゲ ー ム は 単 純 だ が 、 シ ス テ ム と し て 興 味 深 い 挙 動 を 示 し 、 ラ ン ダ ム 性 と 規 則 性 の 間 で 変 動 す る 。 ラ イ フ ゲ ー ム の 最 も 顕 著 な 特 徴 と し て ﹁ グ ラ イ ダ ー ﹂ ︵ 格 子 を 横 断 し て 移 動 し て い く セ ル 群 ︶ が 頻 繁 に 発 生 す る こ と が 挙 げ ら れ る 。 グ ラ イ ダ ー を う ま く 配 置 す る と 一 種 の 相 互 作 用 が 生 ま れ る 。 長 年 の 研 究 に よ り 、 ラ イ フ ゲ ー ム が チ ュ ー リ ン グ マ シ ン を エ ミ ュ レ ー ト で き る こ と が 判 明 し た [ 2 0 ] 。 そ れ が 単 な る 趣 味 の 話 題 と 受 け 止 め ら れ た た め か 、 ラ イ フ ゲ ー ム の 特 殊 性 の 研 究 や 関 連 す る 規 則 の 研 究 が 若 干 行 わ れ た 以 外 、 こ の 発 見 を 受 け た 研 究 は な さ れ な か っ た 。
1 9 8 1 年 、 熱 力 学 第 二 法 則 に 反 す る よ う に 見 え る 自 然 界 の 様 々 な 複 雑 な パ タ ー ン を 検 討 し て い た ス テ ィ ー ブ ン ・ ウ ル フ ラ ム は 、 セ ル ・ オ ー ト マ ト ン の 研 究 を 始 め た [ 2 1 ] 。 当 初 の 動 機 は セ ル ・ オ ー ト マ ト ン で 神 経 ネ ッ ト ワ ー ク な ど の シ ス テ ム を モ デ リ ン グ で き る の で は な い か と い う も の だ っ た [ 2 1 ] 。 1 9 8 3 年 6 月 、 R e v i e w s o f M o d e r n P h y s i c s 誌 に て 基 本 セ ル ・ オ ー ト マ ト ン ︵ 英 語 版 ︶ ︵ 特 に ル ー ル 30 ︶ に つ い て の 最 初 の 論 文 を 発 表 [ 2 1 ] 。 ウ ル フ ラ ム は 、 単 純 な 規 則 で 示 さ れ る 振 る 舞 い の 予 期 せ ぬ 複 雑 さ を 見 て 、 自 然 界 の 複 雑 さ も 同 様 の 機 構 に よ っ て 生 ま れ て い る の で は な い か と 考 え た [ 2 1 ] 。 し か し 、 彼 の 研 究 に よ っ て セ ル ・ オ ー ト マ ト ン は 神 経 ネ ッ ト ワ ー ク の モ デ リ ン グ に は 貧 弱 す ぎ る こ と が 判 明 し た [ 2 1 ] 。 さ ら に ウ ル フ ラ ム は 真 の 無 作 為 性 と 計 算 既 約 性 ︵ 英 語 版 ︶ の 概 念 を 定 式 化 し [ 2 2 ] 、 ル ー ル 1 1 0 ︵ 英 語 版 ︶ が チ ュ ー リ ン グ 完 全 で あ る と 推 測 し た ︵ 1 9 9 0 年 代 に ウ ル フ ラ ム の 助 手 M a t t h e w C o o k が そ れ を 証 明 し た ︶ 。
ウ ル フ ラ ム は 1 9 8 0 年 代 中 盤 以 降 に 学 界 を 去 っ て M a t h e m a t i c a を 開 発 し 、 彼 の そ れ ま で の 研 究 結 果 を 広 い 範 囲 の 単 純 で 抽 象 的 な 系 に 拡 張 し て 適 用 す る の に M a t h e m a t i c a を 使 っ た 。 2 0 0 2 年 、 ウ ル フ ラ ム は そ れ ら の 成 果 を 1 2 8 0 頁 の 著 書 A N e w K i n d o f S c i e n c e と し て 発 表 し た 。 こ の 中 で セ ル ・ オ ー ト マ ト ン が あ ら ゆ る 科 学 に と っ て 重 要 な 関 わ り を 持 つ こ と を 主 張 し て い る 。 一 部 で 誤 解 さ れ て い る よ う に 、 同 書 は 物 理 法 則 が セ ル ・ オ ー ト マ ト ン に 基 づ い て い る と は 言 っ て い な い ︵ ツ ー ゼ と は 異 な る ︶ が 、 セ ル ・ オ ー ト マ ト ン に 基 づ い た 物 理 モ デ ル を い く つ か 記 述 し て お り 、 他 に も 各 種 抽 象 系 に 基 づ い た モ デ ル を 示 し て い る 。
ウ ル フ ラ ム は あ ら ゆ る 1 次 元 の セ ル ・ オ ー ト マ ト ン の 時 間 発 展 の 仕 方 を 調 べ 上 げ 、 セ ル ・ オ ー ト マ ト ン を 含 む 単 純 な 計 算 モ デ ル の 4 つ の ク ラ ス を 定 義 し た 。 そ れ ま で の セ ル ・ オ ー ト マ ト ン の 研 究 で は 、 パ タ ー ン の 種 類 か ら 規 則 群 を 分 類 す る 傾 向 が あ っ た の に 対 し て 、 ウ ル フ ラ ム の 分 類 は 規 則 自 体 を 分 類 す る 最 初 の 試 み だ っ た 。 4 つ の ク ラ ス は 次 の 通 り で あ る 。
● ク ラ ス 1 - 秩 序 状 態 。 ほ ぼ 全 て の 初 期 状 態 で 素 早 く 安 定 し た 均 質 な 状 態 に な る 。 初 期 状 態 に 無 作 為 性 が あ っ て も 消 滅 す る [ 2 3 ] 。 ● ク ラ ス 2 - 周 期 状 態 。 ほ ぼ 全 て の 初 期 状 態 で 素 早 く 安 定 状 態 ま た は 周 期 的 に 振 動 す る 状 態 に な る 。 初 期 状 態 の 無 作 為 性 は 消 滅 す る 場 合 も あ る が 、 残 存 す る 場 合 も あ る 。 初 期 状 態 を 部 分 的 に 変 更 し た 場 合 、 そ の 影 響 は 局 所 的 と な る 傾 向 が あ る [ 2 3 ] 。 ● ク ラ ス 3 - カ オ ス 状 態 。 ほ ぼ 全 て の 初 期 状 態 で セ ル 全 体 が ラ ン ダ ム な 変 化 を 続 け る 。 安 定 し た 構 造 が 現 れ て も 、 す ぐ に 周 囲 の ノ イ ズ に よ っ て 破 壊 さ れ る 。 初 期 状 態 の 部 分 的 変 更 は 全 体 に 拡 散 し て い く 傾 向 が あ る [ 2 3 ] 。 ● ク ラ ス 4 - ほ ぼ 全 て の 初 期 状 態 で 規 則 的 な パ タ ー ン と ラ ン ダ ム な パ タ ー ン が 共 存 し 、 複 雑 な パ タ ー ン を 形 成 す る 。 局 所 的 に 形 成 さ れ た 構 造 は 長 期 間 存 続 す る こ と が で き る [ 2 4 ] 。 秩 序 状 態 で あ る ク ラ ス 1 、 ク ラ ス 2 は 新 し い 変 化 を 生 み 出 さ な い 、 い わ ば 死 ん だ 世 界 で あ る 。 カ オ ス 状 態 で あ る ク ラ ス 3 は ラ ン ダ ム す ぎ て 、 意 味 の あ る 情 報 を 生 み 出 す こ と が で き な い 。 ウ ル フ ラ ム は 秩 序 状 態 と カ オ ス 状 態 の 間 に あ る ク ラ ス 4 の 様 な 状 態 こ そ が 、 生 命 現 象 な ど の 現 実 世 界 で 見 ら れ る 複 雑 な 現 象 を 引 き 起 こ す 源 だ と 考 え た 。 こ の 研 究 に よ り 、 複 雑 系 と 呼 ば れ る 新 し い 科 学 分 野 の 基 盤 が 確 立 し た 。
こ れ ら の 定 義 は 質 的 な も の で 、 そ の 解 釈 に は 若 干 の 幅 が あ る 。 ウ ル フ ラ ム は ﹁ ど ん な 一 般 分 類 体 系 で も 、 あ る 定 義 で は こ の ク ラ ス に な る が 、 別 の 定 義 で は 別 の ク ラ ス に な る と い う ケ ー ス が 必 然 的 に 存 在 す る 。 セ ル ・ オ ー ト マ ト ン で も そ れ は 変 わ ら な い 。 あ る ク ラ ス の 特 徴 と 別 の ク ラ ス の 特 徴 を 備 え た 規 則 群 は 時 と し て 存 在 す る ﹂ と し て い る [ 2 5 ] 。 ウ ル フ ラ ム の 分 類 は 、 セ ル ・ オ ー ト マ ト ン の 出 力 を 圧 縮 し た 長 さ の 分 類 と 経 験 的 に 合 致 し て い る [ 2 6 ] 。
C u l i k と Yu に よ っ て 、 ウ ル フ ラ ム の 4 つ の ク ラ ス の 算 術 的 階 層 に お け る 位 置 が 証 明 さ れ て い る 。 ク ラ ス 1 と 2 は
Π
2
0
{\displaystyle \Pi _{2}^{0}}
- 完 全 、 ク ラ ス 3 は
Σ
3
0
{\displaystyle \Sigma _{3}^{0}}
- 完 全 に 所 属 す る 。
ウ ル フ ラ ム の 分 類 に 触 発 さ れ 、 CA を 形 式 的 に 厳 密 に 分 類 し よ う と す る 試 み も な さ れ て き た 。 例 え ば 、 C u l i k と Yu は 3 つ の w e l l - d e f i n e d な ク ラ ス ︵ そ し て そ れ ら の ど れ に も 分 類 さ れ な い 4 番 目 の ク ラ ス ︶ を 提 案 し た 。 こ れ を C u l i k - Y u ク ラ ス な ど と 呼 び 、 あ る 規 則 群 が ど の ク ラ ス に 属 す る か の 判 定 は 決 定 不 能 だ と 証 明 さ れ た [ 2 7 ] [ 2 8 ] [ 2 9 ] 。
可 逆 型 [ 編 集 ] 現 在 状 態 か ら 1 つ 前 の 状 態 ︵ プ レ イ メ ー ジ ︶ が 一 意 に 求 め ら れ る セ ル ・ オ ー ト マ ト ン を ﹁ 可 逆 的 ﹂ ( r e v e r s i b l e ) で あ る と い う [ 3 0 ] 。 セ ル ・ オ ー ト マ ト ン を 状 態 か ら 状 態 へ の 関 数 と 考 え る と 、 可 逆 性 は そ の 関 数 が 全 単 射 で あ る こ と を 意 味 す る [ 3 0 ] 。 可 逆 型 の セ ル ・ オ ー ト マ ト ン は 、 時 間 を 遡 っ た 際 の 挙 動 も セ ル ・ オ ー ト マ ト ン と し て 記 述 で き る 。 こ れ は 、 セ ル ・ オ ー ト マ ト ン を 位 相 幾 何 学 的 に 説 明 し た カ ー テ ィ ス - ヘ ド ラ ン ド - リ ン ド ン の 定 理 ︵ 英 語 版 ︶ の 帰 結 で あ る [ 3 1 ] [ 3 2 ] 。 可 逆 で な い 有 限 の セ ル ・ オ ー ト マ ト ン に は 、 ど ん な 状 態 か ら も 絶 対 生 成 ︵ 到 達 ︶ で き な い 配 置 が 存 在 す る 。 そ の よ う な 配 置 を ﹁ エ デ ン の 園 配 置 ﹂ と 呼 ぶ [ 3 3 ] 。 換 言 す れ ば 、 エ デ ン の 園 パ タ ー ン に は プ レ イ メ ー ジ が 存 在 し な い 。
1 次 元 の セ ル ・ オ ー ト マ ト ン に つ い て は 、 プ レ イ メ ー ジ を 探 す ア ル ゴ リ ズ ム が 知 ら れ て い て 、 各 ル ー ル に つ い て 可 逆 的 か そ う で な い か は 既 に 判 明 し て い る [ 3 4 ] [ 3 5 ] 。 2 次 元 以 上 の セ ル ・ オ ー ト マ ト ン に つ い て は 、 任 意 の ル ー ル の 可 逆 性 は 決 定 不 能 で あ る こ と が 証 明 さ れ て い る 。 J a r k k o K a r i に よ る 証 明 は 、 ワ ン の タ イ ル の タ イ ル 並 べ 問 題 と 関 連 し て い る [ 3 6 ] 。
可 逆 型 セ ル ・ オ ー ト マ ト ン は 、 熱 力 学 の 法 則 に 従 う 気 体 や 液 体 の 力 学 現 象 の シ ミ ュ レ ー シ ョ ン に 使 わ れ る こ と が 多 い 。 そ の 場 合 の セ ル ・ オ ー ト マ ト ン は 特 別 に 可 逆 性 を 持 つ よ う 設 計 さ れ る 。 こ の 種 の シ ス テ ム の 研 究 者 と し て ト マ ソ ・ ト フ ォ リ や ノ ー マ ン ・ マ ー ゴ ラ ス ︵ 英 語 版 ︶ ら が い る 。 意 識 的 に 可 逆 型 セ ル ・ オ ー ト マ ト ン を 作 る 手 法 は い く つ か 存 在 す る 。 二 階 セ ル ・ オ ー ト マ ト ン ︵ 英 語 版 ︶ や ブ ロ ッ ク ・ セ ル ・ オ ー ト マ ト ン ︵ 英 語 版 ︶ が そ れ で 、 ど ち ら も セ ル ・ オ ー ト マ ト ン の 定 義 に 何 ら か の 修 正 を 施 す 。 こ れ ら は 厳 密 に は 上 に 挙 げ た よ う な セ ル ・ オ ー ト マ ト ン の 定 義 か ら 外 れ て い る が 、 十 分 に 大 き な 近 傍 と 多 数 の 状 態 を 持 つ 従 来 型 の セ ル ・ オ ー ト マ ト ン で エ ミ ュ レ ー ト で き る こ と が 判 っ て お り 、 従 来 型 の セ ル ・ オ ー ト マ ト ン の サ ブ セ ッ ト と 見 な す こ と が で き る 。 逆 に 全 て の 可 逆 型 セ ル ・ オ ー ト マ ト ン は ブ ロ ッ ク ・ セ ル ・ オ ー ト マ ト ン で エ ミ ュ レ ー ト で き る [ 3 7 ] [ 3 8 ] 。
総 和 型 [ 編 集 ] 特 殊 な セ ル ・ オ ー ト マ ト ン と し て 、 総 和 型 ( t o t a l i s t i c ) セ ル ・ オ ー ト マ ト ン が あ る 。 総 和 型 セ ル ・ オ ー ト マ ト ン で の 各 セ ル の 状 態 は 数 値 で 表 さ れ ︵ 通 常 、 有 限 個 の 整 数 値 ︶ 、 時 刻 t に お け る セ ル の 値 は 、 時 刻 t − 1 に お け る 近 傍 ︵ 自 身 も 含 む こ と も あ る ︶ の セ ル 群 の 値 の 総 和 だ け に 依 存 し て 決 定 さ れ る [ 3 9 ] [ 4 0 ] 。 時 刻 t に お け る セ ル の 状 態 が 自 身 の t − 1 で の 状 態 に 依 存 す る 場 合 、 そ の よ う な セ ル ・ オ ー ト マ ト ン を ﹁ 外 部 総 和 型 ﹂ ( o u t e r t o t a l i s t i c ) と 呼 ぶ [ 4 0 ] 。 ラ イ フ ゲ ー ム は 、 値 と し て 0 と 1 を と る 外 部 総 和 型 の セ ル ・ オ ー ト マ ト ン の 例 で あ る 。 同 じ く 外 部 総 和 型 で ム ー ア 近 傍 だ が 、 規 則 を ラ イ フ ゲ ー ム と は 変 え た セ ル ・ オ ー ト マ ト ン を 欧 米 で は " l i f e - l i k e " と 呼 ぶ [ 4 1 ] [ 4 2 ] 。
そ の 他 [ 編 集 ] CA の 概 念 は 様 々 な 拡 張 が 可 能 で あ る 。
六 角 形 の セ ル に 基 づ く セ ル ・ オ ー ト マ ト ン ︵ ル ー ル 3 4 / 2 ︶ 例 え ば 、 矩 形 の 格 子 で は な く 別 の 多 角 形 を 使 う と い う 拡 張 が あ る 。 例 え ば 六 角 形 を 平 面 に 敷 き 詰 め た と き 、 個 々 の 六 角 形 を セ ル と し て 扱 う こ と が で き る 。 多 く の 場 合 そ の よ う な セ ル ・ オ ー ト マ ト ン は 、 矩 形 格 子 で 近 傍 と 規 則 を う ま く 調 整 し た も の と 等 価 で あ る 。 他 に も ペ ン ロ ー ズ ・ タ イ ル の よ う な 平 面 充 填 で 格 子 を 形 成 す る こ と も で き る [ 4 3 ] 。
ま た 、 規 則 を 決 定 的 な も の で は な く 確 率 的 な も の に す る 拡 張 も あ る 。 そ の よ う な CA を 確 率 的 セ ル ・ オ ー ト マ ト ン ︵ 英 語 版 ︶ と 呼 ぶ 。 こ の 場 合 、 時 刻 t の パ タ ー ン か ら 時 刻 t + 1 の と り う る 各 パ タ ー ン の 遷 移 確 率 が 確 率 的 規 則 に よ り 指 定 さ れ る 。 も っ と 単 純 な 規 則 を 使 う こ と も あ り 、 例 え ば ﹁ 基 本 的 に ラ イ フ ゲ ー ム の 規 則 に 従 う が 、 毎 回 0 . 0 0 1 % の 確 率 で 本 来 と は 反 対 の 色 に な る ﹂ と い っ た 規 則 を 設 定 す る 。
時 間 や 場 所 に よ っ て 近 傍 の 定 義 や 規 則 を 変 化 さ せ る と い う 拡 張 も あ る 。 例 え ば 、 最 初 の 世 代 で は 水 平 方 向 の 隣 接 し た セ ル を 近 傍 と す る が 、 次 の 世 代 で は 垂 直 方 向 の 隣 接 す る セ ル を 近 傍 と す る 、 と い っ た 具 合 で あ る 。
CA で は 、 あ る セ ル の 新 た な 状 態 は 、 他 の セ ル の 新 た な 状 態 に 影 響 さ れ な い 。 こ の 原 則 を 変 更 す る こ と も で き る 。
連 続 値 セ ル オ ー ト マ ト ン ︵ 英 語 版 ︶ と 呼 ば れ る も の も あ る 。 総 和 型 と 似 て い る が 、 規 則 や 状 態 が 離 散 値 で は な く 連 続 な 値 ︵ 一 般 に 単 位 区 間 の 値 ︶ を 用 い る 。 つ ま り 、 セ ル の 状 態 は 有 限 個 の 実 数 で 表 さ れ る 。 例 え ば 、 液 体 に お け る 拡 散 パ タ ー ン の モ デ ル な ど に 使 わ れ る 。
C o n t i n u o u s s p a t i a l a u t o m a t a で は 位 置 が 連 続 的 で あ る 。 あ る 位 置 の 状 態 は 有 限 個 の 実 数 で あ る 。 時 間 も 連 続 的 に 推 移 し 、 状 態 は 微 分 方 程 式 に し た が っ て 変 化 す る 。 重 要 な 例 と し て 反 応 拡 散 系 が あ り 、 ア ラ ン ・ チ ュ ー リ ン グ は シ マ ウ マ の 縞 模 様 や ヒ ョ ウ の ド ッ ト 模 様 を 生 み 出 し た 化 学 反 応 を 説 明 す る 微 分 方 程 式 を 提 案 し た [ 4 4 ] 。 そ の よ う な パ タ ー ン を CA で 近 似 的 に 生 成 す る こ と も 可 能 で あ る 。 c o n t i n u o u s s p a t i a l a u t o m a t a で ラ イ フ ゲ ー ム の グ ラ イ ダ ー の よ う な 現 象 が 生 じ る 例 も 知 ら れ て い る [ 4 5 ] 。
1 次 元 セ ル ・ オ ー ト マ ト ン [ 編 集 ] 最 も 単 純 だ が 自 明 で は な い CA は 、 1 次 元 で 各 セ ル は 2 つ の 状 態 を と る こ と が で き 、 近 傍 は 両 側 に 接 し て い る 隣 の セ ル と い う 場 合 で あ る 。 あ る セ ル と そ の 両 側 の 3 つ の セ ル で 近 傍 を 構 成 す る の で 、 1 つ の 近 傍 が と り う る パ タ ー ン は 2 3 = 8 種 類 と な る 。 規 則 は そ れ ら パ タ ー ン に つ い て 、 そ の セ ル が 次 世 代 に 1 と 0 の ど ち ら 状 態 と な る か を 決 定 す る 。 し た が っ て 規 則 群 の 組 合 せ は 2 8 = 2 5 6 通 り 存 在 す る [ 4 ] 。 そ れ ら 2 5 6 種 類 の CA は 一 般 に ウ ル フ ラ ム が 考 案 し た 0 か ら 2 5 5 ま で の ル ー ル 番 号 で 参 照 さ れ 、 こ れ を ウ ル フ ラ ム ・ コ ー ド と 呼 ぶ 。 こ れ ら 2 5 6 種 類 の CA は い く つ か の 論 文 で 研 究 ・ 比 較 さ れ て い る 。 ル ー ル 30 と ル ー ル 1 1 0 ︵ 英 語 版 ︶ の CA は 特 に 興 味 深 い 。 下 図 は 、 1 カ 所 だ け 1 に し た 初 期 状 態 か ら の そ れ ら CA の 変 化 の 様 子 を 示 し て い る 。 図 の 各 行 が CA の 1 世 代 の 履 歴 で あ り 、 一 番 上 の 行 が t = 0 で あ る 。 各 ピ ク セ ル は 、 0 を 白 、 1 を 黒 で 描 画 し て い る 。
ルール30セル・オートマトン [ 編集 ]
現在の状態
111
110
101
100
011
010
001
000
中央のセルの次の状態
* 0*
* 0*
* 0*
* 1*
* 1*
* 1*
* 1*
* 0*
ルール110セル・オートマトン [ 編集 ]
現在の状態
111
110
101
100
011
010
001
000
中央のセルの次の状態
* 0*
* 1*
* 1*
* 0*
* 1*
* 1*
* 1*
* 0*
例 え ば ﹁ ル ー ル 30 ﹂ と 呼 ば れ る の は 、 上 の 表 の よ う に 時 刻 t + 1 に お け る 中 央 の セ ル の 内 部 状 態 一 覧 を 並 べ る と 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 と な っ て お り 、 こ の 2 進 数 の 数 を 10 進 数 に 直 す と 30 で あ る た め で あ り 、 こ れ を ウ ル フ ラ ム ・ コ ー ド と 呼 ぶ 。
ル ー ル 30 は ﹁ ク ラ ス 3 ﹂ の 挙 動 を 示 し 、 単 純 な 初 期 状 態 か ら も カ オ ス 的 な 経 過 を 示 し 、 無 作 為 な 履 歴 に な っ て い る 。
ル ー ル 1 1 0 は ラ イ フ ゲ ー ム の よ う に ﹁ ク ラ ス 4 ﹂ の 挙 動 を 示 し 、 完 全 な 無 作 為 で も な く 、 完 全 な 反 復 で も な い 。 局 所 的 構 造 が 現 れ 、 様 々 な 複 雑 な 形 で 相 互 作 用 す る 。 1 9 9 4 年 ウ ル フ ラ ム の 研 究 助 手 だ っ た マ シ ュ ー ・ ク ッ ク は 、 そ れ ら 構 造 の 一 部 が チ ュ ー リ ン グ 完 全 性 を サ ポ ー ト す る の に 十 分 で あ る こ と を 証 明 し た 。 ル ー ル 1 1 0 は 非 常 に 単 純 な 1 次 元 の シ ス テ ム で あ り 、 具 体 的 な こ と を 実 行 す る よ う 設 計 す る の は 困 難 で あ る た め 、 こ の 成 果 は 興 味 深 い 。 こ の 結 果 か ら ウ ル フ ラ ム は ク ラ ス 4 の セ ル ・ オ ー ト マ ト ン が 本 質 的 に チ ュ ー リ ン グ 完 全 で あ る 可 能 性 を 示 唆 し た 。 1 9 9 8 年 、 セ ル ・ オ ー ト マ ト ン の 学 会 が サ ン タ フ ェ 研 究 所 で 開 催 さ れ 、 ク ッ ク は そ の 成 果 を 発 表 し た が 、 ウ ル フ ラ ム は A N e w K i n d o f S c i e n c e の 出 版 前 に そ の 証 明 の 詳 細 を 公 表 し た く な か っ た た め 、 証 明 の 詳 細 は 発 表 さ れ な か っ た [ 4 6 ] 。 2 0 0 4 年 、 C o o k の 証 明 が ウ ル フ ラ ム の 発 行 す る 雑 誌 C o m p l e x S y s t e m s ( V o l . 1 5 , N o . 1 ) で 発 表 さ れ た 。 実 に 証 明 し て か ら 10 年 が 経 過 し て い る 。 ル ー ル 1 1 0 を ベ ー ス と し て 極 小 の 万 能 チ ュ ー リ ン グ マ シ ン が 構 築 さ れ て い る [ 4 7 ] 。
ル ー ル 90 [ 編 集 ] ま た 、 ル ー ル 90 の 1 次 元 セ ル ・ オ ー ト マ ト ン は 典 型 的 な フ ラ ク タ ル 図 形 で あ る シ ェ ル ピ ン ス キ ー の ギ ャ ス ケ ッ ト を 生 成 す る 。 ︵ W o l f r a m A l p h a で ル ー ル 90 を 見 る → r u l e 9 0 ︶
シェルピンスキーのギャスケット 生物学における例 [ 編集 ] イモガイ の一種タガヤサンミナシのセル・オートマトン状模様の貝殻[48]
一 部 の 生 物 学 的 過 程 は セ ル ・ オ ー ト マ ト ン で シ ミ ュ レ ー ト で き る 。
イ モ ガ イ や ガ ク フ ボ ラ と い っ た 貝 の 貝 殻 の 模 様 は セ ル ・ オ ー ト マ ト ン の 描 く パ タ ー ン に よ く 似 て い る 。 貝 殻 の 辺 縁 に 狭 い 帯 状 に 色 素 細 胞 が あ る 。 各 色 素 細 胞 は 活 性 化 さ れ る と 色 素 を 分 泌 し 、 同 時 に 近 傍 の 色 素 細 胞 の 活 性 化 を 阻 害 す る よ う に な っ て お り 、 天 然 の セ ル ・ オ ー ト マ ト ン の 規 則 の よ う に 作 用 す る [ 4 8 ] 。 こ の 色 素 細 胞 の 帯 が 貝 殻 に 色 の 模 様 を 残 し つ つ 、 少 し ず つ 貝 殻 が 成 長 し て い く 。 例 え ば 、 イ モ ガ イ の 一 種 タ ガ ヤ サ ン ミ ナ シ は ウ ル フ ラ ム が 研 究 し た ル ー ル 30 CA と よ く 似 た 模 様 で あ る [ 4 8 ] 。
植 物 は CA 的 機 構 で 気 体 の 吸 入 と 排 出 を 行 っ て い る 。 葉 に 多 数 存 在 す る 気 孔 が セ ル ・ オ ー ト マ ト ン の セ ル の よ う に 振 る 舞 う [ 4 9 ] 。
頭 足 類 は 表 皮 に 色 素 胞 が あ り 、 体 表 の 模 様 を 変 化 さ せ る が 、 こ れ を 2 状 態 で 2 次 元 の セ ル ・ オ ー ト マ ト ン で シ ミ ュ レ ー ト で き る 。 各 状 態 は 色 素 胞 を 広 げ た 状 態 と 縮 め た 状 態 に 対 応 す る [ 5 0 ] 。
神 経 細 胞 を シ ミ ュ レ ー ト す る し き い 値 型 CA が 考 案 さ れ て お り 、 認 知 や 学 習 と い っ た 複 雑 な 挙 動 を シ ミ ュ レ ー ト で き る 。
線 維 芽 細 胞 も セ ル ・ オ ー ト マ ト ン と 似 た 挙 動 を 示 す 。 個 々 の 線 維 芽 細 胞 は そ の 近 傍 の 細 胞 と し か 相 互 作 用 し な い [ 5 1 ] 。
化 学 に お け る 例 [ 編 集 ] ベ ロ ウ ソ フ ・ ジ ャ ボ チ ン ス キ ー 反 応 は セ ル ・ オ ー ト マ ト ン を 使 っ て シ ミ ュ レ ー ト で き る 。 1 9 5 0 年 代 、 A ・ M ・ ジ ャ ボ チ ン ス キ ー は ソ 連 の B ・ P ・ ベ ロ ウ ソ フ ︵ 英 語 版 ︶ の 研 究 成 果 を さ ら に 進 め 、 マ ロ ン 酸 、 酸 化 し た 臭 素 酸 塩 、 セ リ ウ ム 塩 の 混 合 物 の 薄 い 均 一 な 層 を 置 い て お く と 、 同 心 円 や 渦 巻 き 模 様 な ど の 幾 何 学 的 模 様 が 生 じ る こ と を 発 見 し た 。 1 9 8 8 年 8 月 、 サ イ エ ン テ ィ フ ィ ッ ク ・ ア メ リ カ ン ︵ 日 本 で は 日 経 サ イ エ ン ス ︶ 誌 上 の " C o m p u t e r R e c r e a t i o n " と い う 記 事 で [ 5 2 ] 、 A . K . D e w d n e y は ベ ロ ウ ソ フ ・ ジ ャ ボ チ ン ス キ ー 反 応 に 非 常 に よ く 似 た 挙 動 を 示 す セ ル ・ オ ー ト マ ト ン を 紹 介 し た [ 5 3 ] 。 ベ ロ ウ ソ フ ・ ジ ャ ボ チ ン ス キ ー 反 応 が 、 分 子 レ ベ ル で そ の セ ル ・ オ ー ト マ ト ン と 同 じ よ う な 仕 組 み で 発 生 し て い る の か ど う か は 不 明 で あ る 。 こ れ ま で 、 セ ル ・ オ ー ト マ ト ン 的 な 化 学 反 応 が 自 然 界 で 観 察 さ れ た こ と は な い 。 そ の よ う な 化 学 反 応 は 全 て 研 究 室 や 実 験 室 で の み 観 測 さ れ て い る 。
物 理 に お け る 例 [ 編 集 ] ソ リ ト ン の よ う な ふ る ま い を 見 せ る 、 箱 玉 系 と 呼 ば れ て い る セ ル ・ オ ー ト マ ト ン が あ る 。
並 列 コ ン ピ ュ ー タ [ 編 集 ] 離 散 的 ( 非 連 続 的 ) 時 間 で 記 述 さ れ 、 時 刻 t + 1 に お け る 1 つ の セ ル の 内 部 状 態 は 、 時 刻 t に お け る 状 態 に よ っ て 決 定 さ れ る と い っ た 点 で 、 セ ル ・ オ ー ト マ ト ン は チ ュ ー リ ン グ マ シ ン と よ く 似 て い る 。 実 際 、 万 能 チ ュ ー リ ン グ マ シ ン と 等 価 な 動 作 を す る セ ル ・ オ ー ト マ ト ン が 存 在 す る こ と が 知 ら れ て い る 。 し か し 、 チ ュ ー リ ン グ マ シ ン は ﹁ 逐 次 的 な 処 理 を 行 う デ ジ タ ル コ ン ピ ュ ー タ ﹂ の モ デ ル で あ る の に 対 し 、 セ ル ・ オ ー ト マ ト ン は 各 セ ル が 並 列 に 演 算 処 理 を 実 現 し て お り 、 い わ ば ﹃ 並 列 コ ン ピ ュ ー タ ﹄ で あ る と い う 点 で 大 き く 異 な る 。
セ ル ・ オ ー ト マ ト ン の 概 念 を ハ ー ド ウ ェ ア で 実 装 し て 情 報 処 理 を 行 お う と す る 試 み も 行 わ れ て い る 。 処 理 要 素 は 格 子 状 に 配 置 さ れ 、 2 次 元 か 3 次 元 の 平 面 充 填 構 造 と さ れ る 。 そ れ 以 外 の 並 べ 方 も 可 能 だ が 、 ま だ 試 さ れ た こ と は な い 。 各 処 理 要 素 ︵ す な わ ち セ ル ︶ は 隣 接 す る 少 数 の セ ル だ け と や り 取 り す る 。 遠 い セ ル と の 直 接 通 信 手 段 は 存 在 し な い 。 セ ル の 相 互 作 用 に は 、 電 荷 、 磁 化 、 振 動 な ど の 物 理 的 な 手 段 を 使 う 。 い ず れ に し て も 各 処 理 要 素 間 を 結 線 す る 必 要 は な い 。 こ れ は 、 今 日 の ノ イ マ ン 型 コ ン ピ ュ ー タ の プ ロ セ ッ サ と は か な り 違 う 。
例 え ば シ ス ト リ ッ ク ア レ イ ︵ 英 語 版 ︶ は CA プ ロ セ ッ サ ア レ イ の 一 例 で あ る 。
遺 伝 的 ア ル ゴ リ ズ ム を 使 っ た 進 化 す る セ ル ・ オ ー ト マ ト ン [ 編 集 ] セ ン サ ー ネ ッ ト ワ ー ク や さ ら に 微 細 な 構 造 を ネ ッ ト ワ ー ク と し て 設 計 し 、 分 散 処 理 を 行 わ せ る こ と に 関 心 が 集 ま っ て い る 。 分 散 シ ス テ ム を 使 い 大 域 的 な レ ベ ル で 情 報 処 理 す る と い う 考 え 方 か ら 創 発 計 算 と い う ア イ デ ア が 生 ま れ た [ 5 4 ] 。 ポ ー ト ラ ン ド 州 立 大 学 の 教 授 で サ ン タ フ ェ 研 究 所 に も 所 属 し て い る メ ラ ニ ー ・ ミ ッ チ ェ ル ︵ 英 語 版 ︶ [ 5 5 ] は 、 そ の た め に 自 己 進 化 す る セ ル の 格 子 を 使 う ア イ デ ア に 取 り 組 ん で い る [ 5 4 ] 。 ミ ッ チ ェ ル ら は セ ル 格 子 の プ ロ グ ラ ム に 進 化 的 ア ル ゴ リ ズ ム を 採 用 し て い る [ 5 6 ] 。 分 散 型 シ ス テ ム に お け る 計 算 は 古 典 的 な コ ン ピ ュ ー タ と は 大 き く 異 な り 、 大 域 的 お よ び 局 所 的 な パ タ ー ン の 変 化 と い う 形 で 情 報 処 理 が な さ れ る 。
こ の 手 法 の 発 想 の 元 に な っ て い る の は 、 社 会 性 昆 虫 、 神 経 系 、 経 済 シ ス テ ム と い っ た 自 然 界 に 見 ら れ る 複 雑 な シ ス テ ム で あ る [ 5 6 ] 。 研 究 の 焦 点 は 、 進 化 す る 分 散 型 シ ス テ ム で い か に し て 計 算 が 発 生 す る か を 解 明 す る こ と で あ る 。 モ デ ル を 構 築 し ど の よ う に し て 創 発 計 算 が 生 じ る か を 解 明 す る た め 、 ミ ッ チ ェ ル ら は セ ル ・ オ ー ト マ ト ン 内 の パ タ ー ン を 進 化 さ せ る べ く 遺 伝 的 ア ル ゴ リ ズ ム ( GA ) を 適 用 し た 。 既 に GA に よ っ て 洗 練 さ れ た 創 発 計 算 戦 略 が 生 じ る 規 則 を 発 見 し て い る [ 5 7 ] 。 ミ ッ チ ェ ル ら が 採 用 し た の は 1 次 元 2 値 で 6 個 の 近 傍 を 持 つ セ ル ・ オ ー ト マ ト ン で あ る 。 先 頭 と 末 尾 は 繋 が っ て い る の で 、 環 状 に な っ て い る 。
2 次 元 セ ル ・ オ ー ト マ ト ン を 擬 似 乱 数 発 生 に 使 っ た 例 が あ る 。 [ 5 8 ] ル ー ル 30 は 、 ブ ロ ッ ク 暗 号 に 応 用 可 能 と い う 提 案 が あ る 。 [ 5 9 ] セ ル ・ オ ー ト マ ト ン を 公 開 鍵 暗 号 に 使 う と い う 提 案 も あ る 。 [ 6 0 ] 誤 り 訂 正 符 号 [ 編 集 ] セ ル ・ オ ー ト マ ト ン を 誤 り 訂 正 符 号 の 設 計 に 応 用 し た 例 と し て 、 D . R o y C h o w d h u r y 、 S . B a s u 、 I . S e n G u p t a 、 P . P a l C h a u d h u r i の 論 文 " D e s i g n o f C A E C C - C e l l u l a r A u t o m a t a B a s e d E r r o r C o r r e c t i n g C o d e " が あ る 。 こ の 論 文 で は セ ル ・ オ ー ト マ ト ン を 使 っ て S E C - D E D 符 号 ︵ 1 ビ ッ ト 誤 り 訂 正 - 2 ビ ッ ト 誤 り 検 出 符 号 ︶ を 構 築 す る 新 た な 手 法 が 定 義 さ れ て お り 、 そ の 符 号 の 高 速 ハ ー ド ウ ェ ア デ コ ー ダ も 報 告 さ れ て い る 。
物質世界の基盤のモデルとしてのCA [ 編集 ]
A n d r e w I l a c h i n s k i は 著 書 C e l l u l a r A u t o m a t a で 、 多 く の 学 者 が 宇 宙 自 体 が セ ル ・ オ ー ト マ ト ン な の で は な い か と い う 疑 問 を 投 げ か け て い る と 指 摘 し た [ 6 1 ] 。 I l a c h i n s k i は 、 こ の 問 題 の 重 要 性 を 示 す に は 簡 単 な 観 察 を し て み る の が よ い と 主 張 し 、 例 え ば ル ー ル 1 1 0 ︵ 英 語 版 ︶ の 発 展 す る パ タ ー ン を ど う や っ た ら う ま く 説 明 で き る か 考 え て み る の が よ い と し た [ 6 2 ] 。 そ し て 、 も し そ の イ メ ー ジ の 生 成 方 法 を 知 ら な い と し た ら 、 何 ら か の 粒 子 状 の オ ブ ジ ェ ク ト の 運 動 の 軌 跡 で は な い か と 推 測 す る だ ろ う と 述 べ て い る 。 実 際 、 物 理 学 者 J a m e s C r u t c h f i e l d は そ の 考 え 方 か ら 厳 密 な 数 学 的 理 論 を 構 築 し た [ 6 3 ] 。 こ の 考 え 方 を 推 し 進 め て い く と 、 素 粒 子 物 理 学 で 説 明 さ れ て い る 我 々 の 世 界 も 根 底 で は CA と 見 な せ る の で は な い か と い う 考 え 方 に 到 達 す る 。
そ の 考 え 方 に 沿 っ た 理 論 は ま だ 発 展 途 中 だ が 、 こ の 仮 説 に 興 味 を 惹 か れ た 学 者 ら が 離 散 的 フ レ ー ム ワ ー ク で 世 界 を 理 解 す る こ と に つ い て 興 味 深 い 憶 測 と 有 益 な 直 観 を 示 し て い る 。 AI 研 究 者 マ ー ビ ン ・ ミ ン ス キ ー は 、 4 次 元 CA 格 子 で 素 粒 子 の 相 互 作 用 を 理 解 す る 方 法 を 研 究 し た [ 6 4 ] 。 コ ン ピ ュ ー タ の 先 駆 者 コ ン ラ ー ト ・ ツ ー ゼ は 、 素 粒 子 の 持 つ 情 報 に つ い て の 問 題 を 解 く た め 、 不 規 則 な 格 子 を 考 案 し た [ 6 5 ] 。 ま た エ ド ワ ー ド ・ フ レ ド キ ン は " f i n i t e n a t u r e h y p o t h e s i s " と 名 付 け た 仮 説 を 提 唱 。 ﹁ 最 終 的 に 時 間 や 空 間 を 含 む 全 て の 物 理 量 は 離 散 的 で 有 限 だ と 判 明 す る だ ろ う ﹂ と し た [ 6 6 ] 。 フ レ ド キ ン と ウ ル フ ラ ム は デ ジ タ ル 物 理 学 の 信 奉 者 で あ る 。
21 世 紀 に 入 る と 、 非 標 準 計 算 に つ い て の 著 作 か ら こ の 考 え 方 に 沿 っ た 示 唆 が 生 ま れ て い る 。 ウ ル フ ラ ム の A N e w K i n d o f S c i e n c e で は 、 CA が 物 理 学 を 含 め た 様 々 な 主 題 を 理 解 す る 鍵 だ と し て い る 。 ︵ F r a n c e s c o B e r t o が 創 始 し 、 G a b r i e l e R o s s i と J a c o p o T a g l i a b u e が 発 展 さ せ た ︶ i L a b s [ 6 7 ] が 2 0 1 0 年 に 出 版 し た M a t h e m a t i c s O f t h e M o d e l s o f R e f e r e n c e で は ﹁ 菱 形 十 二 面 体 ﹂ を ベ ー ス と す る 格 子 と 独 特 の 規 則 で 2 次 元 お よ び 3 次 元 の 宇 宙 を 説 明 す る モ デ ル を 提 案 し て い る 。 こ の モ デ ル は チ ュ ー リ ン グ マ シ ン と 等 価 で あ り 、 完 全 な 可 逆 性 を 有 し ︵ 様 々 な 量 を 保 存 し 、 情 報 を 決 し て 失 わ な い ︶ 、 宇 宙 の 発 展 に つ い て の 質 的 な 論 述 を 計 算 で き る 論 理 が 組 み 込 ま れ て い る [ 6 8 ] 。
(一) ^ D a n i e l D e n n e t t ( 1 9 9 5 ) , D a r w i n ' s D a n g e r o u s I d e a , P e n g u i n B o o k s , L o n d o n , I S B N 9 7 8 - 0 - 1 4 - 0 1 6 7 3 4 - 4 , I S B N 0 - 1 4 - 0 1 6 7 3 4 - X (二) ^ W o l f r a m , S t e p h e n ( 1 9 8 3 ) . “ S t a t i s t i c a l M e c h a n i c s o f C e l l u l a r A u t o m a t a ” . R e v i e w s o f M o d e r n P h y s i c s 55 ( 3 ) : 6 0 1 – 6 4 4 . B i b c o d e : 1 9 8 3 R v M P . . . 5 5 . . 6 0 1 W . d o i : 1 0 . 1 1 0 3 / R e v M o d P h y s . 5 5 . 6 0 1 . http://www.stephenwolfram.com/publications/articles/ca/83-statistical/ . (三) ^ a b c d K i e r , S e y b o l d & C h e n g 2 0 0 5 , p . 15 (四) ^ a b B i a l y n i c k i - B i r u l a & B i a l y n i c k a - B i r u l a 2 0 0 4 , p . 9 (五) ^ S c h i f f 2 0 1 1 , p . 41 (六) ^ P i c k o v e r , C l i f f o r d A . ( 2 0 0 9 ) . T h e M a t h B o o k : F r o m P y t h a g o r a s t o t h e 5 7 t h D i m e n s i o n , 2 5 0 M i l e s t o n e s i n t h e H i s t o r y o f M a t h e m a t i c s . S t e r l i n g P u b l i s h i n g C o m p a n y , I n c . p . 4 0 6 . I S B N 9 7 8 - 1 4 0 2 7 5 7 9 6 9 (七) ^ a b S c h i f f 2 0 1 1 , p . 1 (八) ^ J o h n v o n N e u m a n n , “ T h e g e n e r a l a n d l o g i c a l t h e o r y o f a u t o m a t a , ” i n L . A . J e f f r e s s , e d . , C e r e b r a l M e c h a n i s m s i n B e h a v i o r – T h e H i x o n S y m p o s i u m , J o h n W i l e y & S o n s , N e w Y o r k , 1 9 5 1 , p p . 1 - 3 1 . (九) ^ J o h n G . K e m e n y , “ M a n v i e w e d a s a m a c h i n e , ” S c i . A m e r . 1 9 2 ( A p r i l 1 9 5 5 ) : 5 8 - 6 7 ; S c i . A m e r . 1 9 2 ( J u n e 1 9 5 5 ) : 6 ( e r r a t a ) . (十) ^ S c h i f f 2 0 1 1 , p . 3 (11) ^ I l a c h i n s k i 2 0 0 1 , p . x x i x (12) ^ B i a l y n i c k i - B i r u l a & B i a l y n i c k a - B i r u l a 2 0 0 4 , p . 8 (13) ^ a b W o l f r a m 2 0 0 2 , p . 8 7 6 (14) ^ v o n N e u m a n n , J o h n ; B u r k s , A r t h u r W . ( 1 9 6 6 ) . T h e o r y o f S e l f - R e p r o d u c i n g A u t o m a t a . U n i v e r s i t y o f I l l i n o i s P r e s s (15) ^ W i e n e r , N . ; R o s e n b l u e t h , A . ( 1 9 4 6 ) . “ T h e m a t h e m a t i c a l f o r m u l a t i o n o f t h e p r o b l e m o f c o n d u c t i o n o f i m p u l s e s i n a n e t w o r k o f c o n n e c t e d e x c i t a b l e e l e m e n t s , s p e c i f i c a l l y i n c a r d i a c m u s c l e ” . A r c h . I n s t . C a r d i o l . M é x i c o 16 : 2 0 5 . (16) ^ D a v i d e n k o , J . M . ; P e r t s o v , A . V . ; S a l o m o n s z , R . ; B a x t e r , W . ; J a l i f e , J . ( 1 9 9 2 ) . “ S t a t i o n a r y a n d d r i f t i n g s p i r a l w a v e s o f e x c i t a t i o n i n i s o l a t e d c a r d i a c m u s c l e ” . N a t u r e 3 5 5 ( 6 3 5 8 ) : 3 4 9 – 3 5 1 . B i b c o d e : 1 9 9 2 N a t u r . 3 5 5 . . 3 4 9 D . d o i : 1 0 . 1 0 3 8 / 3 5 5 3 4 9 a 0 . P M I D 1 7 3 1 2 4 8 . (17) ^ H e d l u n d , G . A . ( 1 9 6 9 ) . “ E n d o m o r p h i s m s a n d a u t o m o r p h i s m s o f t h e s h i f t d y n a m i c a l s y s t e m ” . M a t h . S y s t e m s T h e o r y 3 ( 4 ) : 3 2 0 – 3 7 5 1 . d o i : 1 0 . 1 0 0 7 / B F 0 1 6 9 1 0 6 2 . http://www.springerlink.com/content/k62915l862l30377/ . (18) ^ S c h i f f 2 0 1 1 , p . 1 8 2 (19) ^ G a r d n e r , M a r t i n ( 1 9 7 0 ) . “ M a t h e m a t i c a l G a m e s : T h e f a n t a s t i c c o m b i n a t i o n s o f J o h n C o n w a y ' s n e w s o l i t a i r e g a m e " l i f e " ” . S c i e n t i f i c A m e r i c a n ( 2 2 3 ) : 1 2 0 – 1 2 3 . http://www.ibiblio.org/lifepatterns/october1970.html . (20) ^ P a u l C h a p m a n . L i f e u n i v e r s a l c o m p u t e r . N o v e m b e r 2 0 0 2 (21) ^ a b c d e W o l f r a m 2 0 0 2 , p . 8 8 0 (22) ^ W o l f r a m 2 0 0 2 , p . 8 8 1 (23) ^ a b c I l a c h i n s k i 2 0 0 1 , p . 12 (24) ^ I l a c h i n s k i 2 0 0 1 , p . 13 (25) ^ W o l f r a m 2 0 0 2 , p . 2 3 1 (26) ^ Z e n i l , H e c t o r ( 2 0 1 0 ) . “ C o m p r e s s i o n - b a s e d i n v e s t i g a t i o n o f t h e d y n a m i c a l p r o p e r t i e s o f c e l l u l a r a u t o m a t a a n d o t h e r s y s t e m s ” . C o m p l e x S y s t e m s 19 ( 1 ) . http://www.complex-systems.com/pdf/19-1-1.pdf . (27) ^ G . C a t t a n e o , E . F o r m e n t i , L . M a r g a r a ( 1 9 9 8 ) . “ T o p o l o g i c a l c h a o s a n d C A ” . I n M . D e l o r m e , J . M a z o y e r . C e l l u l a r a u t o m a t a : a p a r a l l e l m o d e l . S p r i n g e r . p . 2 3 9 . I S B N 9 7 8 - 0 - 7 9 2 3 - 5 4 9 3 - 2 . https://books.google.co.jp/books?id=dGs87s5Pft0C&pg=PA239&redir_esc=y&hl=ja (28) ^ B u r t o n H . V o o r h e e s ( 1 9 9 6 ) . C o m p u t a t i o n a l a n a l y s i s o f o n e - d i m e n s i o n a l c e l l u l a r a u t o m a t a . W o r l d S c i e n t i f i c . p . 8 . I S B N 9 7 8 - 9 8 1 - 0 2 - 2 2 2 1 - 5 . https://books.google.co.jp/books?id=WcZTQHPrG68C&pg=PA8&redir_esc=y&hl=ja (29) ^ M a x G a r z o n ( 1 9 9 5 ) . M o d e l s o f m a s s i v e p a r a l l e l i s m : a n a l y s i s o f c e l l u l a r a u t o m a t a a n d n e u r a l n e t w o r k s . S p r i n g e r . p . 1 4 9 . I S B N 9 7 8 - 3 - 5 4 0 - 5 6 1 4 9 - 1 (30) ^ a b K a r i , J a r r k o 1 9 9 1 , p . 3 7 9 (31) ^ R i c h a r d s o n , D . ( 1 9 7 2 ) . “ T e s s e l l a t i o n s w i t h l o c a l t r a n s f o r m a t i o n s ” . J . C o m p u t e r S y s t e m S c i . 6 ( 5 ) : 3 7 3 – 3 8 8 . d o i : 1 0 . 1 0 1 6 / S 0 0 2 2 - 0 0 0 0 ( 72 ) 8 0 0 0 9 - 6 . (32) ^ M a r g e n s t e r n , M a u r i c e ( 2 0 0 7 ) . C e l l u l a r A u t o m a t a i n H y p e r b o l i c S p a c e s - T o m e I , V o l u m e 1 . A r c h i v e s c o n t e m p o r a i n e s . p . 1 3 4 . I S B N 9 7 8 - 2 - 8 4 7 0 3 - 0 3 3 - 4 . https://books.google.co.jp/books?id=wGjX1PpFqjAC&pg=PA134&redir_esc=y&hl=ja (33) ^ S c h i f f 2 0 1 1 , p . 1 0 3 (34) ^ S e r a f i n o A m o r o s o , Y a l e N . P a t t , D e c i s i o n P r o c e d u r e s f o r S u r j e c t i v i t y a n d I n j e c t i v i t y o f P a r a l l e l M a p s f o r T e s s e l l a t i o n S t r u c t u r e s . J . C o m p u t . S y s t . S c i . 6 ( 5 ) : 4 4 8 - 4 6 4 ( 1 9 7 2 ) (35) ^ S u t n e r , K l a u s ( 1 9 9 1 ) . “ D e B r u i j n G r a p h s a n d L i n e a r C e l l u l a r A u t o m a t a ” . C o m p l e x S y s t e m s 5 : 1 9 – 3 0 . http://www.complex-systems.com/pdf/05-1-3.pdf . (36) ^ K a r i , J a r k k o ( 1 9 9 0 ) . “ R e v e r s i b i l i t y o f 2 D c e l l u l a r a u t o m a t a i s u n d e c i d a b l e ” . P h y s i c a D 45 : 3 7 9 – 3 8 5 . B i b c o d e : 1 9 9 0 P h y D . . . 4 5 . . 3 7 9 K . d o i : 1 0 . 1 0 1 6 / 0 1 6 7 - 2 7 8 9 ( 90 ) 9 0 1 9 5 - U . (37) ^ K a r i , J a r k k o ( 1 9 9 9 ) . “ O n t h e c i r c u i t d e p t h o f s t r u c t u r a l l y r e v e r s i b l e c e l l u l a r a u t o m a t a ” . F u n d a m e n t a I n f o r m a t i c a e 38 : 9 3 – 1 0 7 . (38) ^ D u r a n d - L o s e , J é r ô m e ( 2 0 0 1 ) . “ R e p r e s e n t i n g r e v e r s i b l e c e l l u l a r a u t o m a t a w i t h r e v e r s i b l e b l o c k c e l l u l a r a u t o m a t a ” . D i s c r e t e M a t h e m a t i c s a n d T h e o r e t i c a l C o m p u t e r S c i e n c e AA : 1 4 5 – 1 5 4 . (39) ^ W o l f r a m 2 0 0 2 , p . 60 (40) ^ a b I l a c h i n s k i , A n d r e w ( 2 0 0 1 ) . C e l l u l a r a u t o m a t a : a d i s c r e t e u n i v e r s e . W o r l d S c i e n t i f i c . p p . 4 4 – 4 5 . I S B N 9 7 8 - 9 8 1 - 2 3 8 - 1 8 3 - 5 . https://books.google.co.jp/books?id=3Hx2lx_pEF8C&pg=PA4&redir_esc=y&hl=ja (41) ^ " l i f e - l i k e c e l l u l a r a u t o m a t o n " と い う 用 語 の 初 出 は 少 な く と も B a r r a l , C h a t é & M a n n e v i l l e ( 1 9 9 2 ) ま で 遡 る が 、 こ の 文 献 で は 外 部 総 和 型 全 般 を そ の よ う に 呼 ん で お り 、 2 次 元 に 限 定 し て い な い 。 (42) ^ A d a m a t z k y , A n d r e w , e d ( 2 0 1 0 ) . G a m e o f L i f e C e l l u l a r A u t o m a t a . S p r i n g e r . I S B N 9 7 8 - 1 - 8 4 9 9 6 - 2 1 6 - 2 - こ ち ら は よ り 限 定 的 な 意 味 で " l i f e - l i k e " と 呼 ん で い る 。 (43) ^ h t t p : / / w w w . n e w s c i e n t i s t . c o m / a r t i c l e / d n 2 2 1 3 4 - f i r s t - g l i d e r s - n a v i g a t e - e v e r c h a n g i n g - p e n r o s e - u n i v e r s e . h t m l (44) ^ M u r r a y , J . . M a t h e m a t i c a l B i o l o g y I I . S p r i n g e r . (45) ^ P i v a t o , M : " R e a l L i f e : T h e c o n t i n u u m l i m i t o f L a r g e r t h a n L i f e c e l l u l a r a u t o m a t a " , T h e o r e t i c a l C o m p u t e r S c i e n c e , 3 7 2 ( 1 ) , M a r c h 2 0 0 7 , p p . 4 6 - 6 8 (46) ^ G i l e s , J i m ( 2 0 0 2 ) . “ W h a t K i n d o f S c i e n c e i s T h i s ? ” . ネ イ チ ャ ー ( 4 1 7 ) : 2 1 6 – 2 1 8 . (47) ^ W e i n b e r g , S t e v e n ( O c t o b e r 2 4 , 2 0 0 2 ) . “ I s t h e U n i v e r s e a C o m p u t e r ? ” . T h e N e w Y o r k R e v i e w o f B o o k s ( R e a S . H e d e r m a n ) . http://www.nybooks.com/articles/archives/2002/oct/24/is-the-universe-a-computer/?pagination=false 2 0 1 2 年 10 月 12 日 閲 覧 。 . (48) ^ a b c C o o m b s , S t e p h e n ( F e b r u a r y 1 5 , 2 0 0 9 ) , T h e G e o m e t r y a n d P i g m e n t a t i o n o f S e a s h e l l s , p p . 3 – 4 , http://www.maths.nott.ac.uk/personal/sc/pdfs/Seashells09.pdf 2 0 1 2 年 9 月 2 日 閲 覧 。 (49) ^ P e a k , W e s t ; M e s s i n g e r , M o t t ( 2 0 0 4 ) . “ E v i d e n c e f o r c o m p l e x , c o l l e c t i v e d y n a m i c s a n d e m e r g e n t , d i s t r i b u t e d c o m p u t a t i o n i n p l a n t s ” . P r o c e e d i n g s o f t h e N a t i o n a l I n s t i t u t e o f S c i e n c e o f t h e U S A 1 0 1 ( 4 ) : 9 1 8 – 9 2 2 . B i b c o d e : 2 0 0 4 P N A S . . 1 0 1 . . 9 1 8 P . d o i : 1 0 . 1 0 7 3 / p n a s . 0 3 0 7 8 1 1 1 0 0 . P M C 3 2 7 1 1 7 . P M I D 1 4 7 3 2 6 8 5 . http://www.pnas.org/cgi/content/abstract/101/4/918 . (50) ^ h t t p : / / g i l l y . s t a n f o r d . e d u / p a s t _ r e s e a r c h _ f i l e s / A P a c k a r d n e u r a l n e t . p d f (51) ^ Y v e s B o u l i g a n d ( 1 9 8 6 ) . D i s o r d e r e d S y s t e m s a n d B i o l o g i c a l O r g a n i z a t i o n . p p . 3 7 4 – 3 7 5 (52) ^ A . K . D e w d n e y , T h e h o d g e p o d g e m a c h i n e m a k e s w a v e s , S c i e n t i f i c A m e r i c a n , p . 1 0 4 , A u g u s t 1 9 8 8 . (53) ^ M . G e r h a r d t a n d H . S c h u s t e r , A c e l l u l a r a u t o m a t o n d e s c r i b i n g t h e f o r m a t i o n o f s p a t i a l l y o r d e r e d s t r u c t u r e s i n c h e m i c a l s y s t e m s , P h y s i c a D 3 6 , 2 0 9 - 2 2 1 , 1 9 8 9 . (54) ^ a b T h e E v o l u t i o n o f E m e r g e n t C o m p u t a t i o n , J a m e s P . C r u t c h f i e l d a n d M e l a n i e M i t c h e l l ( S F I T e c h n i c a l R e p o r t 9 4 - 0 3 - 0 1 2 ) (55) ^ h t t p : / / w w w . s a n t a f e . e d u / a b o u t / p e o p l e / p r o f i l e / M e l a n i e % 2 0 M i t c h e l l (56) ^ a b T h e E v o l u t i o n a r y D e s i g n o f C o l l e c t i v e C o m p u t a t i o n i n C e l l u l a r A u t o m a t a , J a m e s P . C r u t c h f e l d , M e l a n i e M i t c h e l l , R a j a r s h i D a s ( I n J . P . C r u t c h ¯ e l d a n d P . K . S c h u s t e r ( e d i t o r s ) , E v o l u t i o n a r y D y n a m i c s | E x p l o r i n g t h e I n t e r p l a y o f S e l e c t i o n , N e u t r a l i t y , A c c i d e n t , a n d F u n c t i o n . N e w Y o r k : O x f o r d U n i v e r s i t y P r e s s , 2 0 0 2 . ) (57) ^ E v o l v i n g C e l l u l a r A u t o m a t a w i t h G e n e t i c A l g o r i t h m s : A R e v i e w o f R e c e n t W o r k , M e l a n i e M i t c h e l l , J a m e s P . C r u t c h f e l d , R a j a r s h i D a s ( I n P r o c e e d i n g s o f t h e F i r s t I n t e r n a t i o n a l C o n f e r e n c e o n E v o l u t i o n a r y C o m p u t a t i o n a n d I t s A p p l i c a t i o n s ( E v C A ' 9 6 ) . M o s c o w , R u s s i a : R u s s i a n A c a d e m y o f S c i e n c e s , 1 9 9 6 . ) (58) ^ T o m a s s i n i , M . ; S i p p e r , M . ; P e r r e n o u d , M . ( 2 0 0 0 ) . “ O n t h e g e n e r a t i o n o f h i g h - q u a l i t y r a n d o m n u m b e r s b y t w o - d i m e n s i o n a l c e l l u l a r a u t o m a t a ” . I E E E T r a n s a c t i o n s o n C o m p u t e r s 49 ( 10 ) : 1 1 4 6 – 1 1 5 1 . (59) ^ W o l f r a m , S . " C r y p t o g r a p h y w i t h C e l l u l a r A u t o m a t a " , I n A d v a n c e s i n C r y p t o l o g y : C R Y P T O ' 8 5 P r o c e e d i n g s [ W i l l i a m s , H . C . ( E d . ) ] . L e c t u r e N o t e s i n C o m p u t e r S c i e n c e 2 1 8 . S p r i n g e r - V e r l a g , 4 2 9 – 4 3 2 , 1 9 8 6 . (60) ^ " C e l l u l a r A u t o m a t o n P u b l i c - K e y C r y p t o s y s t e m " , C o m p l e x S y s t e m s , V o l . 1 , N o . 1 ( 1 9 8 7 ) . (61) ^ I l a c h i n s k i 2 0 0 1 , p . 6 6 0 (62) ^ I l a c h i n s k i 2 0 0 1 , p p . 6 6 1 – 6 6 2 (63) ^ J . P . C r u t c h f i e l d , " T h e C a l c u l i o f E m e r g e n c e : C o m p u t a t i o n , D y n a m i c s , a n d I n d u c t i o n " , P h y s i c a D 7 5 , 1 1 - 5 4 , 1 9 9 4 . (64) ^ M . M i n s k y , " C e l l u l a r V a c u u m " , I n t e r n a t i o n a l J o u r n a l o f T h e o r e t i c a l P h y s i c s 2 1 , 5 3 7 - 5 5 1 , 1 9 8 2 . (65) ^ K . Z u s e , " T h e C o m p u t i n g U n i v e r s e " , I n t . J o u r . o f T h e o . P h y . 2 1 , 5 8 9 - 6 0 0 , 1 9 8 2 . (66) ^ E . F r e d k i n , " D i g i t a l m e c h a n i c s : a n i n f o r m a t i o n a l p r o c e s s b a s e d o n r e v e r s i b l e u n i v e r s a l c e l l u l a r a u t o m a t a " , P h y s i c a D 4 5 , 2 5 4 - 2 7 0 , 1 9 9 0 (67) ^ i L a b s (68) ^ F . B e r t o , G . R o s s i , J . T a g l i a b u e , T h e M a t h e m a t i c s o f t h e M o d e l s o f R e f e r e n c e , C o l l e g e P u b l i c a t i o n s , 2 0 1 0 (69) ^ W e i s s t e i n , E r i c W . . “ C e l l u l a r A u t o m a t o n ” . 2 0 1 1 年 3 月 13 日 閲 覧 。 (70) ^ t h e H a c k e r E m b l e m p a g e o n E r i c S . R a y m o n d ' s s i t e (71) ^ B l a c k f o r d , R u s s e l l ; I k i n , V a n ; M c M u l l e n , S e a n ( 1 9 9 9 ) . “ G r e g E g a n ” . S t r a n g e c o n s t e l l a t i o n s : a h i s t o r y o f A u s t r a l i a n s c i e n c e f i c t i o n . C o n t r i b u t i o n s t o t h e s t u d y o f s c i e n c e f i c t i o n a n d f a n t a s y . 80 . G r e e n w o o d P u b l i s h i n g G r o u p . p p . 1 9 0 – 2 0 0 . I S B N 9 7 8 - 0 - 3 1 3 - 2 5 1 1 2 - 2 (72) ^ H a y l e s , N . K a t h e r i n e ( 2 0 0 5 ) . “ S u b j e c t i v e c o s m o l o g y a n d t h e r e g i m e o f c o m p u t a t i o n : i n t e r m e d i a t i o n i n G r e g E g a n ' s f i c t i o n ” . M y m o t h e r w a s a c o m p u t e r : d i g i t a l s u b j e c t s a n d l i t e r a r y t e x t s . U n i v e r s i t y o f C h i c a g o P r e s s . p p . 2 1 4 – 2 4 0 . I S B N 9 7 8 - 0 - 2 2 6 - 3 2 1 4 7 - 9 (73) ^ K a s m a n , A l e x . “ M a t h F i c t i o n : B l o o m ” . 2 0 1 1 年 3 月 27 日 閲 覧 。 (74) ^ h t t p : / / w w w . s f w r i t e r . c o m / s y w 1 . h t m (75) ^ h t t p : / / w w w . d e z e e n . c o m / 2 0 1 4 / 0 9 / 2 6 / f r a n c i s - b i t o n t i - 3 d - p r i n t e d - m o l e c u l e - s h o e s - a d o b e - s t r a t a s y s / 参考文献 [ 編集 ]
『アインシュタインの部屋』上・下 - エド・レジス著／大貫昌子訳 工作舎 ISBN 978-4-87502-171-1 ・ISBN 978-4-87502-172-8
『コンピューターレクリエーションI 遊びの発想』 - A.K.デュードニー著 別冊サイエンス32
『哲学者クロサキと工学者アイハラの神はカオスに宿りたもう』 - 合原 一幸、 黒崎 政男 共著
『箱玉系の数理』 - 時弘哲治 朝倉書店
Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life . Oxford University Press . ISBN 0198531001 Chopard, Bastien; Droz, Michel (2005). Cellular Automata Modeling of Physical Systems . Cambridge University Press . ISBN 0-521-46168-5 Gutowitz, Howard, ed (1991). Cellular Automata: Theory and Experiment . MIT Press . ISBN 9780262570862 Ilachinski, Andrew (2001). Cellular Automata: A Discrete Universe . World Scientific. ISBN 9789812381835 Kier, Lemont B.; Seybold, Paul G.; Cheng, Chao-Kun (2005). Modeling Chemical Systems using Cellular Automata . Springer. ISBN 9781402036576 Schiff, Joel L. (2011). Cellular Automata: A Discrete View of the World . Wiley & Sons, Inc. ISBN 9781118030639 Wolfram, Stephen (2002). A New Kind of Science . Wolfram Media . ISBN 978-1579550080 Barral, Bernard; Chaté, Hugues; Manneville, Paul (1992). “Collective behaviors in a family of high-dimensional cellular automata”. Physics Letters A 163 (4): 279–285. doi :10.1016/0375-9601(92)91013-H . Cellular automaton FAQ from the newsgroup comp.theory.cell-automataA. D. Wissner-Gross. 2007. Pattern formation without favored local interactions
"Neighbourhood Survey" 三角格子や大きな近傍のセル・オートマトンなどを論じているvon Neumann, John, 1966, The Theory of Self-reproducing Automata , A. Burks, ed., Univ. of Illinois Press, Urbana, IL.
『自己増殖オートマトンの理論』- フォン・ノイマン著 岩波書店
Cosma Shalizi's Cellular Automata Notebook 書誌情報が豊富Wolfram's papers on CAs
A.M. Turing. 1952. The Chemical Basis of Morphogenesis. Phil. Trans. Royal Society , vol. B237, pp. 37 – 72. - 連続的オートマトンの一種を提唱している。
Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996.)
The Evolutionary Design of Collective Computation in Cellular Automata, James P. Crutchfeld, Melanie Mitchell, Rajarshi Das (In J. P. Crutch¯eld and P. K. Schuster (editors), Evolutionary Dynamics|Exploring the Interplay of Selection, Neutrality, Accident, and Function. New York: Oxford University Press, 2002.)
The Evolution of Emergent Computation, James P. Crutchfield and Melanie Mitchell (SFI Technical Report 94-03-012)
Ganguly, Sikdar, Deutsch and Chaudhuri "A Survey on Cellular Automata" Zuse´s publications on CA-based physics (1967, 1969, 1970) , with comments by Juergen SchmidhuberKlaus Sutner. 1989. A Note on Culik-Yu Classes Complex Systems 3 (1989) 107-115.
関連項目 [ 編集 ] 外部リンク [ 編集 ]
-完全、クラス3は
-完全に所属する。
ウルフラムの分類に触発され、CAを形式的に厳密に分類しようとする試みもなされてきた。例えば、CulikとYuは3つのwell-definedなクラス︵そしてそれらのどれにも分類されない4番目のクラス︶を提案した。これを Culik-Yu クラスなどと呼び、ある規則群がどのクラスに属するかの判定は決定不能だと証明された[27][28][29]。
