mappage des réductions de r to re
-
29-09-2020 - |
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 $
. .La solution
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
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 ^ * $ .
.