|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 完 ： [かん] 【名詞】 1. The End (book, film, etc.) 2. Finis ・ 全 ： [ぜん] 1. (n,pref) all 2. whole 3. entire 4. complete 5. overall 6. pan
計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全（チューリングかんぜん、Turing-complete）あるいは計算完備であるという。 チャーチ＝チューリングのテーゼによれば「計算可能関数」は、それを計算しようとする計算モデルがチューリング完全であれば計算できる。 たとえばC言語やJavaなどをはじめとする、一般的なプログラミング言語（の背景にある計算モデル）はほぼ全てチューリング完全である。一見単純な機能しか持たない言語がチューリング完全な例としては、純LISP、Lazy K、Brainfuckなどがある。究極的に単純な計算モデルとしては「ウルフラムの2状態3記号チューリングマシン」（w:Wolfram's 2-state 3-symbol Turing machine）がチューリング完全であると証明されている。 チューリング完全かどうかという事は、計算可能性理論の問題である。計算複雑性の分野の問題である時間や記憶容量の消費量については考えない。表計算における数式の処理などで、繰り返し処理を「どうやっても実現できなければ」〔「書けない」ではない。直截には書くことができなくても、可能なあらゆる手段のどれか一つによって実現できればよい。〕それはチューリング完全ではない。 「多くのコンピュータ言語のうち、特にチューリング完全な言語をプログラミング言語と呼ぶことが多い。」とする説明は間違いである。しばしば設定ファイルの記法などがチューリング完全であることがあるが（たとえばSendmailの設定ファイル）、それを「プログラミング言語」とは普通は呼ばない（前述のように、たった2状態3記号しかないチューリングマシンでもチューリング完全が可能である）。 ==理論== チューリングマシン以外にチューリング完全な計算モデルとしては、ラムダ計算やμ再帰関数やマルコフアルゴリズムなどが挙げられる。ラムダ計算がチューリング完全であることを証明する上で重要な点は、Yコンビネータによりラムダ計算の範囲内で再帰ができ、これがループと等価な能力をもつことである。 チューリング完全性に関する重要なトピックとして、チャーチ＝チューリングのテーゼが挙げられる。 スティーブン・ウルフラムは、以前からこういった問題を追求していたことで知られる一人だが、最も単純でありながらチューリング完全であろう計算モデルとして、2状態3記号のチューリングマシン、「2, 3 チューリングマシン」に目を付け、2007年にその万能性（あるいはその否定）の証明に2万5000ドルの懸賞金をかけた。問題提起から47日後、バーミンガム大学コンピューター科学部の学生だったAlex Smithが肯定的（万能である、とする）証明を提出し〔http://www.wolframscience.com/prizes/tm23/solved.html〕、懸賞は確定した。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「チューリング完全」の詳細全文を読む スポンサード リンク
|