什么是未定的语言$ B $正在降低其补充？

Question

我遇到了一个问题，要求给出一个未定名语言 $ b $ 这样的 $ b \ leq_m\ overline {b} $ ...

但是，我可以难以构建一个例子......我的困难是给出了一个不可确定但是图灵识别的语言，说 $ a_ {tm} $ ，其补充 $ \ overline {a_ {tm}} $ 不是图灵识别和循环。如果我减少这样的语言（例如 $ x \中的\ {tm} \ leq_m y \ in \ ovline {a_ {tm}} $ ，实例 $ y \ in \ ovline {a_ {tm}} $ 无法由任何tm识别（因为按定义， $ \ overline {a_{TM}} $ 是循环）...

任何帮助？

Answer 1

让 $ h $ 是所有图灵机的语言，可在空输入上停止。 显然 $ h $ 不可确定。

让 $ l={（1，t）：t \ in h \} \ cup \ {（0，t）：t \ not \ in h \} $ 。

清楚 $ l $ 是不可行的。如果 $ l $ 是可解除的，那么一个图灵机 $ m $ for $ l $ 也意味着存在图灵机 $ m'$ ，其决定 $ H $ 。 $ m'$ 使用输入 $ t $ 只是模拟 $ M $ 带输入 $（1，t）$ 。

而且，对于图灵机 $ t $ 和 $ x \ in \ {0,1 \} $ < / span>我们有： $$ （x，t）\ \ in l \ iff（1-x，t）\ not \ in l \ iff（1-x，t）\ in \ ovline {l}。 $$

这一点，结合我们可以决定给定的单词是否对有效的图灵机进行编码，显示 $ l $ 是可将 $ \ overline {l} $ 。