この言語は決められますか？

Question

タイトルが言うように

。 この言語は決められ、どのように証明しますか？

$$ l={\ langle m \ rangle \ mid m \ text {はチューリングマシンであり、入力があり、} m \ text {halts} \}$$

Answer 1

あなたの言語は決まっていません。 $ l $ のチューリングマシンの存在が存在することに気付くのに十分であることを示すために停止問題を解決するチューリング機の存在を意味します。

実際には、 $ m $ を指定して、入力 $ x $ を設定することができます。 Machine $ m '$ は、その入力を無視し、 $ x $ をテープに書き込み、シミュレーション< SPAN CLASS="math-container"> $ m $ 。明らかに $ m '$ $ m $ の停止時の場合に限られている場合（その入力に関係なく） $ x $ 。 $ m '$ m' \ in l $ で \ m '\ \ m' \ \ m '\ m' \ \ m '\ m' \ m '} class="math-container"> $ t $ 入力 $ m '$ 。