https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%9D%D0%B5%D0%B4%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 2026-05-06T09:31:00Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%9D%D0%B5%D0%B4%D0%B5%D1%82%D0%B5%D1%80%D0%BC%D0%B8%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0&diff=1153&oldid=prev 2008-08-04T09:55:52Z

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

WikiSysop