מכונת טיורינג לא דטרמיניסטית

הגדרה: מכונת טיורינג לא דטרמינסטית הינה חמישיה: S,h),  (Q,S, = N

כאשר: Q                    קבוצת מצבים סופית.

S             א"ב  סופי ( S Î (#

 Î Q             h      מצב עצירה.

             Î Q s      מצב התחלתי.

                  Δ       טבלת מעברים

 [ (Q – { h } ) x S ] x [ Q x S È { L, R } ] Δ  Í

   

במכונה לא דטרמינסטית, מה שלא כתוב בטבלה לא קיים! המכונה נתקעת.