Back

ⓘ Недетерминистичка Тјурингова машина




                                     

ⓘ Недетерминистичка Тјурингова машина

У теорији рачунарства, Тјурингова машина је теоретска машина која се користи у мисаоним експериментима да би се испитале могућности и ограничења рачунара.

У суштини, Тјурингова машина је једноставан рачунар који чита и уписује појединачне симболе на бесконачној траци, стриктно поштујући предефинисан скуп правила. Она одређује коју акцију ће предузети на основу свог тренутног стања и симбола који учита. Пример једног од правила Тјурингове машине је: "Ако си у стању 2 и учиташ симбол А, промени га у Б и помери траку лево".

Код детерминистичке Тјурингове машине, скуп правила једнозначно одређује њену акцију у свакој ситуацији. Недетерминистичка Тјурингова машина НТМ са друге стране, може да има скуп правила која омогућавају више различитих акција у датој ситуацији. На пример, недетерминистичка Тјурингова машина може у свом скупу правила истовремено да има правило: "Ако си у стању 2 и учиташ симбол А, промени га у Б и помери траку лево" и правило: "Ако си у стању 2 и учиташ симбол А, промени га у C и помери траку десно".

Детерминистичка Тјурингова машина ДТМ има функцију преноса која на основу задатог стања машине и учитаног симбола одређује следеће три ствари:

  • следеће стање машине.
  • симбол који треба да буде уписан на траку,
  • смер померања траке,

На пример, за учитано X са траке у стању 3, ДТМ може да упише Y, помери траку десно и промени стање у 5. Недетерминистичка Тјурингова машина НТМ се од детерминистичке разликује у томе што њене акције нису једнозначно одређене њеним стањем и учитаним симболом. Многе различите акције могу да буду изведене са истом комбинацијом стања и учитаних симбола. На пример: учитано X са траке у стању 3 може да дозволи да НТМ упише Y, помери траку десно и пређе у стање 5, или да упише X, помери траку лево и остане у стању 3.

                                     

1. Дефиниција

Недетерминистичка Тјурингова машина може формално да се дефинише шесторком M = Q, Σ, ι, ⊔, A, δ {\displaystyle M=Q,\Sigma,\iota,\sqcup,A,\delta}, где су:

  • A ⊆ Q {\displaystyle A\subseteq Q} скуп прихватљивих стања,
  • ι ∈ Q {\displaystyle \iota \in Q} почетно стање,
  • Σ {\displaystyle \Sigma } коначни скуп симбола азбука траке,
  • Q {\displaystyle Q} коначни скуп стања,
  • ⊔ ∈ Σ {\displaystyle \sqcup \in \Sigma } симбол "празан" бланко,
  • δ ⊆ Q ∖ A × Σ × Q × Σ × { L, R } {\displaystyle \delta \subseteq \leftQ\backslash A\times \Sigma \right\times \leftQ\times \Sigma \times \{L,R\}\right} релација над стањима и симболима – преносна релација. L {\displaystyle L} померај улево и R {\displaystyle R} померај удесно.

Разлика од стандардне детерминистичке Тјурингове машине је што су код њих прелазне релације функције прелаза. Конфигурације и релација приноса на конфигурацијама, која описује могуће акције Тјурингове машине за било који могући дати садржај траке, су исте као и за стандардне Тјурингове машине, осим што релација приноса није више са једном вредношћу. Израз за прихватање стринга је непромењен: недетерминистичка Тјурингова машина прихвата стринг ако, кад је машина покренута са конфигурацијом у којој је глава траке на првом карактеру стринга ако га има, и трака је празна иначе, бар један од могућих прорачуна машине из те конфигурације доводи машину у стање у A {\displaystyle A}.

                                     

2. Одлука више правила

Како НТМ "зна" коју од ових акција да преузме? Постоје два погледа на ово. Један је да кажемо да је машина "најсрећнији могући погађач" ; увек бира прелаз стања који ће довести до прихватљивог стања, ако таква промена постоји. Други поглед је да замислимо да се машина "грана" у пуно копија, од којих свака прати један од могућих прелаза стања. Док ДТМ има јединствену "путању прорачуна" коју прати, НТМ има "дрво прорачуна". Ако се бар једна грана дрвета заустави са условом прихватања, кажемо да НТМ прихвата улаз.

                                     

3. Еквиваленција са ДТМ

