Probableca maŝino de Turing

En komputebleca teorio, probableca maŝino de Turing estas speco de maŝino de Turing kiu hazarde elektas inter la haveblaj trairoj je ĉiu punkto kun egala probablo.

Ekvivalente, ĝi povas esti difinita kiel determinisma maŝino de Turing havanta aldonan skriban komandon ĉe kiu la valoro skribita estas unuforme distribuita en la maŝina alfabeto (ĝenerale, egala verŝajneco de skribo de '1' aŭ '0' sur la bendo). Alia komuna varianto estas simple determinisma maŝino de Turing kun aldona bendo plena de hazardaj bitoj, nomata kiel la hazarda bendo.

Sekve de tio, probableca maŝino de Turing povas (malsimile al determinisma maŝino de Turing) havi stokastajn rezultojn; sur donita enigo kaj komanda stata maŝino, ĝi povas havi malsamajn rultempojn, aŭ ĝi povas ne halti ajn; plui, ĝi povas akcepti enigon en unu rulo kaj malakcepti la saman enigon en la alia rulo.

Pro tio la nocio de akcepto de linio per probableca maŝino de Turing povas esti difinita en malsamaj manieroj. Estas diversaj polinomo-tempaj hazardigitaj komplikecaj klasoj kiuj rezultiĝas de malsamaj difinoj de akcepto - RP, Co-RP, BPP kaj ZPP. Se oni limigas la maŝinon al logaritma spaco anstataŭ polinoma tempo, rezultiĝas la analogaj RL, Co-RL, BPL kaj ZPL. Se fari ambaŭ limigojn, rezultiĝas klasoj RLP, Co-RLP, BPLP, kaj ZPLP.

Probableca kalkulado estas ankaŭ kritika por la difino de plejparto klasoj de interagaj pruvaj sistemoj, en kiu la kontrolila maŝino dependas sur hazardo por eviti estado aŭgurita kaj artifikita per la ĉiopova provata maŝino. Ekzemple, la klaso IP egalas al PSPACO, sed se hazardo estas forprenita de la kontrolilo, rezultiĝas nur NP, kiu estas ne sciata sed larĝe kredita al esti konsiderinde pli malgranda klaso.

Unu el la centraj demandoj de komplikteorio estas ĉu hazardo aldonas povon; tio estas, ĉu estas problemo kiu povas esti solvita en polinoma tempo per probableca maŝino de Turing sed ne per determinisma maŝino de Turing? Aŭ ĉu povas determinismaj maŝinoj de Turing kompetente simuli ĉiujn probablecajn maŝinojn de Turing kun maksimume polinoma malplirapidiĝo? Nun estas larĝe kredite de esploristoj ke la lasta estas la okazo, kiu devus enhavi ke P = BPP. La sama demando por logaritma spaco anstataŭ polinoma tempo (ĉu L = BPLP?) estas eĉ pli larĝe kredita al esti vera. Aliflanke, la pova hazardo donas al interagaj pruvaj sistemoj kaj la simplaj algoritmoj ĝi kreas por malfacila problemoj kiel polinomo-tempa primeco-testo kaj logaritmo-spaca grafea konekteca provo sugestas ke hazardo povas aldoni povon.

Vidu ankaŭ

• Hazardigita algoritmo
• Kvantuma komputilo estas alia modelo de kalkulado kiu estas imanente probableca.
• Nedeterminisma maŝino de Turing

Eksteraj ligiloj

• Retejo de NIST pri probablecaj maŝinoj de Turing