next up previous contents
Next: Kvantový Turingův stroj Up: Matematické modely počítačů Previous: Klasický Turingův stroj   Obsah

Pravděpodobnostní Turingův stroj

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