Belirleyici Olmayan Turing Makinesi
Belirleyici Olmayan Turing Makinesinde, her durum ve sembol için, TM'nin sahip olabileceği bir grup eylem vardır. Yani burada geçişler deterministik değil. Belirleyici olmayan bir Turing Makinesinin hesaplanması, başlangıç konfigürasyonundan ulaşılabilen bir konfigürasyon ağacıdır.
Kabul yapılandırması olan ağacın en az bir düğümü varsa bir girdi kabul edilir, aksi takdirde kabul edilmez. Hesaplama ağacının tüm dalları tüm girdilerde durursa, deterministik olmayan Turing Makinesi,Decider ve bazı girdiler için tüm dallar reddedilirse, girdi de reddedilir.
Belirleyici olmayan bir Turing makinesi, resmi olarak 6-tuple (Q, X, ∑, δ, q 0 , B, F) olarak tanımlanabilir burada -
Q sonlu bir durum kümesidir
X teyp alfabesidir
∑ giriş alfabesidir
δ bir geçiş işlevidir;
δ: Q × X → P (Q × X × {Sola Kaydırma, Sağa Kaydırma}).
q0 başlangıç durumu
B boş semboldür
F nihai durumlar kümesidir