En generalisering av en deterministisk Turing-maskin , där maskinen, från vilket tillstånd och värden som helst på bandet, kan göra en av flera (det kan övervägas, utan förlust av generalitet - två) möjliga övergångar och valet är gjord på ett probabilistiskt sätt ( kasta ett mynt )
En probabilistisk Turing-maskin liknar en icke- deterministisk Turing-maskin , men istället för en icke-deterministisk övergång väljer maskinen ett av alternativen med viss sannolikhet.
Det finns också en alternativ definition:
En probabilistisk Turing-maskin är en deterministisk Turing-maskin som har en extra hårdvarukälla av slumpmässiga bitar, varav valfritt antal, till exempel, kan "beställa" och "ladda" på ett separat band och sedan använda i beräkningar på vanligt sätt för MT .
Klassen av algoritmer som slutförs i polynomtid på en probabilistisk Turing-maskin och returnerar ett svar med ett fel på mindre än 1/3 kallas BPP-klassen .
| Turing maskin | |
|---|---|
| Maskinalternativ |
|