语言的半解密性$ \ overline {l _ {\ epsilon}} $

Question

首先考虑问题：给定 $ l_h={r（m）w：m \在tm_0中，w \ in l（m）\} $ $ r（m）$ 是 $ m \中的编码转换，在tm_0 $ 中。假设为矛盾 $ \ overline {l_ {h}} $ 是半解解码的，然后在tm_0中存在 $ q \ $ 带 $ l（q）=overline {l x {h}} $ 因此每个 $ m \在tm_0 $ 中我们有以下几个 $$ q \接受\输入\ r（m）w \ iff m \ do \ not \ accept \输入\ w \ \ \ \（1）$$ 然后我们构建机器 $ z $ s.t.输入和运行机器 $ q $ 。观察以下是任意 $ m \中的tm_0 $ ： \ begin {alignat *} {2} z \接受\输入\ r（m）＆\ iff q \接受\输入\ r（m）r（m）\\ ＆\ iff m \ do \ not \接受\输入\ r（m） \结束{alignat *} 拍摄 $ m= z $ 将使我们成为一个矛盾。因此， $ \ overline {l_ {h}} $ 不是半解解码的。

我正在尝试申请案例 $ l _ {\ epsilon}={r（m）：m \ tm ant tmpt {s.t。 $ m $接受$ \ epsilon $} \} $ 其中 $ r（m）$ 是 $ m \在tm_0 $ 中。但我面临着一些麻烦。假设 $ \ overline {l _ {\ epsilon}} $ 是半解辨别的，然后有 $ q \ TM_0 $ 使用 $ l（q）=overline {l _ {\ epsilon}} $ 因此每个 $ m \ in tm_0 $ 我们有以下几个 $$ q \接受\输入\ r（m）\ iff m \ do \ not \ accept \ finn \ \ epsilon $$ 然后我真的无法找到适当的 $ z $ 在这种情况下，输入输入只需工作。任何建议都得到了赞赏。

Answer 1

假设为矛盾 $ \ overline {l _ {\ epsilon}} $ 是半解解码的。它很容易证明 $ l _ {\ epsilon} $ 通过减少到停止问题来半解解析，即 $ l_ {H} $ 是半解脱的。如果 $ l _ {\ epsilon} $ 和 $ \ overline {l _ {\ epsilon}} $ 是半-Decidable，因此 $ l _ {\ epsilon} $ 是可解除的。这是一个矛盾，如 $ l _ {\ epsilon} $ 以及 $ l_ {h} $ 是半删除的。

在此处证明使用以下索赔：

$ \ textbf {索赔：} \ text {如果$ l $和$ \ overline {l} $ semi-decisable，那么$ l $是deminable} $