Mapeo de reducciones de R a re

Question

Let $ l_1 $ Sé algún idioma en $ R $ .Deje que $ l_2 $ sea algún idioma en $ re $ .Es necesariamente que $ l_1 \ leq_m l_2 $ ? Sé que para el contenedor matemático "no trivial $ l_1 $ , $ l_1 $ en $ R $ Es correcto decir que $ l_1 \ leq_m l_2 $ . Pero no puedo probar el primer caso.

y otra pregunta: Estoy casi seguro de que lo siguiente es cierto, aunque no he encontrado ninguna referencia a ella en Internet: La función de identidad es una reducción de mapeo de $ \ vacioset $ a $ \ vacioset $ .

Answer 1

si $ l_2 \ neq \ sigma ^ * $ y $ l_2 \ neq \ vacioset $ Luego $ l_1 \ en r $ y $ l_2 \ en re $ implica $ l_1 \ le_m l_2 $ .

Permitir $ t $ ser una máquina de Turing que decida $ l_1 $ . Deje que $ A, B \ in \ SIGMA ^ * $ de modo que $ A \ in l_2 $ y < Span Class="Math-contenedor"> $ b \ no \ in l_2 $ . Para $ x \ in \ sigma ^ * $ , define $ \ phi (x)= \ comienzan {casos} A & \ Text {si $ t (x) $ acepts} \\ b & \ texto {si $ t (x) $ rechazos} \ End {casos} $ . Es fácil verificar que $ \ phi $ es una reducción de mapeo de $ l_1 $ a $ l_2 $ .

si $ l_2=sigma ^ * $ luego $ l_1 \ en R $ y $ l_2 \ in re $ no implica $ l_1 \ le_m l_2 $ . < / p>

Esto se puede ver, por ejemplo, al elegir $ l_1=vacioset $ .

si $ l_2=vacioset $ luego $ l_1 \ en r $ y < Span Class="Math-contenedor"> $ l_2 \ in re $ no implica $ l_1 \ le_m l_2 $ .

Esto se puede ver, por ejemplo, al elegir $ l_1=sigma ^ * $ .