チューリングマシンの停止問題

Input −チューリングマシンと入力文字列 w。

Problem −チューリングマシンは文字列の計算を終了しますか w有限のステップ数で？答えは「はい」または「いいえ」のいずれかでなければなりません。

Proof−最初に、この問題を解決するためにそのようなチューリングマシンが存在すると仮定し、次にそれ自体が矛盾していることを示します。このチューリングマシンをHalting machineこれは、有限の時間内に「はい」または「いいえ」を生成します。停止中のマシンが有限時間で終了する場合、出力は「yes」として表示され、それ以外の場合は「no」として出力されます。以下は、停止マシンのブロック図です。

今、私たちは設計します inverted halting machine (HM)’ として-

• 場合 H YESを返し、その後永久ループします。

• 場合 H NOを返し、停止します。

以下は、「倒立停止機」のブロック図です。

さらに、機械 (HM)₂ どの入力自体は次のように構成されます-

• （HM）₂が入力で停止した場合、永久ループします。
• それ以外の場合は、停止します。

ここで、矛盾があります。したがって、停止性問題はundecidable。