Az elméleti számítástechnikában a probabilisztikus Turing-gép egy nemdeterminisztikus Turing-gép, amely minden pontban a rendelkezésre álló átmenetek közül választ egy valószínűség-eloszlás szerint. Ennek következtében egy valószínűségi Turing-gép (ellentétben egy determinisztikus Turing-géppel) sztochasztikus eredményeket hozhat; azaz egy adott bemeneten és utasításállapot-gépen eltérő futási időkkel rendelkezhet, vagy egyáltalán nem állhat meg; továbbá elfogadhat egy bemenetet az egyik végrehajtás során, és elutasíthatja ugyanazt a bemenetet egy másik végrehajtás során.
Abban az esetben, ha az átmenetek valószínűsége egyenlő, a valószínűségi Turing-gépek definiálhatók olyan determinisztikus Turing-gépekként, amelyek rendelkeznek egy további "írás" utasítással, ahol az írás értéke egyenletesen oszlik el a Turing-gép ábécéjében (általában egyenlő a valószínűsége annak, hogy az "1" vagy a "0" felkerül a szalagra). Egy másik gyakori átfogalmazás az, hogy egyszerűen egy determinisztikus Turing-gépet használunk egy hozzáadott, véletlenszerű bitekkel teli szalaggal, amelyet "véletlenszerű szalagnak" nevezünk.
A kvantumszámítógép (vagy kvantum Turing-gép) egy másik számítási modell, amely eredendően valószínűségi.
Leírás A valószínűségi Turing-gép egy olyan nemdeterminisztikus Turing-gép, amelyben minden nemdeterminisztikus lépés egy „érmefeldobás”, azaz minden lépésben két lehetséges következő lépés van, és a Turing-gép valószínűségileg kiválasztja, hogy melyik lépést tegye meg.Sipser 2006, 368.o.
Formális definíció A probablisztikus Turing-gép egy 7-tagú rendezett halmaz: , ahol:
egy véges állapothalmaz a bemeneti ábécé a szalagalábécé, amely tartalmazza az üres szimbólumot is: # a kezdőállapot az elfogadó (vég-)állapotok halmaza az első probabilisztikus átmenetfüggvény, a szalagon balra, jobbra történő elmozdulást jelöli. a második probabilisztikus átmenetfüggvény
A gép minden lépésben véletlenszerűen választja ki, hogy vagy szerint lép továbbSanjeev, Boaz 2016, 125.o. — ez a választás független minden korábbi lépéstől, hasonlóan egy pénzfeldobáshoz.
Ez a véletlenszerűség hibát vezethet be: olyan stringek is elutasíthatók, amelyeket el kellene fogadni, és fordítva. Ennek kezelésére egy nyelvet az gép akkor ismeri fel hibavalószínűséggel, ha
Ha string az -ben van, az azt jelenti, hogy Ha a string nem -ben van, akkor
Komplexitási osztályok Megoldatlan probléma a számításelméletben: P = PBP ?
A valószínűségi érmefeldobások használata által bevezetett hiba eredményeként a karakterlánc valószínűségi Turing-gép általi elfogadásának fogalma többféleképpen definiálható. Az egyik ilyen fogalom, amely több fontos bonyolultsági osztályt foglal magában, az 1/3-os hibavalószínűség megengedése. Például a BPP bonyolultsági osztály azon nyelvek osztálya, amelyeket egy valószínűségi Turing-gép polinomiális időben 1/3-os hibavalószínűséggel ismer fel. Egy másik osztály, amelyet az elfogadás ezen fogalmával definiáltak, a BPL, amely megegyezik a BPP-vel, de további megkötést tesz, hogy a nyelveknek logaritmikus térben kell megoldhatóknak lenniük.
Az elfogadás más definícióiból származó komplexitási osztályok közé tartozik az RP, a co-RP és a ZPP. Ha a gépet logaritmikus térre korlátozzuk polinomiális idő helyett, akkor az analóg RL, co-RL és ZPL komplexitási osztályokat kapjuk. Mindkét korlátozás érvényesítésével RLP, co-RLP, BPLP és ZPLP komplexitási osztályokat kapjuk.
A valószínűségi számítás kritikus fontosságú az interaktív bizonyítási rendszerek legtöbb osztályának definiálásához is, amelyekben az ellenőrző gép a véletlenszerűségre támaszkodik, hogy elkerülje a mindenható bizonyító gép általi előrejelzést és becsapást. Például az IP osztály egyenlő a PSPACE-szel,, de ha a véletlenszerűséget eltávolítjuk az ellenőrzőből, akkor csak az NP marad, amely nem ismert, de széles körben úgy vélik, hogy lényegesen kisebb osztály.
A komplexitáselmélet egyik központi kérdése, hogy a véletlenszerűség vajon növeli-e a bizonyítási erőt; azaz létezik-e olyan probléma, amelyet egy valószínűségi Turing-gép polinom időben megoldhat, de egy determinisztikus Turing-gép nem? Vagy képesek-e a determinisztikus Turing-gépek hatékonyan szimulálni az összes valószínűségi Turing-gépet legfeljebb polinomiális lassítással? Ismert, hogy P⊆BPP, mivel egy determinisztikus Turing-gép csak egy valószínűségi Turing-gép speciális esete. Azonban bizonytalan, hogy BPP⊆P, ami azt jelenti, hogy BPP=P. Ugyanez a kérdés a polinomiális idő helyett logaritmikus térre (vajon L=BPLP?) még szélesebb körben igaznak tekinthető. Másrészt a véletlenszerűség által az interaktív bizonyítási rendszereknek adott hatalom, valamint az általa létrehozott egyszerű algoritmusok, amelyek olyan nehéz problémákra szolgálnak, mint a polinomiális idejű prímvizsgálat és a logaritmikus térbeli gráfösszefüggőség-vizsgálat, arra utalnak, hogy a véletlenszerűség növelheti a bizonyítási erőt.
Jegyzetek
Fordítás
Források
További információk NIST: probabilistic Turing machine (angol nyelven)
Kategória:Számítógép-tudomány