O generalizare a unei mașini Turing deterministe , în care, din orice stare și valori de pe bandă, mașina poate face una dintre mai multe (se poate considera, fără pierderea generalității - două) posibile tranziții și alegerea se face într-o manieră probabilistică ( aruncarea unei monede )
O mașină Turing probabilistică este similară cu o mașină Turing nedeterministă , doar că în loc de o tranziție nedeterministă, mașina alege una dintre opțiunile cu o oarecare probabilitate.
Există, de asemenea, o definiție alternativă:
O mașină Turing probabilistică este o mașină Turing deterministă care are o sursă hardware suplimentară de biți aleatori, dintre care orice număr, de exemplu, poate „ordona” și „încărca” pe o bandă separată și apoi poate utiliza în calcule în mod obișnuit pentru MT .
Clasa de algoritmi care se completează în timp polinomial pe o mașină Turing probabilistică și returnează un răspuns cu o eroare mai mică de 1/3 se numește clasa BPP .
| mașină Turing | |
|---|---|
| Opțiuni de mașină |
|