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

Вопрос: Q18-08c765

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

Ответы

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

Объяснение

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

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

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

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

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