riduzioni di mappatura da r a re

Question

Let $ l_1 $ Sii un po 'di lingua in $ r $ .Let $ l_2 $ Sii un po 'di lingua in $ re $ .È necessariamente quello $ l_1 \ leq_m l_2 $ ? Lo so per non banale $ l_1 $ , $ l_1 $ in $ R $ È giusto dire che $ l_1 \ leq_m l_2 $ . Ma non posso provare il primo caso.

E un'altra domanda: Sono quasi certo che il seguente è vero, anche se non ho trovato alcun riferimento a questo su Internet: La funzione di identità è una riduzione della mappatura da $ \ vuotyset $ a $ \ vuotyset $ .

Answer 1

se $ l_2 \ neq \ sigma ^ * $ e $ l_2 \ neq \ vuoto $ quindi $ l_1 \ in r $ e $ l_2 \ in re $ implica $ l_1 \ le_m l_2 $ .

Let $ T $ Sii una macchina Turing che decide $ l_1 $ . Let $ A, B \ in \ Sigma ^ * $ In tal modo $ a \ in l_2 $ e < Span Class="Math-Container"> $ B \ non \ in l_2 $ . Per $ x \ in \ Sigma ^ * $ , definisci $ \ phi (x)= \ Begin {casi} A & \ Text {se $ t (x) $ accetta} \\ B & \ Text {IF $ T (X) $ respinge} \ end {casi} $ . È facile controllare che $ \ phi $ è una riduzione della mappatura da $ l_1 $ a $ l_2 $ .

se $ l_2=sigma ^ * $ quindi $ l_1 \ in r $ e $ l_2 \ in re $ non implica $ l_1 \ le_m l_2 $ . < / P >.

Questo può essere visto, ad esempio, scegliendo $ l_1=vuoto $ .

Se $ l_2=vuoto $ quindi $ l_1 \ in r $ e < Class class="container di matematica"> $ l_2 \ in re $ non implica $ l_1 \ le_m l_2 $ . Questo può essere visto, ad esempio, scegliendo $ l_1=sigma ^ * $ .