Это снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений.
Обобщение детерминированной машины Тьюринга, в которой, при каждом переходе,
можно выполнять переход одновременно в несколько (константа) состояний — можно считать, что происходит «клонирование» машины (состояние, содержимое лент, положение головок).
Таким образом, для каждого массива входных данных имеется не один, а несколько (в общем случае — экспоненциальное число) путей, по которым может развиваться вычисление.
Недетерминированная машина Тьюринга выдаст ответ 1, если существует хотя бы один путь
развития вычисления, на котором выдается ответ 1, и 0 — в противном
случае (таким образом, ответы «ДА» и «НЕТ» в случае недетерминированных вычислений несимметричны).
Внимание! Эта статья была создана путем автоматического реплицирования из внутренней базы знаний компании Заказные Информ Системы. Любые правки этой статьи могут быть перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
