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