チューリング完全

チューリング完全の最新ニュースをまとめて検索！

計算理論で、あるプログラミング言語がチューリング機械と同じ計算能力をもつとき、その言語はチューリング完全（チューリングかんぜん、Turing-complete）あるいは計算完備であるという。

多くのプログラミング言語はチューリング完全である。一見単純な機能しか持たない言語がチューリング完全である例としては、5つの基本関数だけをもつ純LISP, Brainfuck, Ook!, Lazy Kなどである。ただしこのような言語は、使いやすさを含めた現実的な処理能力が他の言語に比肩するとはいえない。

正規表現はチューリング完全でない（チョムスキー階層も参照）。SQLや、ループのかけない表計算マクロなども、チューリング完全でない。

ラムダ計算はチューリング完全である。これは、Yコンビネータによりラムダ計算の範囲内で再帰ができ、これがループと等価な能力をもつことから証明できる。

[編集] 関連項目

• チューリング還元
• アルゴリズム情報理論
• Smn定理

この「チューリング完全」はコンピュータに関連した書きかけ項目です。この記事を加筆して下さる協力者を求めています（Portal:コンピュータ）。