https://enciklopedija.cc/index.php?action=history&feed=atom&title=Probabilisti%C4%8Dki_Turingov_strojProbabilistički Turingov stroj - Povijest promjena2026-07-12T18:51:49ZPovijest promjena ove stranice na wikijuMediaWiki 1.42.3https://enciklopedija.cc/index.php?title=Probabilisti%C4%8Dki_Turingov_stroj&diff=40338&oldid=prevWikiSysop: Bot: Automatski unos stranica2021-08-20T04:27:48Z<p>Bot: Automatski unos stranica</p>
<p><b>Nova stranica</b></p><div><!--'''Probabilistički Turingov stroj'''-->U [[teorija izračunljivosti|teoriji izračunljivosti]], '''probabilistički Turingov stroj''' je [[nedeterministički Turingov stroj]] koji slučajno odabire između dostupnih prijelaza u svakoj diskretnoj točki računanja prema nekoj [[razdioba vjerojatnosti|razdiobi vjerojatnosti]].<br />
<br />
U slučaju jednakih vjerojatnosti za prijelaze se može definirati kao deterministički [[Turingov stroj]] koji ima dodatnu "piši" instrukciju pri čemu je vrijednost pisanja [[uniformna razdioba|uniformno raspodijeljena]] u [[abeceda (računarstvo)|abecedi]] Turingovog stroja (općenito, jednaka izglednost pisanja '1' ili '0' na traku.) Druga uobičajena reformulacija definicije jest jednostavno [[Turingov stroj|deterministički Turingov stroj]] sa dodatnom trakom na kojoj su napisani slučajni bitovi zvanoj ''slučajna traka''.<br />
<br />
Kao posljedica, probabilistički Turingov stroj može (za razliku od determinističkog Turingovog stroja) imati stohastičke rezultate - za dani ulaz i stanje stroja može imati različita vremena izvođenja, pa čak i ne mora uopće stati. Štoviše, može prihvatiti ulaz u jednom izvršavanju i odbaciti isti ulaz u drugom izvršavanju.<br />
<br />
Stoga notacija prihvaćanja niza znakova (stringa) probabilističkim Turingovim strojem može biti definirana na različite načine. Razne vremenski polinomne randomizirane [[računska teorija složenosti|klase složenosti]] koje rezultiraju iz različitih definicija prihvatljivosti uključuju [[RP (složenost)|RP]], Co-RP, [[BPP]] i [[ZPP]]. Ograničavanjem stroja na logaritamski prostor mjesto na polinomno vrijeme, mogu se dobiti analogne klase [[RL]], Co-RL, [[BPL (složenost)|BPL]], te [[ZPL]]. Nametanjem obaju ograničenja dobivaju se klase složenosti [[RLP]], Co-RPL, [[BPLP]], i [[ZPLP]].<br />
<br />
Probabilističko je računanje također važno u definiciji većine klasa [[interaktivni sustav dokazivanja|interaktivnih sustava dokazivanja]], u kojima stroj verifikator ovisi o slučajnosti kako bi izbjegao predvidljivost i tako izbjegao svemoćne strojeve dokazivače. Na primjer, klasa '''IP''' je istovjetna klasi '''[[PSPACE]]''', ali ako se faktor [[slučajnost]]i izbaci iz verifikatora, ostaje se samo sa klasom '''[[NP (složenost)|NP]]''' za koju se vjeruje da je znatno manja.<br />
<br />
Jedno od centralnih pitanja teorije složenosti jest dodaje li slučajnost moć, tj. postoji li problem koji probabilistički Turingov stroj može riješiti u polinomnom vremenu, ali ne i deterministički Turingov stroj? Ili može li deterministički Turingov stroj učinkovito simulirati sve probabilističke Turingove strojeve sa najviše polinomnim usporenjem? Trenutno istraživači vjeruju u istinitost potonje tvrdnje, što pak implicira '''P''' = '''BPP'''. Za isto vrijeme za logaritamski prostor umjesto polinomno vrijeme (je li '''L''' = '''BPLP'''?) se još više vjeruje da je istinito. U drugu ruku, moć koju slučajnost daje interaktivnim sustavima dokazivanja i jednostavnim algoritmima koje stvara za teške probleme kao što su ispitivanje primalnosti (prostosti) broja u polinomnom vremenu te ispitivanje povezanosti grafa u logaritamskom prostoru, naznačuje da bi slučajnost ipak mogla dodati moć.<br />
<br />
[[Kvantno računalo]] je drugi računski model koji je inherentno probabilistički.<br />
<br />
== Vanjske poveznice ==<br />
*[http://www.nist.gov/dads/HTML/probablturng.html NIST stranica o probabilističkim Turingovim strojevima]<br />
[[Kategorija:Računski modeli]]</div>WikiSysop