Недетерминированная машина Тьюринга
В недетерминированной машине Тьюринга для каждого состояния и символа существует группа действий, которые TM может выполнять. Итак, здесь переходы не детерминированы. Вычисление недетерминированной машины Тьюринга - это дерево конфигураций, к которым можно получить доступ из начальной конфигурации.
Ввод принимается, если есть хотя бы один узел дерева, который является приемлемой конфигурацией, в противном случае он не принимается. Если все ветви вычислительного дерева останавливаются на всех входах, недетерминированная машина Тьюринга называетсяDecider и если для некоторого ввода все ветви отклоняются, ввод также отклоняется.
Недетерминированную машину Тьюринга можно формально определить как набор из шести (Q, X, ∑, δ, q 0 , B, F), где -
Q конечный набор состояний
X ленточный алфавит
∑ это входной алфавит
δ - функция перехода;
δ: Q × X → P (Q × X × {левый_сдвиг, правый_сдвиг}).
q0 это начальное состояние
B это пустой символ
F это набор конечных состояний