En generalisering af en deterministisk Turing-maskine , hvor maskinen fra en hvilken som helst tilstand og værdier på båndet kan foretage en af flere (det kan overvejes, uden tab af generalitet - to) mulige overgange, og valget er lavet på en sandsynlig måde ( kaste en mønt )
En probabilistisk Turing-maskine ligner en ikke- deterministisk Turing-maskine , kun i stedet for en ikke-deterministisk overgang vælger maskinen en af mulighederne med en vis sandsynlighed.
Der er også en alternativ definition:
En probabilistisk Turing-maskine er en deterministisk Turing-maskine , der har en ekstra hardwarekilde af tilfældige bits, hvoraf et hvilket som helst antal, for eksempel, kan "bestille" og "indlæse" på et separat bånd og derefter bruge i beregninger på sædvanlig måde for MT .
Klassen af algoritmer , der fuldfører i polynomisk tid på en probabilistisk Turing-maskine og returnerer et svar med en fejl på mindre end 1/3, kaldes BPP-klassen .
| Turing maskine | |
|---|---|
| Maskine muligheder |
|