Em uma Máquina de Turing Não Determinística, para cada estado e símbolo, há um grupo de ações que a MT pode ter. Portanto, aqui as transições não são determinísticas. O cálculo de uma Máquina de Turing não determinística é uma árvore de configurações que pode ser alcançada desde a configuração inicial.
Uma entrada é aceita se houver pelo menos um nó da árvore que seja uma configuração aceita, caso contrário, não é aceita. Se todos os ramos da árvore computacional param em todas as entradas, a Máquina de Turing não determinística é chamada deDecider e se para alguma entrada todos os ramos forem rejeitados, a entrada também será rejeitada.
Uma máquina de Turing não determinística pode ser definida formalmente como uma 6-tupla (Q, X, ∑, δ, q 0 , B, F) onde -
Q é um conjunto finito de estados
X é o alfabeto da fita
∑ é o alfabeto de entrada
δ é uma função de transição;
δ: Q × X → P (Q × X × {Left_shift, Right_shift}).
q0 é o estado inicial
B é o símbolo em branco
F é o conjunto de estados finais