Конкретно, недетерминистичке Тјурингове машине су еквивалентне са детерминистичким Тјуринговим машинама. Еквиваленција се односи она то шта се може обрадити наспрам тога колико брзо се то може обрадити. НТМ укључују ДТМ као специјалне случајеве, па је јасно да ДТМ нису моћније. Може нам се учинити да су НТМ моћније од ДТМ, с обзиром на то да омогућавају стабла могућих прорачуна који проистичу из исте почетне конфигурације, прихватајући стринг ако га било која грана у стаблу прихвата.

Међутим, могуће је симулирати НТМ уз помоћ ДТМ: Један начин је да коришћењем ДТМ чије конфигурације представљају више конфигурација НТМ, при чему се операција ДТМ састоји у наизменичном посећивању сваке од њих, извршавајући један корак при свакој посети и дајући нове конфигурације кад год релација прелаза стања дефинише више континуалности. Другачија конструкција симулира НТМ са ДТ машином са 3 траке, од којих прва трака увек чува оригинални улазни стринг, друг се користи да симулира одређен прорачун НТМ, и трећа кодира путању стаблу обраде НТ машине. ДТМ са три траке се лако слимулирају уз помоћ нормалне ДТМ са једном траком.

Код овакве конструкције, резултујућа ДТМ ефективно обавља стабла обраде НТ машине, посећујући све могуће прорачуне НТ машине по растућој дужини док не нађе онај који је прихватљив. Стога, дужина прихватљивог прорачуна ДТ машине је, уопштено, експонент дужине најкраћег прихватљивог прорачуна НТ машине. Ово се сматра као уопштено својство симулација НТ машина ДТ машинама; Најпознатије нерешено питање у рачунарској науци, проблем P=NP, је везан за ово.



                                     

4. Ограничен не-детерминизам

НТМ има својство ограниченог не-детерминизма, на пример, ако се НТМ увек зауставља на датој улазној траци 7 онда се зауставља у ограниченом броју корака, и стога може имати само ограничен број могућих конфигурација.

                                     

5. Поређење са квантним компјутерима

Уобичајена је грешка да се сматра да су квантни компјутери исто што и НТМ. Верује се, али није доказано да моћ квантних компјутера не може да се пореди са моћи НТ машина, тј, вероватно постоје проблеми које НТМ могу ефикасно да реше, док квантни компјутер не може. Могући пример проблема који су решиви НТ машином, а нису решиви квантним компјутером у полиномијалном времену су NP-комплетни проблеми.

                                     

6. Спољашње везе

  • C++ Simulator of a Nondeterministic Multitape Turing Machine download link from sourceforge.net
  • C++ Simulator of a Nondeterministic Multitape Turing Machine free software.
                                     
  • вишеканална Тјурингова машина машине са улазом и излазом, и недетерминистичка Тјурингова машина НДТМ за разлику од детерминистичке Тјурингове машине ДТМ
  • Линеарно - ограничени аутомат је недетерминистичка Тјурингова машина са ограничењем. Поседује траку сачињену од ћелија које могу да садрже симболе коначне
  • ограниченим недетерминистичким Тјуринговим машинама које се називају још и линеарно ограниченим аутоматима. То је недетерминистичка Тјурингова машина са траком
  • израчунљивости, машина која увек стаје или одлучивач или тотална Тјурингова машина је Тјурингова машина која стаје за сваки улаз. Како увек стаје, машина је у стању
  • за који проблем треба да буде одлучен Ово значи да постоји недетерминистичка машина која за задати улаз дужине n има време извршења у оквиру O f n
  • детерминистичка Тјурингова машина али многе класе сложености су засноване на недетерминистичким Тјуринговим машинама логички склоп, квантна Тјурингова машина монотон
  • речима, ако недетерминистичка Тјурингова машина може да реши проблем у меморијском простору f n обична, детерминистичка Тјурингова машина може да реши
  • детерминистичког модела Тјурингове машине постоје ограничења и изузеци са овим ресурсом. На пример, уколико се користи недетерминистичка Тјурингова машина користи
  • путања која повезује све градове, укупне дужине мање од k. Недетерминистичка Тјурингова машина може да пронађе такву путању на следећи начин: У сваком граду
  • помоћу недетерминистичке Тјурингове машине Класа сложености NSPACE f n је скуп проблема одлучивања који могу да буду решени помоћу недетерминистичке Тјурингове
  • који су дали Гери и Џонсон. САТ проблем је у класи НП јер недетерминистичка Тјурингова машина у полиномијалном времену може да погоди доделу истинитосних