Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 54

Рассмотрим следующие языки.

L1 = { <M>  | M takes at least 2016 steps on some input},
L2 = { <M>  | M takes at least 2016 steps on all inputs} and
L3 = { <M>  | M accepts ε},

где для каждой машины Тьюринга M <M> обозначает конкретное кодирование M.

Что из следующего является ИСТИННЫМ?
(A) L1 является рекурсивным и L2, L3 не являются рекурсивными
(B) L2 является рекурсивным и L1, L3 не являются рекурсивными
(C) L1, L2 рекурсивны, а L3 не рекурсивны
(D) L1, L2, L3 являются рекурсивными

Ответ: (с)
Пояснение: L1 и L2 оба являются рекурсивными.
L1 = {<M> | M предпринимает не менее 2016 шагов по некоторому вводу}
В L1 мы можем прекратить вводить данные, если найдем любую строку, которая принимается менее чем за 2016 шагов. В L2 мы
необходимо проверить все возможные входные данные, длина которых меньше 2016 года, и все возможные строки, длина которых меньше
чем 2016 год является конечным набором. Как для L1, так и для L2 машина определенно остановится. И L1, и L2 являются рекурсивными.
L3 неразрешима, M принимает ε. Таким образом, L3 не является рекурсивным.
Вариант (C) является ПРАВИЛЬНЫМ.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 54

0.00 (0%) 0 votes