Turing Complete
チューリング完全とは、計算システムがチューリングマシンをシミュレートでき、あらゆる計算可能な関数を計算できることを意味する。汎用計算能力の基準である。
目的
言語やシステムの計算能力の上限を判定し、計算可能性の限界を理解する。
メカニズム
条件分岐 + 任意のループ/再帰 + 読み書きメモリが必要である。ほとんどのプログラミング言語はチューリング完全である。HTML+CSS（議論あり）、SQL（再帰 CTE）、正規表現（後方参照）は境界線上にある。停止性問題は決定不能である。
ユースケース
- 計算理論を学ぶこと
- プログラミング言語の表現力
- 計算可能かどうかの判定