什么是未定的语言$ B $正在降低其补充?
-
29-09-2020 - |
题
我遇到了一个问题,要求给出一个未定名语言 $ 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}} $ 是循环)...任何帮助?
解决方案
让 $ 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} $ 。
不隶属于 cs.stackexchange