Valószínűségi Turing-gép

Egy determinisztikus Turing-gép általánosítása , amelyben a szalagon lévő bármely állapotból és értékből a gép a több (az általánosság elvesztése nélkül figyelembe vehető - kettő) lehetséges átmenet közül egyet tud végrehajtani, és a választás valószínűségi módszerrel készült ( érme feldobása )

A valószínűségi Turing-gép hasonló a nem determinisztikus Turing-géphez , csak a nem-determinisztikus átmenet helyett a gép bizonyos valószínűséggel választ egyet a lehetőségek közül.

Van egy alternatív definíció is:

A valószínűségi Turing-gép egy determinisztikus Turing-gép , amely további hardverforrással rendelkezik véletlenszerű bitekből, amelyekből például tetszőleges számú „rendelhető” és „betöltés” ​​egy külön szalagra, majd a szokásos módon használható számításokhoz. MT .

Azoknak az algoritmusoknak az osztályát , amelyek egy valószínűségi Turing-gépen polinomiális időben fejeződnek be, és 1/3-nál kisebb hibával adnak választ, BPP osztálynak nevezzük .