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

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

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

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

Состояние машины Тьюринга задается тройкой , где бесконечное слово в алфавите - это:

Состояние, заданное вектором (), называется:

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

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

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

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

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