チューリング完全
計算理論で、あるプログラミング言語チューリング機械と同じ計算能力をもつとき、その言語はチューリング完全(チューリングかんぜん、Turing-complete)あるいは計算完備であるという。多くのプログラミング言語はチューリング完全である。一見単純な機能しか持たない言語がチューリング完全である例としては、5つの基本関数のみを持つ関数型言語の純LISP、さらに基本関数を3つに絞ったLazy K、8つの命令のみ持つ手続き型言語のBrainfuckなどである。ただしこのような言語は、使いやすさを含めた現実的な処理能力が他の言語に比肩するとはいえない。正規表現はチューリング完全でない(チョムスキー階層も参照)。SQLや、ループの書けない表計算マクロなども、チューリング完全でない。ラムダ計算はチューリング完全である。これは、Yコンビネータによりラムダ計算の範囲内で再帰ができ、これがループと等価な能力をもつことから証明できる。そのほか、μ再帰関数マルコフアルゴリズムもチューリング完全である(チャーチ=チューリングのテーゼも参照)。

1 関連項目