Рубрики

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 26

Пусть A ≤ m B обозначает, что язык A отображаемо приводим (также известен как сводимый много к одному) к языку B. Что из следующего является ЛОЖНЫМ?

а) Если A ≤ m B и B рекурсивен, то A рекурсивен.
б) Если A ≤ m B и A неразрешима, то B неразрешима.
c) Если A ≤ m B и B рекурсивно перечислимо, то A рекурсивно перечислимо.
d) Если A ≤ m B и B не является рекурсивно перечислимым, то A не является рекурсивно перечислимым.
(А)
(Б) б
(С) с
(D) d

Ответ: (D)
Объяснение:

  • A ≤ m B означает, что язык A сопоставим для языка B. Таким образом, A не может быть сложнее, чем B.
    Поскольку A можно уменьшить до B, вместо решения A мы можем теперь решить B.
    Итак, первые три варианта верны.
  • Поскольку B не является рекурсивно перечислимым, это не гарантирует, что A не является рекурсивно перечислимым. Таким образом, если A ≤ m B и B не является рекурсивно перечислимым, то A не является рекурсивно перечислимым. Таким образом, ответ D является правильным

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 26

0.00 (0%) 0 votes