Pravděpodobný Turingův stroj - Probabilistic Turing machine

v teoretická informatika, a pravděpodobnostní Turingův stroj je nedeterministický Turingův stroj který podle některých volí mezi dostupnými přechody v každém bodě rozdělení pravděpodobnosti. V důsledku toho může pravděpodobnostní Turingův stroj - na rozdíl od deterministického Turingova stroje - mít stochastický Výsledek; to znamená, že na daném vstupním a instrukčním stavovém stroji může mít různé doby chodu nebo se nemusí vůbec zastavit; dále může přijmout vstup v jednom provedení a odmítnout stejný vstup v jiném provedení.

V případě stejné pravděpodobnosti přechodů lze pravděpodobnostní Turingovy stroje definovat jako deterministické Turingovy stroje s další instrukcí "write", kde hodnota zápisu je rovnoměrně rozloženo v abecedě Turingova stroje (obecně stejná pravděpodobnost zápisu na pásku „1“ nebo „0“). Další běžná formulace je jednoduše a deterministický Turingův stroj s přidanou páskou plnou náhodných bitů zvanou „náhodná páska“.

A kvantový počítač je další model výpočtu, který je ze své podstaty pravděpodobnostní.

Popis

Pravděpodobný Turingův stroj je typ nedeterministický Turingův stroj ve kterém je každý nedeterministický krok „coin-flip“, to znamená, že v každém kroku jsou dva možné další tahy a Turingův stroj pravděpodobnostně vybírá, který tah má provést.^[1]

Formální definice

Pravděpodobnostní Turingův stroj lze formálně definovat jako sedmou n-tici ${ displaystyle M = (Q, Sigma, Gamma, q_ {0}, A, delta _ {1}, delta _ {2})}$ , kde

${ displaystyle Q}$ je konečná množina států
${ displaystyle Sigma}$ je vstupní abeceda
${ displaystyle Gamma}$ je pásková abeceda, která obsahuje prázdný symbol ${ displaystyle sqcup}$
${ displaystyle q_ {0} v Q}$ je počáteční stav
${ displaystyle A subseteq Q}$ je množina přijímajících (konečných) stavů
${ displaystyle delta _ {1}: Q krát gama až Q krát gama krát {L, R }}$ je první pravděpodobnostní přechodová funkce. ${ displaystyle L}$ je pohyb o jednu buňku vlevo na pásku Turingova stroje a ${ displaystyle R}$ je pohyb o jednu buňku doprava.
${ displaystyle delta _ {2}: Q krát gama až Q krát gama krát {L, R }}$ je druhá pravděpodobnostní přechodová funkce.

V každém kroku Turingův stroj pravděpodobnostně použije buď přechodovou funkci ${ displaystyle delta _ {1}}$ nebo přechodová funkce ${ displaystyle delta _ {2}}$ .^[2] Tato volba se provádí nezávisle na všech předchozích možnostech. Tímto způsobem se proces výběru přechodové funkce v každém kroku výpočtu podobá převrácení mince.

Pravděpodobnostní výběr přechodové funkce v každém kroku zavádí do Turingova stroje chybu; to znamená, že řetězce, které má Turingův stroj přijmout, mohou být v některých případech odmítnuty a řetězce, které má Turingův stroj zamítnout, mohou být v některých případech přijaty. Abychom tomu vyhověli, jazyk ${ displaystyle L}$ se říká, že je uznáván s pravděpodobností chyby ${ displaystyle epsilon}$ pravděpodobným Turingovým strojem ${ displaystyle M}$ li:

řetězec ${ displaystyle w}$ v ${ displaystyle L}$ to naznačuje ${ displaystyle { text {Pr}} [M { text {přijímá}} w] geq 1- epsilon}$
řetězec ${ displaystyle w}$ ne v ${ displaystyle L}$ to naznačuje ${ displaystyle { text {Pr}} [M { text {odmítne}} w] geq 1- epsilon}$

Třídy složitosti

