![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/5/51/NonDtT.svg/langpl-640px-NonDtT.svg.png&w=640&q=50)
Niedeterministyczna maszyna Turinga
Z Wikipedii, wolnej encyclopedia
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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/5/51/NonDtT.svg/640px-NonDtT.svg.png)
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).
Dany problem może zostać rozwiązany w czasie wielomianowym na niedeterministycznej maszynie Turinga wtedy i tylko wtedy, gdy poprawność rozwiązania tego problemu jest weryfikowalna w czasie wielomianowym na deterministycznej maszynie Turinga. Tego rodzaju problemy należą do klasy NP (nondeterministic polynomial time).