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

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

За какое количество тактов машина Тьюринга с оракулом проверяет, принадлежит ли записанное на оракульной ленте слово языку $\calA$ :

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

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

за три такта

за два такта

за один такт(Верный ответ)

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

Последовательность перестановок $U_1[A_1],\dots, U_l[A_l]$ , где A_j

- множества битов, $U_j\in\calA$ , $\calA$ - некоторое множество перестановок вида $G\colon\cb^k \to \cb^k$ является:

Количество состояний системы, где

- память, $\callQ,\calA$ - соответственно множество состояний управляющего устройства и алфавит рассматриваемой машины Тьюринга, определяется по формуле:

Перестановка, реализуемая обратимой схемой, является ( $\calA$ - некоторое множество перестановок вида $G\colon\cb^k \to \cb^k$ ):

За какое количество шагов классический компьютер вычислит значение предиката $F(x)\double=\exists\, y\:\calA(x,y)$ (

- количество битов в записи y):

Частичный след от оператора $\calA$ по пространству $\calF$ имеет вид:

Для квантовой схемы $\calA$ - последовательности $U_l[A_l]\cdot\ldots\cdot U_1[A_1]$ , A_j

выступает в роли:

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

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

Выберите верные тождества, где $\calA$ - язык, $y_i\in\cb$ :

За какое время квантовый компьютер вычислит значение предиката $F(x)\double=\exists\, y\:\calA(x,y)$ (

- количество шагов):

Условие существования вероятностной машины Тьюринга

и полинома p(n)

, причем машина

заведомо остановится за время, не превосходящее p(|x|)

, определяет, что:

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

За какое количество тактов машина Тьюринга с оракулом проверяет, принадлежит ли записанное на оракульной ленте слово языку :

За какое количество тактов машина Тьюринга с оракулом проверяет, принадлежит ли записанное на оракульной ленте слово языку $\calA$ :