チューリング完全
チューリングマシンの重要な性質として、停止性問題が挙げられる。
まず、チューリングマシンは、必ず計算を完了できるわけではない。プログラミングの分野で無限ループなどと呼ばれるようなものであるが、計算が止まらないこともある。計算理論ではそのような可能性のあるものを手続きと呼び、有限の時間内に必ず停止するアルゴリズムと区別することがある。ここで、計算が止まるかどうかという判定問題を、あらかじめ決定する手順がないというのが停止性問題の証明するところである。
停止性問題の否定的な結論は、計算可能であることの限界を示している。しかし、それはある意味であたりまえの結果である。なぜなら、たとえば「これこれの条件を満たす自然数は存在しない」という形をした数学の未解決問題があったとする。自然数は 1, 2, 3, ... というようにして数え上げが可能であるし、数学の問題にある「これこれの条件を満たす」というような条件は、コンピュータプログラム中の数式と条件判断として記述できるであろう。もし、どんなコンピュータプログラムでも止まるかどうかが判定できるのであれば、「その条件を満たす自然数を見つけたら止まる」というプログラムが停止するかどうかを判定することで、そのような数学の問題が解決できてしまうことになる。そのように考えれば、停止性問題の結論が否定的であるのはあたりまえと言えよう。