Классические и квантовые вычисления

Важнейшими ресурсами, требующимися машине Тьюринга для вычислений, является:

(Ответ считается верным, если отмечены все правильные варианты ответов.)

Варианты ответа

время

(Верный ответ)

память

(Верный ответ)

объем вычислений V_М(n)

Похожие вопросы

Функции, которые могут быть вычислены на машине Тьюринга, использующей память, ограниченную полиномом от длины входного слова относятся к классу:

Отличием недетерминированной машины Тьюринга является:

Если характеристическая функция предиката вычислима на машине Тьюринга

, для которой $S_М(n)=\poly(n)$ , то

Для задания состояния машины Тьюринга обязательным является указание:

Условием остановки машины Тьюринга, находящейся в состоянии $(\sigma,p,q)$ , является:

В наборе $\calS,\emptycell,\calA,\calQ,q_0,\delta$ для задания машины Тьюринга множество S является:

Частичная функция

из $\calA^*$ в $\calA^*$ вычислима на машине Тьюринга :

Для вероятностной машины Тьюринга можно определить:

Время работы машины Тьюринга определяется:

Состояние перехода вероятностной машины Тьюринга определяется: