2011-gre-cs-practice-book.pdf/Q18

Задача зарезервирована: Urmat A 14:56, 19 декабря 2024 (UTC)

Вопрос: Q18-08c765

Предположим, что профессор X разрабатывает новую модель вычислений, называемую нейтронной машиной. Что из следующего будет следствием тезиса Чёрча-Тьюринга?

Ответы

1. Ни одна нейтронная машина не может решить задачу коммивояжёра за полиномиальное время.
2. Ни одна нейтронная машина не может решить задачу максимального соответствия для двудольных графов за полиномиальное время.
3. Ни одна нейтронная машина не может определить, содержит ли десятичное разложение 7 последовательных семерок.
4. Ни одна нейтронная машина не может смоделировать данную машину Тьюринга за полиномиальное время.
5. Правильный ответ: Ни одна нейтронная машина не может определить за полиномиальное время, останавливается ли данная машина Тьюринга, если ее входная лента изначально пуста.

Объяснение

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

• Первое утверждение не относится к тезису Чёрча-Тьюринга. Мы вообще ещё не знаем можно ли решить эту задачу за полиномиальное время или нет
• Эта задача может быть решена за полиномиальное время с помощью алгоритмов, таких как алгоритм Хопкрофта-Карп. Поэтому это утверждение неверно.
• Это задача, которую можно решить за полиномиальное время, и не требует сложных вычислений. Поэтому это утверждение неверно.
• Это утверждение неверно, так как машины Тьюринга могут имитировать друг друга, но это может занять больше времени, чем полиномиальное, в зависимости от конкретной реализации.
• Это утверждение связано с проблемой остановки, которая является неразрешимой. Таким образом, это утверждение является следствием тезиса Чёрча-Тьюринга.

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

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

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