Probabilistički Turingov stroj
U 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 razdiobi vjerojatnosti.
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 uniformno raspodijeljena u abecedi Turingovog stroja (općenito, jednaka izglednost pisanja '1' ili '0' na traku.) Druga uobičajena reformulacija definicije jest jednostavno deterministički Turingov stroj s dodatnom trakom na kojoj su napisani slučajni bitovi zvanoj slučajna traka.
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.
Stoga notacija prihvaćanja niza znakova (stringa) probabilističkim Turingovim strojem može biti definirana na različite načine. Razne vremenski polinomne randomizirane klase složenosti koje rezultiraju iz različitih definicija prihvatljivosti uključuju 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, te ZPL. Nametanjem obaju ograničenja dobivaju se klase složenosti RLP, Co-RPL, BPLP, i ZPLP.
Probabilističko je računanje također važno u definiciji većine klasa 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čajnosti izbaci iz verifikatora, ostaje se samo s klasom NP za koju se vjeruje da je znatno manja.
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 s 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ć.
Kvantno računalo je drugi računski model koji je inherentno probabilistički.