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

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

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

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

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

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

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

Дефиниција[уреди | уреди извор]

Недетерминистичка Тјурингова машина може формално да се дефинише шесторком $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$ , где су:

$Q$ коначни скуп стања,
$\Sigma$ коначни скуп симбола (азбука траке),
$\iota \in Q$ почетно стање,
$\sqcup \in \Sigma$ симбол „празан“ (бланко),
$A\subseteq Q$ скуп прихватљивих стања,
$\delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,R\}\right)$ релација над стањима и симболима – преносна релација. $L$ померај улево и $R$ померај удесно.

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

Одлука више правила[уреди | уреди извор]

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

Еквиваленција са ДТМ[уреди | уреди извор]

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

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

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

Ограничен не-детерминизам[уреди | уреди извор]

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

Поређење са квантним компјутерима[уреди | уреди извор]

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

Референце[уреди | уреди извор]

^ Elements of the Theory of Computation, by Harry R. Lewis and Christos H. Papadimitriou, Prentice-Hall, Englewood Cliffs, New Jersey. 1981. ISBN 978-0-13-273417-2. стр. 206-211.
^ The Orion Quantum Computer Anti-Hype FAQ, Scott Aaronson.
^ Tušarová, Tereza (2004). „Quantum complexity classes”. arXiv:cs/0409051 .

Спољашње везе[уреди | уреди извор]

[1] Elements of the Theory of Computation, by Harry R. Lewis and Christos H. Papadimitriou, Prentice-Hall, Englewood Cliffs, New Jersey. 1981. ISBN 978-0-13-273417-2. стр. 206-211.

[2] The Orion Quantum Computer Anti-Hype FAQ, Scott Aaronson.

[3] Tušarová, Tereza (2004). „Quantum complexity classes”. arXiv:cs/0409051 .

[1]

[2]

[3]