PUERTA | GATE-CS-2014-(Conjunto-2) | Pregunta 26

Sea A ≤ _m B denota que el lenguaje A está mapeando reducible (también conocido como reducible de muchos a uno) al lenguaje B. ¿Cuál de los siguientes es FALSO?
(A) Si A ≤ _m B y B es recursivo, entonces A es recursivo.
(B) Si A ≤ _m B y A es indecidible, entonces B es indecidible.
(C) Si A ≤ _m B y B es recursivamente enumerable, entonces A es recursivamente enumerable.
(D) Si A ≤ _m B y B no es recursivamente enumerable, entonces A no es recursivamente enumerable.

Respuesta: (D)
Explicación:

• A ≤ _m B significa que el idioma A se está mapeando reducible al idioma B. Por lo tanto, A no puede ser más difícil que B.
  Dado que A puede reducirse a B, en lugar de decidir A, ahora podemos decidir B.
  Entonces, las primeras tres opciones son correctas .
• Como B no es enumerable recursivamente, no garantiza que A no sea enumerable recursivamente. Por lo tanto, si A ≤ _m B y B no es enumerable recursivamente, entonces A no es enumerable recursivamente.  Por lo tanto, la respuesta es D es correcta

Comente a continuación si encuentra algo incorrecto en la publicación anterior.

Cuestionario de esta pregunta