Рубрики

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

Пусть <M> будет кодированием машины Тьюринга в виде строки над ∑ = {0, 1}. Пусть L = {<M> | M — машина Тьюринга, которая принимает строку длины 2014}. Тогда L
(A) разрешимый и рекурсивно перечислимый
(B) неразрешимо, но рекурсивно перечислимо
(C) неразрешимы и не рекурсивно перечислимы
(D) разрешимо, но не рекурсивно перечислимо

Ответ: (Б)
Объяснение: Есть конечное количество строк длины '2014'. Таким образом, машина Тьюринга примет входную строку длины «2014» и проверит ее.

Если входная строка присутствует в языке, то машина Тьюринга остановится в конечном состоянии.

Но если машина Тьюринга не может принять входную строку, она остановится в неконечном состоянии или перейдет в бесконечный цикл и никогда не остановится.
Таким образом, L неразрешимо и рекурсивно перечислимо.

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

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

0.00 (0%) 0 votes