チューリングコンプリート

一般に、プログラミング言語と称されるものは、ほぼ全てがチューリングコンプリートである。

単純そうに見えても、能力を満たす言語としては、Brainfuck、Whitespace、Grassなどといったものがある。

現在使われている主流のプログラミング言語は、このような単純な言語に、更に使いやすさを加えたものである、ともいえる。

次のようなものは、チューリングコンプリートではない。

• SQL
• 正規表現
• ループを表現できないマクロ等

数式ではあるが、λ計算(ラムダ計算)はチューリングコンプリートである。数式にループの機能など存在し得ないが、しかしλ計算は不動点コンビネータ(Yコンビネータ)で再帰を定義することが可能であり、これが事実上ループと等価の効果をもたらすため、λ計算はチューリングコンプリートなのである。