チューリング完全
計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全（チューリングかんぜん、Turing-complete）あるいは計算完備であるという。
万能チューリングマシンと同等の計算を実現できるという事は、決められた手順にしたがって計算できるあらゆる問題を処理することができることを意味していると考えられ、万能チューリングマシンで実現不可能な計算のメカニズムを可能にする方法は知られていない。簡単に言えば、チューリング完全であれば、実現可能なアルゴリズムや手続きはすべて処理できるということを意味している。
多くのコンピュータ言語のうち、特にチューリング完全な処理を表現できる言語のことをプログラミング言語と呼ぶことが多い。正規言語やSQLや繰り返し処理の書けない表計算の数式などの処理はチューリング完全ではないが、汎用的に使われるC言語やJava言語などの言語の処理の多くが、チューリング完全である。一見単純な機能しか持たない言語がチューリング完全な処理を記述できる例としては、純LISP、Lazy K、Brainfuckなどがある。なお、チューリング完全かどうかという事は、計算可能性理論の問題である。計算複雑性の分野の問題である時間や記憶容量の消費量については考えない。
理論
理論的には、先ほど説明した「言語」というのは、表現方法としての記号の羅列であり、厳密には、その処理方式である「計算モデル」とは異なる。
チューリングマシン以外にチューリング完全な計算モデルとしては、ラムダ計算やμ再帰関数やマルコフアルゴリズムなどが挙げられる。ラムダ計算がチューリング完全であることを証明する上で重要な点は、Yコンビネータによりラムダ計算の範囲内で再帰ができ、これがループと等価な能力をもつことである。
チューリング完全性に関する重要なトピックとして、チャーチ＝チューリングのテーゼが挙げられる。
最も単純な計算モデルとして、「ウルフラムの 2, 3 チューリングマシン」の万能性が証明されている[1]。
性質
チューリングマシンの重要な性質として、停止性問題が挙げられる。
まず、チューリングマシンは、必ず計算を完了できるわけではない。プログラミングの分野で無限ループなどと呼ばれるようなものであるが、計算が止まらないことがあるのである。計算理論ではそのような可能性のあるものを手続きと呼び、有限の時間内に必ず停止するアルゴリズムと区別することがある。
ここで、計算が止まるかどうかという判定問題を、あらかじめ決定する手順がないというのが停止性問題の証明するところである。この事実は、（万能）チューリングマシンとチューリング完全性の一つの限界を示している。
