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

Материал из DISCOPAL
Перейти к: навигация, поиск

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

Вопрос: Q18-08c765

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

Ответы

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


Объяснение

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

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

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

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

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

Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q18&oldid=34182»