Zobecnění deterministického Turingova stroje , ve kterém z libovolného stavu a hodnot na pásce může stroj provést jeden z několika (lze uvažovat bez ztráty obecnosti - dva) možných přechodů a výběr je vyrobeno pravděpodobnostním způsobem ( hození mincí )
Pravděpodobnostní Turingův stroj je podobný nedeterministickému Turingovu stroji , pouze místo nedeterministického přechodu stroj s určitou pravděpodobností volí jednu z možností.
Existuje také alternativní definice:
Pravděpodobnostní Turingův stroj je deterministický Turingův stroj , který má přídavný hardwarový zdroj náhodných bitů, z nichž libovolný počet může například „objednat“ a „načíst“ na samostatnou pásku a poté použít ve výpočtech obvyklým způsobem pro MT _
Třída algoritmů , které se dokončí v polynomiálním čase na pravděpodobnostním Turingově stroji a vrátí odpověď s chybou menší než 1/3, se nazývá třída BPP .
| Turingův stroj | |
|---|---|
| Možnosti stroje |
|