Macchina di Turing non deterministica
In una macchina di Turing non deterministica, per ogni stato e simbolo, ci sono un gruppo di azioni che la MT può avere. Quindi, qui le transizioni non sono deterministiche. Il calcolo di una macchina di Turing non deterministica è un albero di configurazioni che possono essere raggiunte dalla configurazione iniziale.
Un input è accettato se c'è almeno un nodo dell'albero che è una configurazione di accettazione, altrimenti non è accettato. Se tutti i rami dell'albero computazionale si arrestano su tutti gli input, la macchina di Turing non deterministica viene chiamata aDecider e se per qualche input vengono rifiutati tutti i rami, viene rifiutato anche l'ingresso.
Una macchina di Turing non deterministica può essere formalmente definita come una tupla di 6 (Q, X, ∑, δ, q 0 , B, F) dove -
Q è un insieme finito di stati
X è l'alfabeto del nastro
∑ è l'alfabeto di input
δ è una funzione di transizione;
δ: Q × X → P (Q × X × {Shift_sinistra, Shift_Destra}).
q0 è lo stato iniziale
B è il simbolo vuoto
F è l'insieme degli stati finali