Izvorni kod stranice Nedeterministička Turingova mašina

U teoriji računarstva, [[Tjuringova mašina (Apstraktna mašina)|Tjuringova mašina]] je teoretska mašina koja se koristi u misaonim eksperimentima da bi se ispitale mogućnosti i ograničenja računara. 

U suštini, Turingova mašina je jednostavan računar koji čita i upisuje pojedinačne simbole na beskonačnoj traci, striktno poštujući predefinisan skup pravila. Ona određuje koju akciju će preduzeti na osnovu svog trenutnog stanja i simbola koji učita. Primer jednog od pravila Turingove mašine je: „ Ako si u stanju 2 i učitaš simbol A, promeni ga u B i pomeri traku levo“.

Kod '''determinističke Turingove mašine''', skup pravila jednoznačno određuje njenu akciju u svakoj situaciji. '''Nedeterministička Turingova mašina''' ('''NTM''') sa druge strane, ''može da ima skup pravila koja omogućavaju više različitih akcija u datoj situaciji''. Na primer, nedeterministička Turingova mašina može u svom skupu pravila istovremeno da ima pravilo: „ Ako si u stanju 2 i učitaš simbol A, promeni ga u B i pomeri traku levo“ i pravilo: „ Ako si u stanju 2 i učitaš simbol A, promeni ga u C i pomeri traku desno“.

Deterministička Turingova mašina (DTM) ima ''funkciju prenosa'' koja na osnovu zadatog stanja mašine i učitanog simbola određuje sledeće tri stvari:
* simbol koji treba da bude upisan na traku,
* smer pomeranja trake (levo, desno, ili ostanak u mestu),
* sledeće stanje mašine.
Na primer, za učitano X sa trake u stanju 3, DTM može da upiše Y, pomeri traku desno i promeni stanje u 5.

Nedeterministička Turingova mašina (NTM) se od determinističke razlikuje u tome što njene akcije nisu ''jednoznačno određene'' njenim stanjem i učitanim simbolom. ''Mnoge različite akcije mogu da budu izvedene sa istom kombinacijom stanja i učitanih simbola''. Na primer: učitano X sa trake u stanju 3 može da dozvoli da NTM upiše Y, pomeri traku desno i pređe u stanje 5, ili da upiše X, pomeri traku levo i ostane u stanju 3.

== Definicija ==

Nedeterministička Turingova mašina može formalno da se definiše šestorkom <math>M=(Q, \Sigma, \iota, \sqcup, A, \delta)</math>, gde su:

* <math>Q</math> konačni skup stanja,
* <math>\Sigma</math> konačni skup simbola (azbuka trake),
* <math>\iota \in Q</math> početno stanje,
* <math>\sqcup \in \Sigma</math> simbol „prazan“ (blanko),
* <math>A \subseteq Q</math> skup prihvatljivih stanja,
* <math>\delta \subseteq \left(Q \backslash A \times \Sigma\right) \times \left( Q \times \Sigma \times \{L,R\} \right)</math> relacija nad stanjima i simbolima – ''prenosna relacija''. <math>L</math> pomeraj ulevo i <math>R</math> pomeraj udesno.

[[Kategorija:Računski modeli]]
[[Kategorija:Teorija automata]]