Nedeterministički Turingov stroj

U računarstvu, nedeterministički Turingov stroj (NTS) je Turingov stroj čiji upravljački mehanizam operira slično onome nedeterminističkog konačnog automata.

Opis

Obični (deterministički) Turingov stroj (DTS) ima funkciju prijelaza koja, za dano stanje i znak (simbol) trake ispod glave za čitanje i pisanje, specificira tri stvari: znak koji se piše na traku, smjer (lijevi ili desni) pomaka glave, te sljedeće stanje upravljačke jedinke. Na primjer, znak X na traci u stanju 3 može učiniti da DTS zapiše znak Y na traku, pomakne glavu jednu poziciju u desno, i promijeni stanje u 5.

NTS se razlikuje u tome što stanje i ulazni znak trake više ne specificiraju jedinstveno ove promjene - mnoge različite akcije se mogu primjeniti za istu kombinaciju stanja i pročitanog znaka. Na primjer, X na traci u stanju 3 sad može dozvoliti NTS da zapiše Y, pomakne glavu u desno te promijeni stanje u 5, ili da zapiše znak X, pomakne glavu u lijevo, i ostane u stanju 3.

Kako NTS "zna" koju bi od ovih akcija trebao obaviti? Postoje dva načina gledanja na ovaj problem. Jedan od njih je gledanje na stroj kao "najsretnijeg mogućeg odabratelja" - uvijek odabire onaj prijelaz koji s vremenom vodi u prihvatljivo stanje, ukoliko on uopće postoji. Drugi način gledanja jest zamišljanje da se stroj "grana" u mnogo kopija, od kojih svaka slijedi jedan mogući prijelaz. Dok DTS ima jedinstven "put računanja" kojeg slijedi, NTS ima "stablo računanja". Ako bilo koja grana stabla stane u "prihvatljivim" uvjetima, kažemo da NTS prihvaća ulaz.

Definicija

Formalnije, nedeterministički Turingov stroj je uređena šestorka [math]\displaystyle{ M=(Q, \Sigma, \iota, \sqcup, A, \delta) }[/math], pri čemu je

• [math]\displaystyle{ Q }[/math] konačan skup stanja
• [math]\displaystyle{ \Sigma }[/math] konačan skup znakova (simbola) (abeceda trake)
• [math]\displaystyle{ \iota \in Q }[/math] početno stanje
• [math]\displaystyle{ \sqcup }[/math] znak kojim se označava prazna ćelija ([math]\displaystyle{ \sqcup \in \Sigma }[/math])
• [math]\displaystyle{ A \subseteq Q }[/math] skup prihvatljivih stanja
• [math]\displaystyle{ \delta: Q \backslash A \times \Sigma \rightarrow \left( Q \times \Sigma \times \{L,R\} \right) }[/math] viševrijednosna funkcija nad stanjima i znakovima zvana funkcija prijelaza, pri čemu je L pomak u lijevo i R pomak u desno. U konvencionalnim Turingovim strojevima, funkcija prijelaza nije viševrijednosna.

Varijacije

Postoji velik broj varijacija ove definicije. Na primjer, početno stanje može biti zamijenjeno skupom početnih stanja. (Ovo je istovjetna definicija jer je trivijalno simulirati višestruka početna stanja dodavanjem jednog početnog stanja koji ih nedeterministički odabire.)

Varijacija također može sadržavati skup odbijajućih stanja, u kojem pak slučaju se kaže da NTS odbija sve putove računanja koji vode do odbijajućih stanja.

Istovjetnost sa DTS

Intuitivno može izgledati da su NTS moćniji od DTS, pošto mogu izvršavati mnogo mogućih računanja odjednom, zahtijevajući da samo jedan od njih uspije. Ali bilo koji jezik kojeg prihvaća NTS također može prihvatiti DTS: DTS može simulirati svaki prijelaz NTS, praveći višestruke kopije simuliranog stanja kad su višestruki prijelazi dozvoljeni, i simulirajući ih sve paralelno, ne poput procesa u višezadaćnim operacijskim sustavima.

Očito je da ovakav način simulacije zahtijeva značajno veći potrošak vremena. Koliko točno veći se općenito ne zna - ovo je, ukratko, definicija "Je li P = NP?" problema (vidjeti klase složenosti P i NP).

Usporedba sa ostalim računskim modelima

NTS ima svojstvo ograničenog nedeterminizma, tj. ako NTS uvijek staje za danu ulaznu traku T, tada on staje i u ograničenom broju konfiguracija. Ovo je svojstvo važno prilikom suprostavljanja nekih drugih modela konkurentnih računanja kao što je Actor model, koji pak imaju svojstvo neograničenog nedeterminizma.

Uobičajena je miskoncepcija da su kvantna računala NTS. Vjeruje da je moć vremenski polinomnih kvantnih računala neusporediva onoj vremenskih polinomnih NTS. To jest, za svaki od ta dva računska modela postoji problem koji jedan može riješiti, a drugi vrlo izvjesno ne može. Izgledan primjer problema koje rješavaju NTS, ali ne i vremenski polinomna kvantna računala, su NP-potpuni problemi.

Vidjeti također

• Probabilistički Turingov stroj

Izvori

• Harry R. Lewis, Christos Papadimitriou (1981). Elements of the Theory of Computation (1st edition ed.). Prentice-Hall. ISBN 0-13-273417-6  Section 4.6: Nondeterministic Turing machines, pp. 204–211.
• John C. Martin (1997). Introduction to Languages and the Theory of Computation (2nd edition ed.). McGraw-Hill. ISBN 0-07-040845-9  Section 9.6: Nondeterministic Turing machines, pp. 277–281.
• Christos Papadimitriou (1993). Computational Complexity (1st edition ed.). Addison-Wesley. ISBN 0-201-53082-1  Section 2.7: Nondeterministic machines, pp. 45–50.

Vanjske poveznice

• besplatni C++ simulator nedeterminističkog višetračnog Turingovog stroja