Vikipedio:Projekto matematiko/Probableca maŝino de Turing

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Probableca maŝino de Turing
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En komputebleca teorio, probableca maŝino de Turing estas ne-(determinisma, determina) Maŝino de Turing kiu hazarde elektas inter la havebla (trairoj, trairas) je ĉiu punkto kun egala probablo.

Ekvivalente, ĝi povas esti difinita kiel (determinisma, determina) Maŝino de Turing havanta aldona "skribi" komando kie la valoro de la skribi estas unuforme distribuita en la Turing-a (Maŝina, Aparata) alfabeto (ĝenerale, egala verŝajneco de skribanta '1' aŭ '0' sur al la bendo.) Alia komuna _reformulation_ estas simple (determinisma, determina) Maŝino de Turing kun adiciis bendo plena de hazarda (bitoj, bitas, enbuŝaĵoj, enbuŝaĵas, malmultoj, malmultas) (nomita, vokis) la hazarda bendo.

Sekve de tio, probableca maŝino de Turing povas (malverŝajne (determinisma, determina) Turing-a Maŝino) havi stokastaj rezultoj; sur donita (enigo, enigi) kaj komando (ŝtato, stato, stati) maŝino, ĝi (majo, povas) havi malsama kuri (tempoj, tempas), aŭ ĝi (majo, povas) ne halti ajn; plui, ĝi (majo, povas) akcepti (enigo, enigi) en unu ekzekuto kaj malakcepti la sama (enigo, enigi) en alia ekzekuto.

Pro tio la nocio de (akcepto, konsento) de linio per probableca maŝino de Turing povas esti difinita en malsama (vojoj, vojas). Diversa polinomo-tempo hazardigis kompleksecaj klasoj (tiu, ke, kiu) rezulto de malsama (difinoj, difinas) de (akcepto, konsento) inkluzivi _RP_, Co-_RP_, BPP kaj ZPP. Se ni limigi la maŝino al logaritma spaco anstataŭ polinoma tempo, ni ricevi la analoga _RL_, Co-_RL_, _BPL_, kaj ZPL. Se ni _enforce_ ambaŭ limigoj, ni preni _RLP_, Co-_RPL_, _BPLP_, kaj _ZPLP_.

Probableca kalkulado estas ankaŭ kritika por la difino de plej klasoj de interagaj pruvaj sistemoj, en kiu la kontrolila maŝino dependas sur hazardo al eviti estante aŭgurita kaj artifikis per la ĉiopova _prover_ maŝino. Ekzemple, la klaso _IP_ egalas _PSPACE_, sed se hazardo estas forprenita de la kontrolilo, ni estas (maldekstre, restita) kun nur (Np, NP), kiu estas ne sciata sed larĝe kredis al esti konsiderinde (pli minuskla, pli malgranda) klaso.

Unu de la centra (demandoj, demandas) de komplikteorio estas ĉu hazardo adicias povo; tio estas, estas tie problemo kiu povas esti solvita en polinoma tempo per probableca maŝino de Turing sed ne (determinisma, determina) Maŝino de Turing? Aŭ povas (determinisma, determina) Turingaj aŭtomatoj kompetente simuli ĉiuj probablecaj Turingaj aŭtomatoj kun maksimume polinomo _slowdown_? Ĝi estas nun larĝe kredis per (esploristoj, esploristas) (tiu, ke, kiu) la lasta estas la (kesto, okazo), kiu devus enhavi P = BPP. La sama demando por loga spaco anstataŭ polinoma tempo (faras L = _BPLP_?) estas (eĉ, ebena, para) pli larĝe kredita al esti vera. Aliflanke, la pova hazardo donas al interagaj pruvaj sistemoj kaj la simpla (algoritmoj, algoritmas) ĝi kreas por malfacila (problemoj, problemas) kiel polinomo-tempo (primeco, plejparte) (testante, testado) kaj logo-spaco (grafikaĵo, grafeo) konekteco (testante, testado) (pensigi, sugesti) (tiu, ke, kiu) hazardo (majo, povas) adicii povo.

Kvantuma komputilo estas alia modelo de kalkulada tio estas imanente probableca.