Nedeterministička Tjuringova mašina

U teoriji računarstva, Tjuringova mašina je teoretska mašina koja se koristi u misaonim eksperimentima da bi se ispitale mogućnosti i ograničenja računara.

U suštini, Tjuringova mašina je jednostavan računar koji čita i upisuje pojedinačne simbole na beskonačnoj traci, striktno poštujući predefinisan skup pravila. Ona određuje koju akciju će preduzeti na osnovu svog trenutnog stanja i simbola koji učita. Primer jednog od pravila Tjuringove mašine je: „Ako si u stanju 2 i učitaš simbol A, promeni ga u B i pomeri traku levo“.

Kod determinističke Tjuringove mašine, skup pravila jednoznačno određuje njenu akciju u svakoj situaciji. Nedeterministička Tjuringova mašina (NTM) sa druge strane, može da ima skup pravila koja omogućavaju više različitih akcija u datoj situaciji. Na primer, nedeterministička Tjuringova mašina može u svom skupu pravila istovremeno da ima pravilo: „ Ako si u stanju 2 i učitaš simbol A, promeni ga u B i pomeri traku levo“ i pravilo: „ Ako si u stanju 2 i učitaš simbol A, promeni ga u C i pomeri traku desno“.

Deterministička Tjuringova mašina (DTM) ima funkciju prenosa koja na osnovu zadatog stanja mašine i učitanog simbola određuje sledeće tri stvari:

simbol koji treba da bude upisan na traku,
smer pomeranja trake (levo, desno, ili ostanak u mestu),
sledeće stanje mašine.

Na primer, za učitano X sa trake u stanju 3, DTM može da upiše Y, pomeri traku desno i promeni stanje u 5. Nedeterministička Tjuringova mašina (NTM) se od determinističke razlikuje u tome što njene akcije nisu jednoznačno određene njenim stanjem i učitanim simbolom. Mnoge različite akcije mogu da budu izvedene sa istom kombinacijom stanja i učitanih simbola. Na primer: učitano X sa trake u stanju 3 može da dozvoli da NTM upiše Y, pomeri traku desno i pređe u stanje 5, ili da upiše X, pomeri traku levo i ostane u stanju 3.

Definicija[uredi | uredi izvor]

Nedeterministička Tjuringova mašina može formalno da se definiše šestorkom $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$ , gde su:

$Q$ konačni skup stanja,
$\Sigma$ konačni skup simbola (azbuka trake),
$\iota \in Q$ početno stanje,
$\sqcup \in \Sigma$ simbol „prazan“ (blanko),
$A\subseteq Q$ skup prihvatljivih stanja,
$\delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,R\}\right)$ relacija nad stanjima i simbolima – prenosna relacija. $L$ pomeraj ulevo i $R$ pomeraj udesno.

Razlika od standardne (determinističke) Tjuringove mašine je što su kod njih prelazne relacije funkcije ( funkcije prelaza). Konfiguracije i relacija prinosa na konfiguracijama, koja opisuje moguće akcije Tjuringove mašine za bilo koji mogući dati sadržaj trake, su iste kao i za standardne Tjuringove mašine, osim što relacija prinosa nije više sa jednom vrednošću. Izraz za prihvatanje stringa je nepromenjen: nedeterministička Tjuringova mašina prihvata string ako, kad je mašina pokrenuta sa konfiguracijom u kojoj je glava trake na prvom karakteru stringa ( ako ga ima), i traka je prazna inače, bar jedan od mogućih proračuna mašine iz te konfiguracije dovodi mašinu u stanje u $A$ . ( ako je mašina deterministička, mogući proračuni su prefiksi jedne, moguće beskonačne, putanje.)

Odluka više pravila[uredi | uredi izvor]

Kako NTM „zna“ koju od ovih akcija da preuzme? Postoje dva pogleda na ovo. Jedan je da kažemo da je mašina „najsrećniji mogući pogađač“; uvek bira prelaz stanja koji će dovesti do prihvatljivog stanja, ako takva promena postoji. Drugi pogled je da zamislimo da se mašina „grana“ u puno kopija, od kojih svaka prati jedan od mogućih prelaza stanja. Dok DTM ima jedinstvenu „putanju proračuna“ koju prati, NTM ima „drvo proračuna“. Ako se bar jedna grana drveta zaustavi sa uslovom prihvatanja, kažemo da NTM prihvata ulaz.

