ВОРОТА | ВОРОТА КС 2021 | Набор 1 | Вопрос 49

Для машины Тьюринга M ⟨M⟩ обозначает кодировку M. Рассмотрим следующие два языка.

• L1 = { ⟨M⟩ ∣ M делает более 2021 шага на всех входных данных }
• L2 = { ⟨M⟩ ∣ M делает более 2021 шага на некоторых входных данных }
Какой из следующих вариантов правильный?
(A) И L1, и L2 разрешимы
(B) L1 разрешима, а L2 неразрешима
(C) L1 неразрешима, а L2 разрешима
(D) И L1, и L2 неразрешимы

Ответ: (А)
Объяснение:
• Для L1: проверьте, останавливается ли машина Тьюринга M в пределах 2021 шага для всех входных данных длины, меньшей или равной 2021, если она не останавливается в пределах 2021 шага, определенно она выполняет более 2021 шага, поэтому это разрешимо.
• Для L2: аналогичным образом мы можем проверить, останавливается ли машина Тьюринга M в пределах 2021 шага для некоторых входных данных длины, меньшей или равной 2021. Если она не останавливается в течение 2021 шага для некоторых входных данных, она выполняет более 2021 шага, поэтому она также разрешима.

Викторина этого вопроса