チューリング完全
出典: フリー百科事典『ウィキペディア（Wikipedia）』
計算理論で、ある計算のメカニズムがチューリング機械と同じ計算能力をもつとき、その言語はチューリング完全（チューリングかんぜん、Turing-complete）あるいは計算完備であるという。
ラムダ計算はチューリング完全である。これは、Yコンビネータによりラムダ計算の範囲内で再帰ができ、これがループと等価な能力をもつことから証明できる。そのほか、μ再帰関数やマルコフアルゴリズムもチューリング完全である（チャーチ＝チューリングのテーゼも参照）。
どれだけ単純なもので、チューリング完全を満たせるか、という問題については、「ウルフラムの 2, 3 チューリングマシン」の万能性が証明されている[1]。
多くのプログラミング言語はチューリング完全である。一見単純な機能しか持たない言語がチューリング完全である例としては、純LISP、Lazy K、Brainfuckなどがある（あくまで「計算可能」という観点によるものであって計算量を考えてはいないため、普通のプログラミング言語ではオーダーNで可能な計算にオーダー2Nを必要とする場合などもある）。
正規表現はチューリング完全でない（チョムスキー階層も参照）。SQLや、ループの書けない表計算マクロなども、チューリング完全でない。
[編集] 参考
[編集] 関連項目
 |
この「チューリング完全」はコンピュータに関連した書きかけ項目です。この記事を加筆して下さる協力者を求めています（PJ コンピュータ / Portal:コンピュータ）。 |
