Deterministisen Turingin koneen yleistys , jossa kone voi mistä tahansa nauhan tilasta ja arvoista tehdä yhden useista (voidaan harkita yleisyyden menettämättä kahdesta) mahdollisesta siirtymästä, ja valinta on tehty todennäköisyydellä ( kolikkoa heittämällä )
Probabilistinen Turingin kone on samanlainen kuin ei- deterministinen Turingin kone , vain ei-deterministisen siirtymän sijaan kone valitsee jonkin vaihtoehdoista jollain todennäköisyydellä.
On myös vaihtoehtoinen määritelmä:
Todennäköisyyspohjainen Turingin kone on deterministinen Turingin kone , jossa on ylimääräinen laitteistolähde satunnaisia bittejä, joita se voi esimerkiksi "järjestää" ja "ladata" erilliselle nauhalle ja käyttää sitten laskelmissa tavalliseen tapaan MT .
Algoritmien luokkaa , joka valmistuu polynomiajassa todennäköisyyspohjaisessa Turingin koneessa ja palauttaa vastauksen, jonka virhe on pienempi kuin 1/3, kutsutaan BPP-luokiksi .
| Turingin kone | |
|---|---|
| Konevaihtoehdot |
|