Automata-theory-turing-machine-halting-problem

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

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

問題-チューリングマシンは、有限数のステップで文字列 w の計算を終了しますか？ 答えはyesまたはnoでなければなりません。

証明-最初に、この問題を解決するためにそのようなチューリングマシンが存在すると仮定し、それが矛盾していることを示します。 このチューリングマシンを、限られた時間で「はい」または「いいえ」を生成する*ハルティングマシン*と呼びます。 停止しているマシンが限られた時間内に終了する場合、出力は「yes」になり、そうでない場合は「no」になります。 以下は、ホールティングマシンのブロック図です-

Halting Machine

今、我々は* inverted halting machine（HM） ’*を次のように設計します-

• H がYESを返す場合、永久にループします。
• H がNOを返した場合、停止します。

以下は、「倒立停止マシン」のブロック図です-

反転停止マシン

さらに、それ自身を入力するマシン*（HM）〜2〜*は次のように構築されます-

• 入力で（HM）〜2〜が停止した場合、永久にループします。
• そうでなければ、停止します。

ここで、矛盾があります。 したがって、停止の問題は*決定不能*です。