thumb|300px|right|Drzewo obliczeń niedeterministycznej maszyny Turinga. Niedeterminizm można interpretować jako stworzenie tylu kopii maszyny Turinga ile jest możliwych stanów do których może przejść maszyna, a następnie zastosowanie poszczególnych możliwych ruchów dla każdej kopii. Niedeterministyczna maszyna Turinga – teoretyczny model rozważany w teorii obliczeń w celu badania problemów decyzyjnych. Niedeterministyczna maszyna Turinga jest zdefiniowana tak samo jak deterministyczna maszyna Turinga z jedyną różnicą dotyczącą postaci funkcji przejścia, która w przypadku maszyn niedeterministycznych zwraca zbiór możliwych działań maszyny.
Ewolucje niedeterministycznej maszyny Turinga można reprezentować w postaci drzewa w którym każdy poziom odpowiada jednemu krokowi maszyny, natomiast rozgałęzienia wynikają z niedeterminizmu funkcji przejścia. Taka maszyna kończy prace w momencie, gdy dochodzi do poziomu ze stanem końcowym w co najmniej jednym z węzłów. W tym modelu kolejny krok maszyny liczony jest jako przejście do następnego zbioru możliwych stanów (poziomu drzewa).