計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全(チューリングかんぜん、Turing-complete)あるいは計算完備であるという。チャーチ=チューリングのテーゼによれば「計算可能関数」は、それを計算しようとする計算モデルがチューリング完全であれば計算できる。一般的なプログラミング言語の背景にある計算モデルの多くはチューリング完全である。K、Brainfuckなどがある。究極的に単純な計算モデルとしては「ウルフラムの2状態3記号チューリングマシン(英語版)がチューリング完全であると証明されている。チューリング完全かどうかという事は、計算可能性理論の問題である。計算複雑性の分野の問題である時間や記憶容量の消費量については考えない。表計算における数式の処理などで、繰り返し処理を「どうやっても実現できなければ」[1]それはチューリング完全ではない。コンピュータ言語のうち、少なくともチューリング完全でなければプログラミング言語とは呼ばれない。逆にチューリング完全であるにも関わらず慣例的にプログラミング言語とは呼ばれないものもある。理論[編集]チューリングマシン以外にチューリング完全な計算モデルとしては、ラムダ計算やμ再帰関数やマルコフアルゴリズムなどが挙げられる。ラムダ計算がチューリング完全であることを証明する上で重要な点は、Yコンビネータによりラムダ計算の範囲内で再帰ができ、これがループと等価な能力をもつことである。チューリング完全性に関する重要なトピックとして、チャーチ=チューリングのテーゼが挙げられる。チューリングマシン」に目を付け、2007年にその万能性(あるいはその否定)の証明に2万5000ドルの懸賞金をかけた。問題提起から47日後、バーミンガム大学コンピューター科学部の学生だったアレックス・スミスが肯定的(万能である、とする)証明を提出し[2]、懸賞は確定した。性質[編集]チューリングマシンの重要な性質として、停止性問題が挙げられる。チューリングマシンは、必ず計算を完了できるわけではない。プログラミングの分野で無限ループなどと呼ばれるようなものであるが、計算が止まらないことがあるのである。計算理論ではそのような可能性のあるものを手続きと呼び、有限の時間内に必ず停止するアルゴリズムと区別することがある。ここで、計算が止まるかどうかという判定問題を、あらかじめ決定する手順がないというのが停止性問題の証明するところである。停止性問題の否定的な結論は、「計算可能」であることの限界を示している。それはある意味であたりまえの結果である。「これこれの条件を満たす自然数は存在しない」という形をした数学の未解決問題があったとする。いうようにして数え上げが可能であるし、数学の問題にある「これこれの条件を満たす」というような条件は、コンピュータプログラム中の数式と条件判断として記述できるであろう。どんなコンピュータプログラムでも止まるかどうかが判定できるのであれば、「その条件を満たす自然数を見つけたら止まる」というプログラムが停止するかどうかを判定することで、そのような数学の問題が解決できてしまうことになる。そのように考えれば、停止性問題の結論が否定的であるのはあたりまえと言えよう。「書けない」ではない。直截には書くことができなくても、可能なあらゆる手段のどれか一つによって実現できればよい。http://www.wolframscience.com/prizes/tm23/solved.html関連項目[編集]チューリング還元アルゴリズム情報理論Smn定理この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています(PJ:コンピュータ/P:コンピュータ)。何の日(2月26日)ナポレオン・ボナパルトがエルバ島を脱出(1815年)フランス第二共和政が宣言される(1848年)ヴェルサイユ仮講和条約が締結され普仏戦争が終結(1871年)ベルリン会議終了。列強によるアフリカ分割の原則を確認(1885年)二・二六事件(1936年)イギリスが原爆保有を公表(1952年)ゴダイの虐殺(1966年)国連事務総長のウ・タントが、アースデイ宣言書に署名(1971年)ニューヨーク世界貿易センタービルで爆弾テロ(1993年)ダルフール紛争勃発(2003年)マケドニアの大統領ボリス・トライコフスキが乗った政府専用機がサラエヴォ南方80kmの山岳地帯で墜落。