p122

カオスの縁と計算能力

カオスの縁が計算能力的にもいちばん高いのではないかという憶測は，たとえばセルオートマトンでは一般に正しくないが，カオティクでも周期的でもない微妙なセルオートマトンでさえユニバーサルな計算能力を持ちうることはM. Cook によって，S. Wolfram の予想を証明する形でしめされている．この事実自体は次の仕事からも推測できるように驚くべきことでもないが，証明法にはおもしろみがあるというのが専門家の評である( http://en.wikipedia.org/wiki/Rule 110 cellular automaton 参照)．A. Dhar, P. Lakdawala, G. Mandal, and S. R. Wadia, “Role of initial conditions in the classification of the rule space of cellular automata dynamics,” Phys. Rev. E  51 , 3032-3037 (1995) はユニバーサルチューリング機械を実現するセルオートマトンをいろいろ作り，そのダイナミクスがどんなものであるかを調べた．その結果，それはいわゆるカオスの縁のような系でなくてよく，カオティクな状態を与えるセルオートマトンでいいことなどを示している．