Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 54

Определите языки L0 и L1 следующим образом:

L0 = {< M, w, 0 > | M halts on w}
L1 = {< M, w, 1 > | M does not halts on w} 

Вот триплет, первый компонент которого. M — кодирование машины Тьюринга, второй компонент, w, является строкой, а третий компонент, i, является битом. Пусть L = L0 ∪ L1. Какие из следующих утверждений верно ?
(A) L рекурсивно перечислимо, но L 'не является
(B) L 'рекурсивно перечислимо, но L не
(C) L и L 'являются рекурсивными
(D) Ни L, ни L 'не являются рекурсивно перечислимыми

Ответ: (D)
Пояснение: Поскольку проблема остановки машин Тьюринга неразрешима. Таким образом, L = L0 ∪ L1 неразрешима, даже не полурежима. Это не является рекурсивным перечислимым, поэтому его дополнение (L ') также не является рекурсивным перечислимым.

Вариант (D) правильный.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2003 | Вопрос 54

0.00 (0%) 0 votes