Рубрики

ВОРОТА | GATE-CS-2001 | Вопрос 32

Рассмотрим следующую проблему X.

Given a Turing machine M over the input alphabet Σ, any
state q of M And a word w∈Σ*, does the computation of M
on w visit the state q? 

Какое из следующих утверждений о X является правильным?
(A) X разрешима
(B) X неразрешима, но частично разрешима
(C) X неразрешима и даже частично не разрешима
(D) X не является проблемой решения

Ответ: (Б)
Объяснение:
Эта проблема является государственной проблемой въезда. Проблема вхождения в состояние может быть сведена к проблеме остановки.

Построим машину Тьюринга M с конечным состоянием «q». Запускаем машину Тьюринга R (для задачи о входе в состояние)
с входами: M, q, w.

Мы даем 'W' в качестве ввода для М.

Если M останавливается в конечном состоянии 'q', то R принимает ввод. Итак, данная проблема частично разрешима.

Если M идет в бесконечном цикле, то M не может ничего вывести. Таким образом, R отклоняет ввод. Итак, данная проблема становится неразрешимой.

Таким образом, вариант (B) является ответом.

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2001 | Вопрос 32

0.00 (0%) 0 votes