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 ₀ , 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}).

• q₀ è lo stato iniziale

• B è il simbolo vuoto

• F è l'insieme degli stati finali