チューリング完全

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルチューリング完全(チューリングかんぜん、Turing-complete)あるいは計算完備であるという。

チャーチ=チューリングのテーゼによれば「計算可能関数」は、それを計算しようとする計算モデルがチューリング完全であれば計算できる。

たとえばC言語Javaなどをはじめとする、一般的なプログラミング言語(の背景にある計算モデル)はほぼ全てチューリング完全である。一見単純な機能しか持たない言語がチューリング完全な例としては、純LISPLazy KBrainfuckなどがある。究極的に単純な計算モデルとしては「ウルフラムの2状態3記号チューリングマシン」(w:Wolfram's 2-state 3-symbol Turing machine)がチューリング完全であると証明されている。

チューリング完全かどうかという事は、計算可能性理論の問題である。計算複雑性の分野の問題である時間や記憶容量の消費量については考えない。表計算における数式の処理などで、繰り返し処理を「どうやっても実現できなければ」[1]それはチューリング完全ではない。

「多くのコンピュータ言語のうち、特にチューリング完全な言語をプログラミング言語と呼ぶことが多い。」とする説明は間違いである。しばしば設定ファイルの記法などがチューリング完全であることがあるが(たとえばSendmailの設定ファイル)、それを「プログラミング言語」とは普通は呼ばない(前述のように、たった2状態3記号しかないチューリングマシンでもチューリング完全が可能である)。

理論[編集]

チューリングマシン以外にチューリング完全な計算モデルとしては、ラムダ計算μ再帰関数マルコフアルゴリズムなどが挙げられる。ラムダ計算がチューリング完全であることを証明する上で重要な点は、Yコンビネータによりラムダ計算の範囲内で再帰ができ、これがループと等価な能力をもつことである。

チューリング完全性に関する重要なトピックとして、チャーチ=チューリングのテーゼが挙げられる。

スティーブン・ウルフラムは、以前からこういった問題を追求していたことで知られる一人だが、最も単純でありながらチューリング完全であろう計算モデルとして、2状態3記号のチューリングマシン、「2, 3 チューリングマシン」に目を付け、2007年にその万能性(あるいはその否定)の証明に2万5000ドルの懸賞金をかけた。問題提起から47日後、バーミンガム大学コンピューター科学部の学生だったAlex Smithが肯定的(万能である、とする)証明を提出し[2]、懸賞は確定した。

性質[編集]

チューリングマシンの重要な性質として、停止性問題が挙げられる。

まず、チューリングマシンは、必ず計算を完了できるわけではない。プログラミングの分野で無限ループなどと呼ばれるようなものであるが、計算が止まらないことがあるのである。計算理論ではそのような可能性のあるものを手続きと呼び、有限の時間内に必ず停止するアルゴリズムと区別することがある。ここで、計算が止まるかどうかという判定問題を、あらかじめ決定する手順がないというのが停止性問題の証明するところである。

停止性問題の否定的な結論は、「計算可能」であることの限界を示している。しかし、それはある意味であたりまえの結果である。なぜなら、たとえば「これこれの条件を満たす自然数は存在しない」という形をした数学の未解決問題があったとする。自然数は 1, 2, 3... というようにして数え上げが可能であるし、数学の問題にある「これこれの条件を満たす」というような条件は、コンピュータプログラム中の数式と条件判断として記述できるであろう。もし、どんなコンピュータプログラムでも止まるかどうかが判定できるのであれば、「その条件を満たす自然数を見つけたら止まる」というプログラムが停止するかどうかを判定することで、そのような数学の問題が解決できてしまうことになる。そのように考えれば、停止性問題の結論が否定的であるのはあたりまえと言えよう。

参考[編集]

  1. ^ 「書けない」ではない。直截には書くことができなくても、可能なあらゆる手段のどれか一つによって実現できればよい。
  2. ^ http://www.wolframscience.com/prizes/tm23/solved.html

関連項目[編集]