|
|
| Строка 1: |
Строка 1: |
| − | Обобщение [[машина Тьюринга|детерминированной машины Тьюринга]], в которой, при каждом переходе,
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | можно выполнять переход одновременно в несколько (константа) состояний — можно считать, что происходит «клонирование» машины (состояние, содержимое лент, положение головок).
| + | |
| − | | + | |
| − | Таким образом, для каждого массива входных данных имеется не один, а несколько (в общем случае — экспоненциальное число) путей, по которым может развиваться вычисление.
| + | |
| − | | + | |
| − | Недетерминированная машина Тьюринга выдаст ответ '''1''', если ''существует хотя бы один'' путь
| + | |
| − | развития вычисления, на котором выдается ответ '''1''', и '''0''' — в противном
| + | |
| − | случае (таким образом, ответы «ДА» и «НЕТ» в случае недетерминированных вычислений несимметричны).
| + | |
| − | | + | |
| − | [[Category:Теория сложности]]
| + | |
| − | {{replicate-from-custiswiki-to-lib}} | + | |
