難解プログラミング言語
チューリング陥穽とは、任意の計算可能な機能が記述できるが、一方でその記述が非実用的なほど難しいような、チューリング完全なプログラミング言語のこと。難解プログラミング言語について、言語機能を最小化しようとする場合に、チューリング陥穽と評されることがある。
INTERCALは最初期から現在に至るまで標準的な難解プログラミング言語の一つである。1972年にドン・ウッズ(英語版)とジェイムズ・リヨンによって、慣れ親しんだ如何なる言語とも異なる言語にしようという意図のもとで設計された。その当時に確立された言語であった、Fortran、COBOL、アセンブリ言語といった言語の各要素をパロディー化していた。
長年、INTERCALは論文の言語マニュアルが存在するのみであった。しかし、1990年にUnix上でC言語により実装されると、INTERCALは再び注目された。これが刺激となり難解プログラミング言語の設計が世界的に流行した。
1993年にWouter van Oortmerssenは小規模なスタック型プログラミング言語(英語版)であるFALSEを作成した。コードが理解しにくく紛らわしくなるように構文規則が設計された。コンパイラはわずか1024バイトであった。FALSEに触発され、Urban Müllerは更に小規模で名高いBrainfuckを作成した。Brainfuckのプログラムはたった8種類の文字のみで構成される。Chris PresseyのBefunge (FALSEに似ているが、二次元の命令ポインタがある)とともに、Brainfuckは現在、最もサポートされている難解プログラミング言語の一つとなった。これらはチューリング陥穽の正統的な例であり、プログラミング言語の不必要に分かりにくい側面を示していた。Brainfuckはチューリング機械の一種のP′′言語と関係が深い。