帮助我了解这个关于$ a_ {tm} $的图灵机问题

Question

我是一个物理/ c.s。学生现在一直在努力与这个特殊问题挣扎。 所以任务如下：

---

考虑以下语言：

$ \ 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} $ 不是可解除的，但是一个tm会决定 $ l_1 $ 实际上是呢？

我觉得我已经知道了第二个问题的解决方案，但想知道我的胆量是否正确。因此，由于<跨越类=“math-container”> $ \ overline {a_ {tm}} $ 不是图灵识别它意味着 $ m $ 使用 $ l（m）=overline {a_ {tm}} $ 不存在/是空的。因此 $ l_2=imptyset $ ，这很容易解密。

Answer 1

求解语言 $ l_1 $ 如果它是半决定 $ a_ {tm} $问题。

你的本能是对 - 它是空的，因此可判定。如果它不是通过任何机会空的，那么通过米饭的定理，它将尚未判定