多数のチューリングマシンで複雑系は、作れるか？

質問

１個のチューリングマシンは、複雑系ではないと思います（多分ですが）
多数のチューリングマシンで複雑系は、作れるのでしょうか？
多数のチューリングマシンが、途中経過を　やりとりすると、結果がカオスになってもいいような気がします。
どうなのでしょうか？

PS。
カオスをｆ(x)とすると、ｘとｘ＋dx　で、カオスなら結果が異なるので、
デジタルな系では、どんなに複雑でも、カオスは、発生しない
ということで、いいでしょうか？
もし、そうなら、デジタルな系では、複雑系を作れない　ということで合ってますか？

回答No.2

ibm_111 · ベストアンサー

＞領域が無限ならその必要はない（カオスになる）

だいたいそのとおりです。
厳密にはカオスにならないこともあるわけですから、
「カオスになりうる」ぐらいにしとくといいでしょう。

あと先の回答で少々コメント追加

>初期値x0を1ビットずつシフトしたり反転したりする構造になっています。

「シフトする」ということが重要です。
カオスというのは、おおざっぱには、
x0=0.1010110100・・・
x1=0.010110100・・・
x2=0.10110100・・・
x3=0.0110100・・・
・・・
という構造を持っています。
このように書くと、初期状態に対する摂動が、
将来の状態に指数関数的に影響するというのは自明ですね
また、離散構造ではカオスにならなさそう、ということも分かります。

お礼

ありがとうございました。
よくわかりました。

回答No.3

stomachman

> 多数のチューリングマシン

　チューリングマシン（あるいはemulation）の基本をお分かりでないようです。チューリングマシンが多数あってヤヤコシく情報をやり取りしたとしても、それが有限個であって決定論的動作をしている限りは、同じことをするチューリングマシン1個が構成可能であり、さらに、万能チューリングマシン1個でも同じことができる。（だからこそ「万能チューリングマシン」。）従って、「多数のチューリングマシン」を考えても何も新しいことは出てきません。

　さて、何をもって「カオス」と呼ぶか、ということについては諸説・疑義がいろいろある所ですね。しかし特に「周期性を持たない」ということだけに注目すると、数値の表現の桁数をどんどん増やして行けば良いでしょう。有理数表現を使うとして、たとえば「n回目のテント写像の結果の分子・分母をそれぞれ((n+1000)番目の素数)倍してから分母に1を足す」のようなカンジの、ワリと簡単な処方でできちゃうのではないかな？（生成される列を局所的に見ればテント写像とほとんど同じなので、大抵の「諸説」には合格できるでしょ。）
　そうだとすれば「デジタルな系では、どんなに複雑でも、カオスは、発生しない」「デジタルな系では、複雑系を作れない」ってことには必ずしもならんのではありませんかね。

お礼

「生成される列を局所的に見ればテント写像とほとんど同じ」ですが、
全体をみれば、循環小数にしかならず、極限をとれば、テント写像ということ
ではないのですか？
極限をとる　ということは、これは実数ですから、「デジタルな系」ではないと思います。

それから、
僕が昔読んだ本では、１個のチューリングマシンでは、多項式時間で解けないが、
∞個のチューリングマシンを並列動作させれば、解ける問題（NPかな？）がある
と書いてありました。（僕の記憶違いかもしれませんが）

回答No.1

ibm_111

あまり自信無いですが、セル・オートマトンはチューリングマシンなのでは？
http://ja.wikipedia.org/wiki/%E3%82%BB%E3%83%AB%E3%83%BB%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3#1.E6.AC.A1.E5.85.83.E3.82.BB.E3.83.AB.E3.83.BB.E3.82.AA.E3.83.BC.E3.83.88.E3.83.9E.E3.83.88.E3.83.B3.E3.81.AE.E4.BE.8B

で、PSについて。
カオスの発生機構は基本的にはテント写像によるものが一番わかり易いです。
http://www.google.co.jp/search?client=ubuntu&channel=fs&q=%E3%83%86%E3%83%B3%E3%83%88%E5%86%99%E5%83%8F&ie=utf-8&oe=utf-8&hl=ja
の最初のpdfを参考にしてください。
テント写像は、2進で考えるとわかりやすいのですが、
初期値x0を1ビットずつシフトしたり反転したりする構造になっています。

まとめると、
1.領域が有限ならアナログ（連続系）でないとカオスにならない
2.領域が無限ならその必要はない。
ということになるかと。

お礼

ご回答、ありがとうございます。

＞領域が無限ならその必要はない（カオスになる）
ということは、チューリングマシンが、セル・オートマトンになるようなので、
（長さ∞のテープに状態を書き込んでいく）
チューリングマシンは、複雑系になりえる

ということで合ってますでしょうか