turing-machines - この言語が決定不可能であることを証明する

Question

次の言語Lは決定不能ですか？

L = { M | Mはチューリングマシンの記述であり、 Mが最大kステップ後に停止するような長さkの入力xが存在します}

そうだと思いますが、証明できませんでした。停止性問題からの削減を考えてみました。

Answer 1

レビュー：停止問題のインスタンスは、旋盤Nが入力yで停止するかどうかを尋ねます。この問題は決定不能であることが知られています（ただし、半決定可能です）。

あなたの言語Lは確かに決定不可能です。これは、停止性問題をLに減らすことで示されます。

1. 停止性問題のインスタンス（N、y ）に対して、L問題の新しいマシンMを作成します。
2. 入力xで、Mはlength（x）ステップの（ N、y ）をシミュレートします。
3. シミュレーションがそのステップ数内で停止した場合、Mは停止します。それ以外の場合、Mは意図的に無限ループに入ります。

この削減は、次の理由で有効です。

• （N、y）が最終的にkステップで停止する場合、 Mは長さk以上のすべての入力で停止するため、 MはLになります。
• それ以外の場合、（N、y）は停止せず、Mは入力文字列の長さに関係なく停止しないため、MはLに含まれません。

最後に、停止問題は決定不可能であるため、Lは決定不可能です。