Недетерминированные вычисления

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Определение:

Недетерминированная машина Тьюринга (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой недетерминированный конечный автомат, то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.

Такая машина допускает слово, если существует последовательность переходов, переводящая машину в допускающее состояние. В связи с этим есть несколько вариантов представления работы НМТ:

1. Можно считать, что машина «очень удачлива», то есть если есть способ попасть в допускающее состояние, то машина всегда делает верный выбор пути.
2. Если есть несколько вариантов пути, то машина делится на копии, каждая из которых следует по одному из возможных переходов. Слово считается допущенным, если его допускает хотя бы одна из копий.

Для записи недетерминированных программ используется специальный оператор.

Определение:

Оператор [math]\leftarrow?[/math] — недетерминированный выбор (недетерминированное присваивание). Запись [math]x\leftarrow?A[/math] означает, что переменной [math]x[/math] недетерминированно присваивается некоторое значение из множества [math]A[/math].

Не следует связывать недетерминированный выбор с вероятностями. Программа как бы присваивает переменной все возможные значения одновременно.

Определение:

Недетерминированная программа — программа, в которой допускается использование недетерминированного выбора.

Определение:

Язык недетерминированной программы — множество слов, для которых существует такая последовательность недетерминированных выборов, что программа допустит это слово.

Классы NTIME и NSPACE

Определение:

[math]\mathrm{NTIME}(f(n))[/math] — множество языков, для которых существует недетерминированная распознающая программа, время работы которой на входе длины [math]n[/math] есть [math]O(f(n))[/math]. [math]\mathrm{NSPACE}(f(n))[/math] — множество языков, для которых существует такая недетерминированная распознающая программа, что на любом входе длины [math]n[/math] ей требуется [math]O(f(n))[/math] памяти.

См. также

• Классы NP и Σ₁