Сандық есептеулер моделі: ықтималдық Тьюринг машинасы
Probabilistic Turing machine
Теориялық информатикада ықтималдық Тьюринг машинасы – бұл кездейсоқ таңдаулар жасайтын есептеу моделі. Нәтижелері стохастикалық, тоқтауы немесе қабылдауы әртүрлі болуы мүмкін.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Есептеудің математикалық моделі
Mathematical model of computation
Теориялық компьютерлік ғылымда, ықтималдық Тьюринг машинасы – бұл әрбір қадамда қолжетімді өтулердің арасынан белгілі бір ықтималдық тарату бойынша таңдау жасайтын детерминистік емес Тьюринг машинасы. Осының салдарынан, ықтималдық Тьюринг машинасы, детерминистік Тьюринг машинасынан айырмашылығы – стохастикалық нәтижелерге ие болуы мүмкін; яғни, берілген кіріс және командалық күйде оның орындалу уақыты әртүрлі болуы мүмкін, немесе ол тоқтамауы да мүмкін; сонымен қатар, ол бір рет кірісті қабылдап, келесі рет сол кірісті қабылдамауы мүмкін. Өтулер үшін тең ықтималдықтар болған жағдайда, ықтималдық Тьюринг машиналары қосымша "жазу" командасы бар детерминистік Тьюринг машиналары ретінде анықталуы мүмкін, онда жазу мәні Тьюринг машинасының әліпбиі бойынша біркелкі таратылады (әдетте, таспаға "1" немесе "0" жазудың тең ықтималдығы). Тағы бір кең таралған түсіндіру – бұл жай ғана детерминистік Тьюринг машинасы, оған "кездейсоқ таспа" деп аталатын кездейсоқ биттермен толтырылған қосымша таспа қосылады. Кванттық компьютер – бұл есептеудің тағы бір моделі, ол негізінен ықтималдыққа негізделген.
In theoretical computer science, a probabilistic Turing machine is a non deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can—unlike a deterministic Turing Machine—have stochastic results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furthermore, it may accept an input in one execution and reject the same input in another execution. In the case of equal probabilities for the transitions, probabilistic Turing machines can be defined as deterministic Turing machines having an additional "write" instruction where the value of the write is uniformly distributed in the Turing machine's alphabet (generally, an equal likelihood of writing a "1" or a "0" on to the tape). Another common reformulation is simply a deterministic Turing machine with an added tape full of random bits called the "random tape". A quantum computer is another model of computation that is inherently probabilistic.
Сипаттама
Ықтималдық Тьюринг машинасы — бұл нондертерминисттік Тьюринг машинасының бір түрі, онда әр нондертерминисттік қадам "монета лақтыру" сияқты болады, яғни әр қадамда екі мүмкін келесі қадам бар және Тьюринг машинасы қай қадамды жасауды ықтималдық бойынша таңдайды.
A probabilistic Turing machine is a type of nondeterministic Turing machine in which each nondeterministic step is a "coin flip", that is, at each step there are two possible next moves and the Turing machine probabilistically selects which move to take.
Күрделілік сыныптары
Ықтималдық монетаны тастау арқылы енгізілген қателіктің салдарынан, ықтималдық Тьюринг машинасымен бір жолдың қабылдануы әртүрлі жолдармен анықталуы мүмкін. Мұндай анықтамалардың бірі, бірнеше маңызды күрделілік сыныптарын қамтиды, ол қателік ықтималдығына 1/3-ке жол береді. Мысалы, BPP күрделілік класы 1/3 қателік ықтималдығымен полиномдық уақытта ықтималдық Тьюринг машинасымен танылатын тілдер класы ретінде анықталады. Осы қабылдау түсінігін пайдалана отырып анықталатын тағы бір класс – BPL, ол BPP-мен бірдей, бірақ тілдер логарифмдік кеңістікте шешілуі керек деген қосымша шектеуді қояды. Қабылдаудың басқа анықтамаларынан туындайтын күрделілік сыныптарына RP, co RP және ZPP жатады. Егер машина полиномдық уақыттың орнына логарифмдік кеңістікпен шектелсе, RL, co RL және ZPL сияқты күрделілік сыныптары алынады. Екі шектеуді де қолдану арқылы RLP, co RLP, BPLP және ZPLP пайда болады. Ықтималдық есептеу интерактивті дәлелдеу жүйелерінің көптеген сыныптарын анықтау үшін де маңызды, онда барлық мүмкіндігі бар дәлелдеуші машинаны болжаудан және алдаудан қорғау үшін тексеруші машина кездейсоқтыққа тәуелді болады. Мысалы, IP класы PSPACE-қа тең, бірақ егер тексерушіден кездейсоқтық алынса, біз тек NP-мен қаламыз, ол әлі белгісіз, бірақ айтарлықтай кішкентай класс деп есептеледі. Күрделілік теориясының орталық сұрақтарының бірі – кездейсоқтық күш қоса ма? Яғни, ықтималдық Тьюринг машинасымен полиномдық уақытта, бірақ детерминистік Тьюринг машинасымен шешілмейтін проблема бар ма? Немесе детерминистік Тьюринг машиналары барлық ықтималдық Тьюринг машиналарын полиномдық уақыттан аспайтын баяулаумен тиімді түрде симуляциялай ала ма? P ⊆ BPP белгілі, өйткені детерминистік Тьюринг машинасы – ықтималдық Тьюринг машинасының ерекше жағдайы. Алайда, BPP ⊆ P екені белгісіз (бірақ кеңінен күдіктелді), бұл BPP = P дегенді білдіреді. Полиномдық уақыттың орнына логарифмдік кеңістік үшін (L = BPLP?) деген сұраққа көбірек сенім бар. Екінші жағынан, кездейсоқтықтың интерактивті дәлелдеу жүйелеріне беретін күші, сондай-ақ полиномдық уақытта жай сан табу және логарифмдік кеңістікте граф байланыстылығын тексеру сияқты қиын проблемалар үшін жасайтын қарапайым алгоритмдер, кездейсоқтық күш қосуы мүмкін екенін көрсетеді.
As a result of the error introduced by utilizing probabilistic coin tosses, the notion of acceptance of a string by a probabilistic Turing machine can be defined in different ways. One such notion that includes several important complexity classes is allowing for an error probability of 1/3. For instance, the complexity class BPP is defined as the class of languages recognized by a probabilistic Turing machine in polynomial time with an error probability of 1/3. Another class defined using this notion of acceptance is BPL, which is the same as BPP but places the additional restriction that languages must be solvable in logarithmic space. Complexity classes arising from other definitions of acceptance include RP, co RP, and ZPP. If the machine is restricted to logarithmic space instead of polynomial time, the analogous RL, co RL, and ZPL complexity classes are obtained. By enforcing both restrictions, RLP, co RLP, BPLP, and ZPLP are yielded. Probabilistic computation is also critical for the definition of most classes of interactive proof systems, in which the verifier machine depends on randomness to avoid being predicted and tricked by the all powerful prover machine. For example, the class IP equals PSPACE, but if randomness is removed from the verifier, we are left with only NP, which is not known but widely believed to be a considerably smaller class. One of the central questions of complexity theory is whether randomness adds power; that is, is there a problem that can be solved in polynomial time by a probabilistic Turing machine but not a deterministic Turing machine? Or can deterministic Turing machines efficiently simulate all probabilistic Turing machines with at most a polynomial slowdown? It is known that P ⊆ BPP, since a deterministic Turing machine is just a special case of a probabilistic Turing machine. However, it is uncertain whether (but widely suspected that) BPP ⊆ P, implying that BPP = P. The same question for log space instead of polynomial time (does L = BPLP?) is even more widely believed to be true. On the other hand, the power randomness gives to interactive proof systems, as well as the simple algorithms it creates for difficult problems such as polynomial time primality testing and log space graph connectedness testing, suggests that randomness may add power.