2004-gre-cs-practice-book.pdf/Q47 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
* Третье — кстати, не уверен, имхо проблему остановки симуляцией можно свести к этой (ну типа если надо вывести «1» — заполнить больше «n» ячеек). | * Третье — кстати, не уверен, имхо проблему остановки симуляцией можно свести к этой (ну типа если надо вывести «1» — заполнить больше «n» ячеек). | ||
| − | {{question-ok|}} | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 15:32, 15 декабря 2024 (UTC)}} |
[[Категория:Теория сложности]] | [[Категория:Теория сложности]] | ||
[[Категория:Разобраться]] | [[Категория:Разобраться]] | ||
Текущая версия на 15:32, 15 декабря 2024
Вопрос: Q47-4c9f66
Пусть M — одноленточная детерминированная машина Тьюринга с ленточным алфавитом
{blank, 0, 1},
C обозначает (возможно, бесконечное) вычисление M, начинающееся с пустой ленты.
Входными данными для каждой задачи, приведенной ниже, являются M и целое положительное число n
Какая из следующих проблем является разрешимой?
- Вычисление C длится не менее n шагов
- Вычисление C длится не менее n шагов, и M выводит 1 в какой-то момент после n-го шага
- M сканирует не менее n различных квадратов ленты во время вычисления C
Ответы
- Нет правильных ответов
- Только 3
- 1 и 2
- 1 и 3
- Правильный ответ: 1
- 1, 2, 3
Объяснение
Исходники — вопрос 47 на 33 странице книги «2004-gre-cs-practice-book.pdf»
У них «Правильный ответ: 1 и 3» — вот не уверен.
- Ну второе — это «проблема остановки» на пустой ленте, неразрешимо.
- Первое можно продетектить симуляцией.
- Третье — кстати, не уверен, имхо проблему остановки симуляцией можно свести к этой (ну типа если надо вывести «1» — заполнить больше «n» ячеек).