Máquina de Turing no determinista

En una máquina de Turing no determinista, para cada estado y símbolo, hay un grupo de acciones que puede tener la MT. Entonces, aquí las transiciones no son deterministas. El cálculo de una máquina de Turing no determinista es un árbol de configuraciones al que se puede acceder desde la configuración inicial.

Se acepta una entrada si hay al menos un nodo del árbol que es una configuración de aceptación; de lo contrario, no se acepta. Si todas las ramas del árbol computacional se detienen en todas las entradas, la máquina de Turing no determinista se llama unDecider y si para alguna entrada se rechazan todas las ramas, la entrada también se rechaza.

Una máquina de Turing no determinista se puede definir formalmente como una tupla de 6 (Q, X, ∑, δ, q ₀ , B, F) donde -

• Q es un conjunto finito de estados

• X es el alfabeto de la cinta

• ∑ es el alfabeto de entrada

• δ es una función de transición;

  δ: Q × X → P (Q × X × {Left_shift, Right_shift}).

• q₀ es el estado inicial

• B es el símbolo en blanco

• F es el conjunto de estados finales