Функции, которые могут быть вычислены на машине Тьюринга, использующей память, ограниченную полиномом от длины входного слова относятся к классу:
(Отметьте один правильный вариант ответа.)
Варианты ответа
(Верный ответ)
Похожие вопросы
Важнейшими ресурсами, требующимися машине Тьюринга для вычислений, является:
Какому классу принадлежит , если существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что Б имеет выигрышную стратегию (Б - игрок, имеющих имя "белые"):
Если характеристическая функция предиката вычислима на машине Тьюринга , для которой , то
Количество состояний системы, где - память, - соответственно множество состояний управляющего устройства и алфавит рассматриваемой машины Тьюринга, определяется по формуле:
Частичная функция из в вычислима на машине Тьюринга :
Отличием недетерминированной машины Тьюринга является:
Время работы машины Тьюринга определяется:
Для вероятностной машины Тьюринга можно определить:
Состояние перехода вероятностной машины Тьюринга определяется:
Для задания состояния машины Тьюринга обязательным является указание: