Пусть <M> будет кодированием машины Тьюринга в виде строки над ∑ = {0, 1}. Пусть L = {<M> | M — машина Тьюринга, которая принимает строку длины 2014}. Тогда L
(A) разрешимый и рекурсивно перечислимый
(B) неразрешимо, но рекурсивно перечислимо
(C) неразрешимы и не рекурсивно перечислимы
(D) разрешимо, но не рекурсивно перечислимо
Ответ: (Б)
Объяснение: Есть конечное количество строк длины '2014'. Таким образом, машина Тьюринга примет входную строку длины «2014» и проверит ее.
Если входная строка присутствует в языке, то машина Тьюринга остановится в конечном состоянии.
Но если машина Тьюринга не может принять входную строку, она остановится в неконечном состоянии или перейдет в бесконечный цикл и никогда не остановится.
Таким образом, L неразрешимо и рекурсивно перечислимо.
Рекомендуемые посты:
- ВОРОТА | 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