チューリングコンプリート - 通信用語の基礎知識

プログラミング言語などにおいて、それがチューリングマシンと同じ能力を持っていること。チューリング完全。

概要

一般に、プログラミング言語と称されるものは、ほぼ全てがチューリングコンプリートである。但しチューリングコンプリートだからといってそれが全てプログラミング言語であるとは限らない。

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

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

特徴

条件

チューリングマシンと同じ能力を持てばよい。最低限、次の機能を持っていれば、それは、記述性や可読性に問題があったとしても、チューリングコンプリートとなる。

つまり「読んで」「書いて」「比較できて」「条件ジャンプまたはプログラムのループができる」ことが少なくとも必要であると言える。

この他、実用面においては、結果を画面に出す機能なども必要だろう。

そしてこれだけの機能が備わっていることから、BrainfuckやWhitespaceなどは、明らかに実用的ではないがチューリングコンプリートと言える。

除外

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

次のようなものは、チューリングコンプリートだとされているが、プログラミング言語とは考えられていない。

元々SQLはチューリングコンプリートではないが、OracleがSQLをプログラミング言語に改造したPL/SQLはチューリングコンプリートである。再帰クエリーが導入されたSQL:1999でSQL自体もチューリングコンプリートになったとされている。

TeX

マークアップ言語であり版組エンジンであるTeXは、プログラムを書くことができる。

作者のKnuthは、TeXをプログラミング言語にするつもりはなかったと思われるが、版組に必要な機能を詰め込んだ結果、最終的に「チューリングコンプリートの関数型言語」になってしまったという、非常に稀な例である。

ラムダ計算

数式ではあるが、λ計算(ラムダ計算)はチューリングコンプリートである。

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

リンク

用語の所属