Ekvivalencija sa DTM[uredi | uredi izvor]

Konkretno, nedeterminističke Tjuringove mašine su ekvivalentne sa determinističkim Tjuringovim mašinama. Ekvivalencija se odnosi ona to šta se može obraditi naspram toga koliko brzo se to može obraditi. NTM uključuju DTM kao specijalne slučajeve, pa je jasno da DTM nisu moćnije. Može nam se učiniti da su NTM moćnije od DTM, s obzirom na to da omogućavaju stabla mogućih proračuna koji proističu iz iste početne konfiguracije, prihvatajući string ako ga bilo koja grana u stablu prihvata.

Međutim, moguće je simulirati NTM uz pomoć DTM: Jedan način je da korišćenjem DTM čije konfiguracije predstavljaju više konfiguracija NTM, pri čemu se operacija DTM sastoji u naizmeničnom posećivanju svake od njih, izvršavajući jedan korak pri svakoj poseti i dajući nove konfiguracije kad god relacija prelaza stanja definiše više kontinualnosti. Drugačija konstrukcija^[1] simulira NTM sa DT mašinom sa 3 trake, od kojih prva traka uvek čuva originalni ulazni string, drug se koristi da simulira određen proračun NTM, i treća kodira putanju stablu obrade NT mašine. DTM sa tri trake se lako slimuliraju uz pomoć normalne DTM sa jednom trakom.

Kod ovakve konstrukcije, rezultujuća DTM efektivno obavlja [Pretraga u širinu[|pretraživanje po širini]] stabla obrade NT mašine, posećujući sve moguće proračune NT mašine po rastućoj dužini dok ne nađe onaj koji je prihvatljiv. Stoga, dužina prihvatljivog proračuna DT mašine je, uopšteno, eksponent dužine najkraćeg prihvatljivog proračuna NT mašine. Ovo se smatra kao uopšteno svojstvo simulacija NT mašina DT mašinama; Najpoznatije nerešeno pitanje u računarskoj nauci, problem P=NP, je vezan za ovo.

Ograničen ne-determinizam[uredi | uredi izvor]

NTM ima svojstvo ograničenog ne-determinizma, na primer, ako se NTM uvek zaustavlja na datoj ulaznoj traci 7 onda se zaustavlja u ograničenom broju koraka, i stoga može imati samo ograničen broj mogućih konfiguracija.

Poređenje sa kvantnim kompjuterima[uredi | uredi izvor]

Uobičajena je greška da se smatra da su kvantni kompjuteri isto što i NTM.^[2] Veruje se, ali nije dokazano da moć kvantnih kompjutera ne može da se poredi sa moći NT mašina^[3], tj, verovatno postoje problemi koje NTM mogu efikasno da reše, dok kvantni kompjuter ne može. Mogući primer problema koji su rešivi NT mašinom, a nisu rešivi kvantnim kompjuterom u polinomijalnom vremenu su NP-kompletni problemi.

Reference[uredi | uredi izvor]

^ Elements of the Theory of Computation, by Harry R. Lewis and Christos H. Papadimitriou, Prentice-Hall, Englewood Cliffs, New Jersey. 1981. ISBN 978-0-13-273417-2. str. 206-211.
^ The Orion Quantum Computer Anti-Hype FAQ, Scott Aaronson.
^ Tušarová, Tereza (2004). „Quantum complexity classes”. arXiv:cs/0409051 .

Spoljašnje veze[uredi | uredi izvor]

[1] Elements of the Theory of Computation, by Harry R. Lewis and Christos H. Papadimitriou, Prentice-Hall, Englewood Cliffs, New Jersey. 1981. ISBN 978-0-13-273417-2. str. 206-211.

[2] The Orion Quantum Computer Anti-Hype FAQ, Scott Aaronson.

[3] Tušarová, Tereza (2004). „Quantum complexity classes”. arXiv:cs/0409051 .

[1]

[2]

[3]