Next: Kvantový Turingův stroj
Up: Matematické modely počítačů
Previous: Klasický Turingův stroj
  Obsah
V předchozím odstavci jsme se zabývali deterministickou verzí Turingova stroje.
Nyní si však představme, že vývoj mezi stavy se řídí podle toho, jaký je
výsledek nějakého náhodného jevu - například hodu kostkou. V takovém případě
je následující stav určen stochasticky výsledkem hodu. Navíc s
možností upřednostnit nebo potlačit některé směry vývoje pomocí váhových
koeficientů. Na tomto základu je založen pravděpodobnostní Turingův stroj
(PTS). PTS je schopen řešit všechny problémy deterministického Turingova stroje
a často dokonce dojde k řešení rychleji. U obou typů strojů vlastně
balancujeme mezi dvěma póly:
jistota, že dojdeme k řešení (pokud existuje) u klasického Turingova stroje
stojí proti možnosti, že najdeme správné řešení rychleji u PTS.
Přestože je Turingův stroj matematickým modelem, nezbavil se všech zátěží
klasické fyziky a jako takový vychází z jejích poznatků. Se znalostmi
kvantové mechaniky však bylo možné ideu PTS upravit a definovat tak
model, který popsal proces kvantového výpočtu.
Bashar
2001-01-23