Увеличивает ли недетерминированность возможности машин - это открытый вопрос для всех ( кроме наиболее простых) ... - Большая Энциклопедия Нефти и Газа
Выдержка из книги
Лупанов О.Б.
Кибернетический сборник Выпуск20
Увеличивает ли недетерминированность возможности машин - это открытый вопрос для всех ( кроме наиболее простых) моделей вычислений. ТМ могут распознавать больше языков, чем детерминированные многоленточные ТМ. Доказательство использует альтернирующие машины.