2004-gre-cs-practice-book.pdf/Q47

Ссылки сюда (2) →

Вопрос: Q47-4c9f66

Пусть M — одноленточная детерминированная машина Тьюринга с ленточным алфавитом

{blank, 0, 1},

C обозначает (возможно, бесконечное) вычисление M, начинающееся с пустой ленты.

Входными данными для каждой задачи, приведенной ниже, являются M и целое положительное число n

Какая из следующих проблем является разрешимой?

1. Вычисление C длится не менее n шагов
2. Вычисление C длится не менее n шагов, и M выводит 1 в какой-то момент после n-го шага
3. M сканирует не менее n различных квадратов ленты во время вычисления C

Ответы

• Нет правильных ответов
• Только 3
• 1 и 2
• 1 и 3
• Правильный ответ: 1
• 1, 2, 3

Объяснение

Исходники — вопрос 47 на 33 странице книги «2004-gre-cs-practice-book.pdf»

У них «Правильный ответ: 1 и 3» — вот не уверен.

• Ну второе — это «проблема остановки» на пустой ленте, неразрешимо.
• Первое можно продетектить симуляцией.
• Третье — кстати, не уверен, имхо проблему остановки симуляцией можно свести к этой (ну типа если надо вывести «1» — заполнить больше «n» ячеек).

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.