ガイドツアー 複雑系の世界 サンタフェ研究所講義ノートから

この本は複雑系の研究の総本山ともいえるサンタフェ研究所の研究者メラニー・ミッチェルが一般聴衆を対象にして行った一連の講義をまとめたものです。フラクタルやべき乗分布、ネットワーク理論、カオス、生命の進化など複雑系に関係する内容をガイドツアーのようにわかりやすくまとめてくれています。入門書でありながら科学書としての評価が大変高く、英王立協会による２０１０年推薦科学図書の1冊として、またアマゾン・コムによる２００９年ベスト科学書の1冊となっているそうです。

基本的には数式がでてこないので読み流すことはできますが、チューリングマシンとセル・オートマトンのところは少し手強いです。手強いけれど簡単な実例に沿って丁寧に解説してくれているので時間をかけて読んでみました。

チューリングマシンとは、

• マス目に分割され、その上にシンボルが書かれているテープ
• テープからシンボルを読み取りまたテープにシンボルを書き込むテープヘッド
• テープヘッドに次に何をすべきかを指示する一揃いのルール

から構成されています。チューリングはこのチューリングマシンで

1. 「一定の手続き」と言う概念を厳密に定義し
2. この定義がチューリングマシンという形態をとって、プログラム可能な電子計算機の発明の基盤を築いた。
3. 何が計算可能であるかに関して限界があるという、ほとんど誰もが予期していなかった事実を明かにしています。

本書ではチューリングマシンの動作を1ステップずつ噛んで含めるように解説しており、大変わかりやすいのですが、３の計算限界（計算不可能性）の証明のところは5回読んでもしっくりわかりません。著者もこの本で一番ややこしいところだと言ってます。

セル・オートマトンとは数多くのセルから構成される格子平面であり、単体として機能する各セルが近傍の状態によってオンになったりオフになったりするものです。これは、中央処理装置がないにも関わらず、予測困難な極めて複雑な振る舞いを示す場合があり、自然界、生命の複雑なシステムを解く鍵になるものです。セル・オートマトンの振る舞いについてもステップごとに丁寧に説明されているので時間をかければちゃんとわかった気分になれます。

チューリングマシンとセル・オートマトン。このふたつを知ることができただけでも読んで良かったと思う。

こちらもどうぞ
複雑系　科学革命の震源地：http://d.hatena.ne.jp/benton/20070729/p2

ガイドツアー　複雑系の世界: サンタフェ研究所講義ノートから