computer-science - チューリングマシン停止問題

Question

マシンのチューリングと停止問題について質問があります。

Atm = {(M,w) ここで、M はチューリング マシンで、w は入力} であり、
HALTtm = {(M,w) ここで、M はチューリング マシンであり、入力 w で停止するとします。

HALTtm <=m Atm であることを証明したい

いくつかの方法を試しましたが、解決には程遠いと思います。誰でもいくつかの手がかりを与えることができますか??

Answer 1

さて、HALTtm にあるすべての (M,w) について、(M,w) が Atm にあることに注意してください。次に、Atm のメンバーであるが停止しない (M',w') が存在し、HALTtm にないことを示します。

Answer 2

次の各言語について、その言語を受け入れるチューリングマシンの遷移図を作成します。

1. {aibj | i≠j}

Answer 3

<=m とは? 「多一還元」という意味だと思いますか？その場合、あなたが求めているのは、すべての文字列 x に対して、合計計算可能な関数 f です。

x が HALTtm に属するのは、f(x) が Atm に属する場合のみです。

そのような f が存在する場合、停止問題を決定できます。x が与えられた場合、f(x) を計算し、f(x) が Atm に属しているかどうかを確認します (Atm は簡単に再帰的/決定可能です)。しかし、停止問題は決定可能ではないため、そのような f は存在しません。したがって、HALTtmは Atm に還元されません。