$ a_ {tm} $に関するこのチューリングマシンの問題を理解するのを手伝ってください

Question

私は物理学/ Cです。学生で、今数日間この特定の問題に苦労しています。 そのため、タスクは次のとおりです。

---

次の言語を考慮してください。

$ \ hspace {20pt} L_1={\ langle m \ rangle \、| \、l（m）= a_ {tm} \ \ \ \\ \ hspace {20pt} L_2={\ langle m \ rangle \、| \、l（m）=overline {a_ {tm}} \} $

これらは決められますか？あなたの決定を証明してください。

$ a_ {tm} $ は $ \ {\ langle m、w \ rangle \、|として定義されています。 \、\ text {mはTM、Mはw} \} \}} \}}} $}} $}

---

まず第一言語 $ L_1 $ を理解しようとしています。 $ L_1 $ の場合はどういう意味ですか？なぜ $ a_ {tm} $ が決まりませんが、 $ L_1 $ 実際には？

私はすでに2番目の問題に対する解決策を知っているような気がしますが、私の腸の本能が正しいかどうかを知りたいのですが。そのため、 $ \ overline {a_ {tm}} $ } $ ではありません。 $ m $ $ l（m）=overline {a_ {tm}} $ は存在しません/空です。したがって、 $ L_2=afthyset $ 、それは簡単に決定できます。

Answer 1

言語の解決 $ L_1 $ は、 $ a_ {tm} $を半決定した場合、すべてのTMを知ることを意味します。問題

あなたの本能は正しいです - それは空であり、それゆえ決定可能です。 それはあらゆる機会で空ではなかった、そしてそれは決められなかったであろう