从R映射减少

Question

let $ l_1 $ 在 $ r $ 中是某种语言。让 $ l_2 $ 是 $重新$ 中的某种语言。这一切都是如此 $ l_1 \ leq_m l_2 $ ？ 我知道，对于非琐事 $ l_1 $ ， $ l_1 $ $ r $ 是说 $ l_1 \ leq_m l_2 $ 。 但我不能证明第一个案例。

和另一个问题： 我几乎确定以下是真的，尽管我没有在互联网上找到它的任何引用： 身份函数是 $ \ imptyset $ 到 $ \ imptyset $ 。

Answer 1

如果 $ l_2 \ neq \ sigma ^ * $ 和 $ l_2 \ neq \ imptyset $ 然后 $ l_1 \在r $ 和 $ l_2 \中，在Re $ 中暗示 $ l_1 \ le_m l_2 $ 。

let $ t $ 是一个图灵的机器，决定 $ l_1 $ 。让 $ a，b \ in \ sigma ^ * $ 这样 $ a \ in l_2 $ 和< SPAN Class=“Math-Container”> $ B \ Not \ IN L_2 $ 。 对于 $ x \ in \ sigma ^ * $ ，define $ \ phi（x）= \ begin {案例} a＆\ text {如果$ t（x）$接受} \\ B＆\ Text {如果$ t（x）$ expects} \结束{案例} $ 。 很容易检查 $ \ phi $ 是从 $ l_1 $ 到 $ l_2 $ 。

如果 $ l_2=sigma ^ * $ 那么 $ l_1 \ in r $ 和 $ l_2 \在重新$ 中并不意味着 $ l_1 \ le_m l_2 $ 。 < / p>

这可以看出，例如，通过选择 $ l_1=imptyset $

如果 $ l_2=imptyset $ 那么 $ l_1 \在r $ 和<跨越类=“数学容器”> $ l_2 \在Re $ 中不暗示 $ l_1 \ le_m l_2 $ 。

可以看出，例如，通过选择 $ l_1=sigma ^ * $ 。