reduções de mapeamento de r para re

Question

Deixe $ l_1 $ ser algum idioma na $ R $ .Deixe $ l_2 $ ser algum idioma em $ re $ .É necessariamente que $ l_1 \ leq_m l_2 $ ? Eu sei que para não trivial $ l_1 $ , $ l_1 $ no recipiente de matemática $ R $ É certo dizer que $ l_1 \ leq_m l_2 $ . Mas eu não posso provar o primeiro caso.

e outra pergunta: Estou quase certo de que o seguinte é verdadeiro, embora eu não tenha encontrado nenhuma referência para ela na Internet: A função de identidade é uma redução de mapeamento da $ \ vazio $ para $ \ vazio $ .

Answer 1

se $ l_2 \ neq \ sigma ^ * $ e $ l_2 \ neq \ forkset $ então $ l_1 \ em R $ e $ l_2 \ in R $ implica $ l_1 \ le_m l_2 $ .

Deixe $ t $ ser uma máquina de Turing que decide $ l_1 $ . Deixe $ a, b \ in \ sigma ^ * $ tal que $ a \ in l_2 $ e < span class="contêiner matemático"> $ b \ não \ in l_2 $ . Para $ x \ in \ sigma ^ * $ , definir $ \ phi (x)= \ begin {casos} A & \ TEXT {se $ t (x) $ aceita} \\ B & \ Text {se $ t (x) $ rejeitar} \ end {casos} $ . É fácil verificar que $ \ phi $ é uma redução de mapeamento de $ l_1 $ para $ l_2 $ .

se $ l_2=sigma ^ * $ então $ l_1 \ em R $ e $ l_2 \ in R $ não implica $ l_1 \ le_m l_2 $ . < / p >.

Isso pode ser visto, por exemplo, escolhendo $ l_1=Fortyset $ .

se $ l_2=FORTSET $ então $ l_1 \ em R $ e < span class="contentor de matemática"> $ l_2 \ in R $ não implica $ l_1 \ le_m l_2 $ .

Isso pode ser visto, por exemplo, escolhendo $ l_1=sigma ^ * $ .