Пусть 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 является правильным
Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.
Тест на этот вопрос
Рекомендуемые посты:
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
- ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65
0.00 (0%) 0 votes