Niedeterministyczna maszyna Turinga
W niezdeterministycznej maszynie Turinga dla każdego stanu i symbolu istnieje grupa działań, które może mieć TM. Tak więc tutaj przejścia nie są deterministyczne. Obliczenia niedeterministycznej maszyny Turinga to drzewo konfiguracji, do których można dotrzeć z konfiguracji początkowej.
Dane wejściowe są akceptowane, jeśli istnieje co najmniej jeden węzeł drzewa, który jest akceptowaną konfiguracją, w przeciwnym razie nie jest akceptowany. Jeśli wszystkie gałęzie drzewa obliczeniowego zatrzymują się na wszystkich wejściach, niedeterministyczna Maszyna Turinga nazywa się aDecider a jeśli dla jakiegoś wejścia wszystkie gałęzie są odrzucone, wejście jest również odrzucane.
Niedeterministyczną maszynę Turinga można formalnie zdefiniować jako 6-krotkę (Q, X, ∑, δ, q 0 , B, F), gdzie -
Q jest skończonym zbiorem stanów
X to alfabet taśmy
∑ jest alfabetem wejściowym
δ jest funkcją przejścia;
δ: Q × X → P (Q × X × {Przesunięcie_ w lewo, Przesunięcie_ w prawo}).
q0 jest stanem początkowym
B jest pustym symbolem
F jest zbiorem stanów końcowych