チューリング陥穽

チューリング陥穽(チューリングかんせい、英語: "Turing tarpit" もしくは "Turing tar-pit" )とは、機能的にはチューリング完全で任意の計算可能な機能を記述できるが、一方で実用性を失うほど記述が難しいような、プログラミング言語・コンピュータインターフェースである。この語は1982年に"Epigrams on Programming^[1]"(直訳「プログラミングに於ける警句集」)を書いたAlan Perlisによって使われた。

54番目の警句 - 全てが可能だが、有用なことは何一つ簡単にはできない「チューリング陥穽」に気をつけろ。

如何なるプログラミング言語でもチューリング完全であれば、任意のプログラムを書き表すことができる。従って厳密には、全てのプログラミング言語の表現能力は等価である。裏を返せば、この理論上の表現能力は言語の実用性と同一ではないことを意味する。チューリング陥穽の特徴は、プログラミングしたい問題の詳細な部分にまでユーザーに扱わせるほど単純化された抽象機械である。

チューリング完全を保てるギリギリまで機能を省いているため、難解プログラミング言語のいくつか、例えばBrainfuck等がチューリング陥穽の典型として挙げられる。これらの言語を嗜むことは、ある種の数学的娯楽である。極めて困難だが数学上はチューリング完全には違いない言語の上に、初歩的なプログラム機能を実現する。この頭の体操をチューリング陥穽はプログラマに提供している。