riduzioni di mappatura da r a re
-
29-09-2020 - |
Domanda
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 $ .
Soluzione
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
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 ^ * $ .