チューリングマシンでは、入力テープに「バックアップ」を置くことができるため、上で説明した計算モデルには不可能な方法で動作可能である。入力に対して停止しないチューリングマシンを構築することもできる。チューリングマシンはあらゆる入力について停止して答え（言語と入力の判定）を返す機械である。このようにチューリングマシンが必ず停止する言語クラスを帰納言語と呼ぶ。ある言語に含まれる文字列を与えられたときには停止するが、その言語に含まれない文字列を与えられたときに停止しない可能性があるというチューリングマシンもある。このような言語を帰納的可算言語と呼ぶ。
従ってチューリングマシンは計算可能性の限界に関する広範囲な問題を解析する強力な手法である。そこで次の疑問が生まれる。「帰納的可算だが帰納でない言語はあるのか？」である。また、「帰納的可算でもない言語はあるのか？」という疑問も生まれる。
停止問題.
ここでチューリングマシンが判定しようとするのは素数や回文といった単純な問題ではなく、チューリングマシンで他のチューリングマシンに関する質問への答えを得ようとしているのである。詳しくは主項目（チューリングマシンの停止問題）を参照してもらうとして、結論としてこの問いに（あらゆる場合に）答えられるチューリングマシンは構築できない。
すなわち、あるプログラムとその入力があったとき、それが停止するかどうかは単にそのプログラムを実行してみるしかないということになる。そして、停止すれば停止することがわかる。停止しない場合は、それがいつか停止するのか、それとも停止せずに永遠に動作するのかは判らない。あらゆるチューリングマシンに関する記述とあらゆる入力の停止する全組合せからなる言語は帰納言語ではない。従って、停止問題は計算不能または判定不能と呼ばれる。
停止問題を拡張したライスの定理では、言語が特定の自明な特性を持つかどうかは（一般に）判定不能であるとされる。
帰納言語以上の言語.
しかし、停止しないチューリングマシンの記述を入力として与えられたとき、それを判定するチューリングマシンが永遠に動作することを許容するなら、停止問題は一応解決する。従って、停止問題判定は帰納的可算言語である。しかし、帰納的可算ですらない言語も存在する。
不合理な計算モデル.