チューリング完全とは何か？

質問

プログラムのチューリング完全性とか万能チューリング機械ってあるじゃないですか。これって、どんな挙動のプログラムでも１言語で書けるって事ですか？

色々と調べてみたのですが、どのサイトもどの資料も説明が難しかったので、ここで質問してます。私の認識は下の通りです。

チューリング完全のプログラムは、FORTRAN、Ｃ言語、Java、JavaScriptなど。

チューリング不完全のプログラムは、TeX、HTML、SQLなど。

要するに、
TeXは数式や楽譜の作成くらいの機能に制限されている。その一方で、FORTRANは数学的計算は勿論、３Ｇゲームや通販サイトなどFORTRAN１言語だけで何でも出来て、ありとあらゆるシステム構築に使えるって事ですか？

チューリングは、戦前イギリスの数学者の名前。彼は次の命題の証明をした。どんな複雑なコンピューターシステムでも中身を分析すれば、四則演算や条件分岐や反復など数種類の小さな基本的システムパーツの組合せになっている。FORTRANやＣ言語はこれを全て含んでいるから、FORTANは何でも出来る。一方、SQLは惜しいがチューリング完全に必須の基本的システムパーツが数種類だけ欠けていて、限界がある。SQLオンリーでゲームを作ろうとすれば、テトリスくらいなら出来るけど、ぷよぷよを作ろうとすれば別の言語を足す事になる。

正しいですか？

回答No.2

kmee · ベストアンサー

私の認識にも間違いがあるかもしれませんが。

チューリング完全とは「チューリングマシンで実現できる」と言っているだけで、実際に何が「チューリングマシンでできる」かには言及していません。

よって
> FORTRANは数学的計算は勿論、３Ｇゲームや通販サイトなどFORTRAN１言語だけで何でも出来て、ありとあらゆるシステム構築に使える

「数学的計算」「３Ｇゲーム」「通販サイト」などが作れるかどうか、と「チューリング完全」かどうかとは、直接の関係はありません。

> TeXは数式や楽譜の作成くらいの機能に制限されている

文章書くだけの人には馴染みが無いかもしれませんが、TeXにはプログラミング言語としての一面があり、これはチューリング完全になっています。

http://ja.wikipedia.org/wiki/Brainfuck
このような、とても実用には使えない言語でも「チューリング完全」です。

また、チューリングマシンは、無限長の記憶領域を持ち、処理時間という概念はありません。
対し、現実のコンピュータは、記憶領域は有限であり、ある程度の処理時間が必要です。
チューリングマシンで「解ける」ことが判っている問題でも、現実のコンピュータではメモリが足りない、あるいは、計算時間が非現実的である、ということが沢山あります。

http://www.youtube.com/watch?v=Q4gTV4r0zRs
少し前に話題になった「組合せ爆発」の動画ですが、この「全ての経路を求める」問題は、正方形の分割数がいくつであろうとも、チューリングマシンを使って解を求めることができます。
しかし、実在のコンピュータで解く場合には、10x10で25万年かかっている、ということで「現実的には解けないのと一緒」と言えます。最後に出てきた高速のアルゴリズムでも、100x100等は「現実的には解けないのと一緒」でしょう。

お礼

さんきゅー

回答No.1

Tacosan

表現に微妙な気はするけどだいたいあってる. でも, 最後の段落はたぶん「構造化定理」だろうから, チューリングは関係ないと思うよ.

ちなみに TeX でオセロはできる.

お礼

さんきゅー