mappage des réductions de r to re

Question

let $ l_1 $ soit une langue dans $ r $ .Laissez $ l_2 $ être une langue dans $ re $ .Est-ce nécessairement que $ l_1 \ leq_m l_2 $ ? Je sais que pour non trivial $ l_1 $ , $ l_1 $ in $ R $ il est juste de dire que $ l_1 \ leq_m l_2 $ . Mais je ne peux pas prouver le premier cas.

et une autre question: Je suis presque certain que ce qui suit est vrai, même si je n'ai trouvé aucune référence à Internet: La fonction d'identité est une réduction de mappage de $ \ videtyset $ to $ \ videtyset $

.

.

Answer 1

si $ l_2 \ neq \ sigma ^ * $ et $ l_2 \ neq \ videtyset $ alors $ l_1 \ in r $ et $ l_2 \ in re $ implique $ l_1 \ le_m l_2 $ .

let $ t $ être une machine de Turing qui décide $ l_1 $ . Laissez $ a, b \ in \ sigma ^ * $ telle que $ a \ in l_2 $ et < SPAN CLASSE="MATH-CONTENEUR"> $ B \ NOT \ IN L_2 $ . Pour $ x \ in \ sigma ^ * $ , définissez $ \ phi (x)= \ commencer {cas} a & \ texte {si $ t $ t (x) $ accepte} \\ B & \ Text {si $ t $ t (x) $ rejetts} \ fin {cas} $ . Il est facile de vérifier que $ \ phi $ est une réduction de mappage de $ l_1 $ to $ l_2 $ .

si $ l_2=sigma ^ * $ alors $ l_1 \ in r $ et $ l_2 \ in re $ n'implique pas $ l_1 \ le_m l_2 $ . < / p>

Ceci peut être vu, par exemple, en choisissant $ l_1=videtyset $ .

.

si $ l_2=videtyset $ alors $ l_1 \ in r $ et < span class="math-conteneur"> $ l_2 \ in re $ n'implique pas $ l_1 \ le_m l_2 $ .

Ceci peut être vu, par exemple, en choisissant $ l_1=sigma ^ * $ .

.