Увеличивает ли недетерминированность возможности машин - это открытый вопрос для всех ( кроме наиболее простых) ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Лупанов О.Б. Кибернетический сборник Выпуск20


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

(cкачать страницу)

Смотреть книгу на libgen

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