База ответов ИНТУИТ

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

<<- Назад к вопросам

Множество состояний управляющего устройства в наборе \calS,\emptycell,\calA,\calQ,q_0,\delta для задания машины Тьюринга - это:

(Отметьте один правильный вариант ответа.)

Варианты ответа
\calS
\calA
\calQ(Верный ответ)
Похожие вопросы
В наборе \calS,\emptycell,\calA,\calQ,q_0,\delta для задания машины Тьюринга множество S является:
В наборе \calS,\emptycell,\calA,\calQ,q_0,\delta для задания машины Тьюринга выполняется условие:
Количество состояний системы, где S - память, \callQ,\calA - соответственно множество состояний управляющего устройства и алфавит рассматриваемой машины Тьюринга, определяется по формуле:
В формуле |\calA|^S\cdot|\calQ|\cdot S для нахождения количества состояний системы, \calQ - это:
Состояние машины Тьюринга задается тройкой (\sigma,p,q) , где бесконечное слово в алфавите \calS - это:
Последовательность перестановок U_1[A_1],\dots, U_l[A_l], где A_j - множества битов, U_j\in\calA, \calA - некоторое множество перестановок вида G\colon\cb^k \to \cb^k является:
Частичная функция f из \calA^* в \calA^* вычислима на машине Тьюринга :
Условие существования вероятностной машины Тьюринга М и полинома p(n), причем машина М заведомо остановится за время, не превосходящее p(|x|), определяет, что:
Зная, что \Prob\left[\left|\frac{\sum\nolimits_{r=1}^{s}y_r}{s}-\PP(1\big|k)\right| >\delta\right]<2e^{-c\delta^{2}s}, где c>0 - константа, за сколько испытаний можно добиться вероятности ошибки \eps при фиксированном \delta:
Перестановка, реализуемая обратимой схемой, является (\calA - некоторое множество перестановок вида G\colon\cb^k \to \cb^k):