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