Nevyřešený problém v informatice:

Je P = BPP ?

(více nevyřešených problémů v informatice)

V důsledku chyby zavedené využitím pravděpodobnostních hodů mincí lze pojem přijetí řetězce pravděpodobnostním Turingovým strojem definovat různými způsoby. Jedna taková představa, která zahrnuje několik důležitých tříd složitosti, umožňuje pravděpodobnost chyby 1/3. Například třída složitosti BPP je definována jako třída jazyků rozpoznaných pravděpodobným Turingovým strojem v polynomiální čas s pravděpodobností chyby 1/3. Další třída definovaná pomocí tohoto pojmu přijetí je BPL, což je stejné jako BPP ale klade další omezení, že jazyky musí být řešitelné logaritmický prostor.

Třídy složitosti vyplývající z jiných definic přijetí zahrnují RP, co-RP, a ZPP. Pokud je stroj omezen na logaritmický prostor místo polynomiálního času, analogický RL, co-RL, a ZPL jsou získány třídy složitosti. Prosazováním obou omezení RLP, co-RLP, BPLP, a ZPLP jsou získány.

Pravděpodobnostní výpočet je také kritický pro definici většiny tříd třídy interaktivní kontrolní systémy, ve kterém ověřovací stroj závisí na náhodnosti, aby se vyhnul předvídání a podvádění všemocným proverovacím strojem. Například třída IP rovná se PSPACE, ale pokud je náhodnost odstraněna z ověřovatele, zbývá nám pouze NP, což není známo, ale obecně se předpokládá, že jde o podstatně menší třídu.

Jednou z ústředních otázek teorie složitosti je, zda náhodnost dodává sílu; to znamená, existuje problém, který lze vyřešit v polynomiálním čase pravděpodobnostním Turingovým strojem, ale nikoli deterministický Turingův stroj? Nebo mohou deterministické Turingovy stroje efektivně simulovat všechny pravděpodobnostní Turingovy stroje s maximálně polynomiálním zpomalením? Je známo že P ${ displaystyle subseteq}$ BPP, protože deterministický Turingův stroj je jen zvláštním případem pravděpodobnostního Turingova stroje. Není však jisté, zda (ale obecně existuje podezření) BPP ${ displaystyle subseteq}$ Pz čehož vyplývá, že BPP = P. Stejná otázka pro prostor protokolu namísto polynomiálního času (dělá L = BPLP?) se ještě více věří, že je to pravda. Na druhou stranu mocná náhodnost dává interaktivním důkazovým systémům, stejně jako jednoduché algoritmy, které vytváří pro obtížné problémy, jako je testování primality v polynomiálním čase a testování připojení log-prostoru, naznačuje, že náhodnost může přidat sílu.

Viz také

Randomizovaný algoritmus

Poznámky

^ Sipser, Michael (2006). Úvod do teorie výpočtu (2. vyd.). USA: Thomson Course Technology. str. 368. ISBN 978-0-534-95097-2.
^ Arora, Sanjeev; Barak, Boaz (2016). Výpočetní složitost: moderní přístup. Cambridge University Press. str. 125. ISBN 978-0-521-42426-4.

Reference

Arora, Sanjeev; Barak, Boaz (2016). Výpočetní složitost: moderní přístup. Cambridge University Press. str. 123–142. ISBN 978-0-521-42426-4.
Sipser, Michael (2006). Úvod do teorie výpočtu (2. vyd.). USA: Thomson Course Technology. 368–380. ISBN 978-0-534-95097-2.

externí odkazy

Web NIST o pravděpodobnostních Turingových strojích

[1] Sipser, Michael (2006). Úvod do teorie výpočtu (2. vyd.). USA: Thomson Course Technology. str. 368. ISBN 978-0-534-95097-2.

[2] Arora, Sanjeev; Barak, Boaz (2016). Výpočetní složitost: moderní přístup. Cambridge University Press. str. 125. ISBN 978-0-521-42426-4.

[1]

[2]