チューリング完全

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

多くの算譜言語はチューリング完全である。一見単純な機能しか持たない言語がチューリング完全である例としては、5つの基本関数だけをもつ純LISPが挙げられる。またBrainfuckもそうである。ただしこのような言語は、使いやすさを含めた現実的な処理能力が他の言語に比肩するとはいえない。

正規表現はチューリング完全でない。SQLや、ループのかけない表計算マクロなども、チューリング完全でない。

ラムダ計算はチューリング完全である。これは、Y結合子と呼ばれる手法によりラムダ計算の範囲内で再帰を摸倣でき、これがループと等価な能力をもつことから証明できる。