Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Теориялық есептеу моделі
Theoretical model of computation
Теориялық компьютерлік ғылымда, нондетерминистік Тьюринг машинасы (НТМ) – кейбір жағдайларда басқару ережелері бірнеше мүмкін әрекеттерді белгілейтін есептеудің теориялық моделі. Яғни, НТМ-нің келесі күйі оның әрекетімен және қазіргі оқып отырған символмен толыққанды анықталмайды, бұл детерминистік Тьюринг машинасынан өзгеше. НТМ-дер кейде компьютерлердің қабілеттерін және шектерін зерттеу үшін ой-эксперименттерде қолданылады. Теориялық компьютерлік ғылымдағы маңызды ашық мәселелердің бірі – P және NP мәселесі, ол (басқа да теңдестірілген тұжырымдамалармен қатар) детерминистік компьютермен нондетерминистік есептеуді модельдеудің қаншалықты қиын екеніне қатысты сұрақтарды қамтиды.
In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is not completely determined by its action and the current symbol it sees, unlike a deterministic Turing machine. NTMs are sometimes used in thought experiments to examine the abilities and limits of computers. One of the most important open problems in theoretical computer science is the P versus NP problem, which (among other equivalent formulations) concerns the question of how difficult it is to simulate nondeterministic computation with a deterministic computer.
Өмірбаян
Негізінде, Тьюринг машинасы – шексіз таспаға бір-бірлеп символдарды оқитын және жазатын қарапайым компьютер деп есептеледі, ол қатаң ережелер жиынына сәйкес жұмыс істейді. Ол өзінің ішкі жағдайына және қазіргі уақытта қандай символды көруіне байланысты келесі қандай іс-әрекетті атқару керектігін анықтайды. Тьюринг машинасының ережелерінің бірі мынандай болуы мүмкін: "Егер сіз 2-ші күйде болсаңыз және 'А' символын көрсеңіз, оны 'В' символына өзгертіңіз, солға жылжыңыз және 3-ші күйге өтіңіз".
In essence, a Turing machine is imagined to be a simple computer that reads and writes symbols one at a time on an endless tape by strictly following a set of rules. It determines what action it should perform next according to its internal state and what symbol it currently sees. An example of one of a Turing Machine's rules might thus be: "If you are in state 2 and you see an 'A', then change it to 'B', move left, and switch to state 3."
Бірнеше ережелерді шешу
ҰМТ осы әрекеттердің қайсысын "біледі"? Мұны қарастырудың екі жолы бар. Бірі – машинаны "мүмкіндігінше ең сәтті болжайтын" деп айтуға болады; егер мұндай ауысу болса, ол әрқашан ақырында қабылдау күйіне жететін ауысуды таңдайды. Екіншісі – машинаның көптеген көшірмелеріне "бөлінуін" көзге елестетуге болады, олардың әрқайсысы мүмкін болатын ауысулардың біреуін орындайды. ДТМ-нің бір ғана "есептеу жолы" болса, ҰМТ-нің "есептеу ағашы" болады. Егер ағаштың кем дегенде бір тармағы "қабылдау" шартымен тоқтаса, ҰМТ кірісті қабылдайды.
How does the NTM "know" which of these actions it should take? There are two ways of looking at it. One is to say that the machine is the "luckiest possible guesser"; it always picks a transition that eventually leads to an accepting state, if there is such a transition. The other is to imagine that the machine "branches" into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single "computation path" that it follows, an NTM has a "computation tree". If at least one branch of the tree halts with an "accept" condition, the NTM accepts the input.
ДТМ-мен есептеулік баламалық
DTM арқылы шешілетін кез келген есептеу мәселесі NTM арқылы да шешіледі, және керісінше де дұрыс. Дегенмен, көбінесе уақыт күрделілігінің әртүрлі болуы мүмкін деп саналады.
Any computational problem that can be solved by a DTM can also be solved by a NTM, and vice versa. However, it is believed that in general the time complexity may not be the same.
DTM NTM-нің ерекше жағдайы ретінде
NTM-дер DTM-дердің ерекше жағдайларын қамтиды, сондықтан DTM-мен жүзеге асырыла алатын кез келген есептеуді тиектес NTM-мен де жүзеге асыруға болады.
NTMs include DTMs as special cases, so every computation that can be carried out by a DTM can also be carried out by the equivalent NTM.
NTM-нің DTM-ны модельдеуі
NTM-дер DTM-ге қарағанда қуаттырақ көрінеді, себебі олар бірдей бастапқы конфигурациядан туындайтын есептеулердің ағаштарын құруға мүмкіндік береді, және ағаштағы кез келген тармақ тізбекті қабылдаса, тізбек қабылданған болып есептеледі. Алайда, NTM-дерді DTM-дермен модельдеуге болады, және бұл бірнеше тәсілмен іске асырылуы мүмкін.
It might seem that NTMs are more powerful than DTMs, since they can allow trees of possible computations arising from the same initial configuration, accepting a string if any one branch in the tree accepts it. However, it is possible to simulate NTMs with DTMs, and in fact this can be done in more than one way.
Конфигурация күйлерінің көптігі
Бір тәсіл – NTM-нің көптеген конфигурацияларын көрсететін конфигурациялары бар DTM-ді пайдалану. DTM-нің жұмысы осы конфигурациялардың әрқайсысын кезекпен аралаудан, әрбір аралауда бір қадам жасаудан және ауысу қатынасы бірнеше мүмкіндікті анықтағанда жаңа конфигурацияларды жасаудан тұрады.
One approach is to use a DTM of which the configurations represent multiple configurations of the NTM, and the DTM's operation consists of visiting each of them in turn, executing a single step at each visit, and spawning new configurations whenever the transition relation defines multiple continuations.
Таспалардың көптігі
Басқа бір құрылым NTM-дерді 3 таспалы DTM-дер арқылы модельдейді, олардың бірінші таспасы әрқашан бастапқы кіріс жолын сақтайды, екіншісі NTM-нің нақты есептеуін модельдеу үшін пайдаланылады, ал үшіншісі NTM-нің есептеу ағашындағы жолды шифрлейді. 3 таспалы DTM-дерді әдеттегі бір таспалы DTM-мен оңай модельдеуге болады.
Another construction simulates NTMs with 3 tape DTMs, of which the first tape always holds the original input string, the second is used to simulate a particular computation of the NTM, and the third encodes a path in the NTM's computation tree. The 3 tape DTMs are easily simulated with a normal single tape DTM.
Уақыт күрделілігі және P мен NP
Екінші құрылымда, құрылған DTM NTM есептеу ағашын ендік бойынша тиімді іздейді, NTM-нің барлық мүмкін есептеулерін ұзындығының өсу ретімен қарастырып, қабылдаушы есептеуді тапқанға дейін жалғастырады. Сондықтан, ДТМ-ның қабылдау есептеуінің ұзындығы, әдетте, НТМ-ның ең қысқа қабылдау есептеуінің ұзындығына экспоненциалды түрде байланысты болады. Бұл NTM-ді DTM арқылы модельдеудің жалпы қасиеті деп саналады. Компьютерлік ғылымдағы ең белгілі шешілмеген мәселе – P = NP мәселесі, осы мәселенің бір жағдайына қатысты: NTM арқылы көпшелік уақытта шешілетін кез келген мәселе, міндетті түрде DTM арқылы да көпшелік уақытта шешіледі ме, әлде жоқ па?
In the second construction, the constructed DTM effectively performs a breadth first search of the NTM's computation tree, visiting all possible computations of the NTM in order of increasing length until it finds an accepting one. Therefore, the length of an accepting computation of the DTM is, in general, exponential in the length of the shortest accepting computation of the NTM. This is believed to be a general property of simulations of NTMs by DTMs. The P = NP problem, the most famous unresolved question in computer science, concerns one case of this issue: whether or not every problem solvable by a NTM in polynomial time is necessarily also solvable by a DTM in polynomial time.
Шектелген нондертимеризм
NTM шектелген нондертиминизм қасиетіне ие. Яғни, егер NTM белгілі бір кіріс таспасы T үшін әрқашан тоқтаса, онда ол шектелген сандағы қадамдарда тоқтайды, демек, оның мүмкін болатын конфигурациялар саны да шектелген болады.
An NTM has the property of bounded nondeterminism. That is, if an NTM always halts on a given input tape T then it halts in a bounded number of steps, and therefore can only have a bounded number of possible configurations.
Кванттық компьютерлермен салыстыру
Кванттық компьютерлер дәстүрлі биттерге қарағанда, күйлердің суперпозициясында бола алатын кванттық биттерді қолданатындықтан, кейде кванттық компьютерлер NTM (детерминистік емес Тьюринг машинасы) деп жаңылысады. Дегенмен, сарапшылар кванттық компьютерлердің мүмкіндіктері, іс жүзінде, NTM-мен салыстыруға келмейтініне сенімді (бірақ бұл әлі дәлелденбеген). Яғни, NTM тиімді шеше алатын, ал кванттық компьютер шеше алмайтын, сондай-ақ керісінше жағдайлар болуы мүмкін. Атап айтқанда, NP-толық мәселелер NTM арқылы шешілуі мүмкін, бірақ кванттық компьютерлер үшін полиномиалдық уақытта шешілмейді. Түсіндіретін болсақ, кванттық компьютер бір уақытта барлық мүмкін есептеу тармақтарын орындағанға сәйкес келетін суперпозициялық күйде болуы мүмкін (бұл NTM-ге ұқсас), бірақ соңғы өлшеу кванттық компьютерді кездейсоқ таңдалған бір тармаққа дейін қысқартады. Бұл тармақ, әдетте, ізделіп отырған шешімді көрсетпейді, NTM-нен өзгеше, ол экспоненциалды түрде көптеген тармақтардың ішінде дұрыс шешімді таңдауға құқылы.
Because quantum computers use quantum bits, which can be in superpositions of states, rather than conventional bits, there is sometimes a misconception that quantum computers are NTMs. However, it is believed by experts (but has not been proven) that the power of quantum computers is, in fact, incomparable to that of NTMs; that is, problems likely exist that an NTM could efficiently solve that a quantum computer cannot and vice versa. In particular, it is likely that NP complete problems are solvable by NTMs but not by quantum computers in polynomial time. Intuitively speaking, while a quantum computer can indeed be in a superposition state corresponding to all possible computational branches having been executed at the same time (similar to an NTM), the final measurement will collapse the quantum computer into a randomly selected branch. This branch then does not, in general, represent the sought for solution, unlike the NTM, which is allowed to pick the right solution among the exponentially many branches.