2004-gre-cs-practice-book.pdf/Q47 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q47-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q47-4c9f66 == | == Вопрос: 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 | ||
=== Объяснение === | === Объяснение === | ||
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|33|47}} | |
| − | {{cstest-source|2004-gre-cs-practice-book.pdf| | + | |
| + | У них «Правильный ответ: 1 и 3» — вот не уверен. | ||
| + | |||
| + | * Ну второе — это «проблема остановки» на пустой ленте, неразрешимо. | ||
| + | * Первое можно продетектить симуляцией. | ||
| + | * Третье — кстати, не уверен, имхо проблему остановки симуляцией можно свести к этой (ну типа если надо вывести «1» — заполнить больше «n» ячеек). | ||
| − | + | {{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» ячеек).