|
|
| 1行目: |
1行目: |
| − | [[計算理論]]において、ある計算のメカニズムが[[チューリングマシン#万能チューリングマシン|万能チューリングマシン]]と同じ計算能力をもつとき、その[[計算モデル]]は'''チューリング完全'''（チューリングかんぜん、Turing-complete）あるいは'''計算完備'''であるという。
| + | __NOINDEX__ |
| − | | + | {{テンプレート:20180815sk}} |
| − | <!--万能チューリングマシンと同等の計算を実現できるという事は、決められた手順にしたがって計算できるあらゆる問題を処理することができることを意味していると考えられ、万能チューリングマシンで実現不可能な計算のメカニズムを可能にする方法は知られていない。簡単に言えば、'''チューリング完全であれば、実現可能な[[アルゴリズム]]や手続きはすべて処理できる'''ということを意味している。
| |
| − | --><!-- ← トートロジーをわかりにくく長々と書いただけにしか見えない
| |
| − | -->[[チャーチ＝チューリングのテーゼ]]によれば「[[計算可能関数]]」は、それを計算しようとする計算モデルがチューリング完全であれば計算できる。
| |
| − | | |
| − | 一般的な[[プログラミング言語]]の背景にある計算モデルの多くはチューリング完全である。一見単純な機能しか持たない言語がチューリング完全な例としては、[[Lazy K]]、[[Brainfuck]]などがある。究極的に単純な計算モデルとしては「{{仮リンク|ウルフラムの2状態3記号チューリングマシン|en|Wolfram's 2-state 3-symbol Turing machine}}がチューリング完全であると証明されている。
| |
| − | | |
| − | チューリング完全かどうかという事は、[[計算可能性理論]]の問題である。[[計算複雑性]]の分野の問題である時間や記憶容量の消費量については考えない。表計算における数式の処理などで、繰り返し処理を「どうやっても実現できなければ」<ref>「書けない」ではない。直截には書くことができなくても、可能なあらゆる手段のどれか一つによって実現できればよい。</ref>それはチューリング完全ではない。
| |
| − | | |
| − | [[コンピュータ言語]]のうち、少なくともチューリング完全でなければ[[プログラミング言語]]とは呼ばれない。逆にチューリング完全であるにも関わらず慣例的にプログラミング言語とは呼ばれないものもある。
| |
| − | | |
| − | ==理論==
| |
| − | チューリングマシン以外にチューリング完全な[[計算モデル]]としては、[[ラムダ計算]]や[[μ再帰関数]]や[[マルコフアルゴリズム]]などが挙げられる。ラムダ計算がチューリング完全であることを証明する上で重要な点は、[[不動点コンビネータ|Yコンビネータ]]によりラムダ計算の範囲内で再帰ができ、これがループと等価な能力をもつことである。
| |
| − | | |
| − | チューリング完全性に関する重要なトピック<!--証明じゃない-->として、[[チャーチ＝チューリングのテーゼ]]が挙げられる。
| |
| − | | |
| − | [[スティーブン・ウルフラム]]は、以前からこういった問題を追求していたことで知られる一人だが、最も単純でありながらチューリング完全であろう計算モデルとして、2状態3記号の[[チューリングマシン]]、「2, 3 チューリングマシン」に目を付け、2007年にその万能性（あるいはその否定）の証明に2万5000ドルの懸賞金をかけた。問題提起から47日後、[[バーミンガム大学]]コンピューター科学部の学生だったアレックス・スミスが肯定的（万能である、とする）証明を提出し<ref>http://www.wolframscience.com/prizes/tm23/solved.html</ref>、懸賞は確定した。
| |
| − | | |
| − | ==性質==
| |
| − | チューリングマシンの重要な性質として、[[停止性問題]]が挙げられる。
| |
| − | | |
| − | まず、チューリングマシンは、必ず計算を完了できるわけではない。プログラミングの分野で[[無限ループ]]などと呼ばれるようなものであるが、計算が止まらないことがあるのである。計算理論ではそのような可能性のあるものを[[手続き]]と呼び、有限の時間内に必ず停止する[[アルゴリズム]]と区別することがある。ここで、計算が止まるかどうかという判定問題を、あらかじめ決定する手順がないというのが停止性問題の証明するところである。
| |
| − | | |
| − | 停止性問題の否定的な結論は、「計算可能」であることの限界を示している。しかし、それはある意味であたりまえの結果である。なぜなら、たとえば「これこれの条件を満たす自然数は存在しない」という形をした数学の未解決問題があったとする。自然数は <math>1, 2, 3, \dots</math> というようにして数え上げが可能であるし、数学の問題にある「これこれの条件を満たす」というような条件は、コンピュータプログラム中の数式と条件判断として記述できるであろう。もし、どんなコンピュータプログラムでも止まるかどうかが判定できるのであれば、「その条件を満たす自然数を見つけたら止まる」というプログラムが停止するかどうかを判定することで、そのような数学の問題が解決できてしまうことになる。そのように考えれば、停止性問題の結論が否定的であるのはあたりまえと言えよう。
| |
| − | | |
| − | == 参考 ==
| |
| − | <references/>
| |
| − | | |
| − | == 関連項目 ==
| |
| − | * [[チューリング還元]]
| |
| − | * [[アルゴリズム情報理論]]
| |
| − | * [[Smn定理]]
| |
| − | | |
| − | {{Computer-stub}} | |
| − | {{DEFAULTSORT:ちゆりんくかんせん}}
| |
| − | | |
| − | [[Category:計算理論]]
| |
| − | [[Category:プログラミング言語]]
| |
| − | [[Category:数学に関する記事]]
| |