section_heading: Nedeterministički Turingov stroj
paragraph_text: Čitanjem znaka X s ulazne trake, pri čemu je upravljačka jedinka u stanju q, TS prelazi u neko od stanja <math>p_i</math>, na traku zapiše znak <math>Z_i</math>, te miče glavu u smjeru <math>D_i</math>. Promijeni li se stanje u <math>p_i</math>, na traku nije moguće zapisati znak <math>Z_j</math> ili pomaknuti glavu u smjeru <math>D_j</math>, gdje je <math>i \ne j</math>. Završi li barem jedan slijed prijelaza prihvatljivim stanjem, niz se prihvaća. Ne završi li niti jedan slijed prijelaza prihvatljivim stanjem, niz se ne prihvaća.