Nedeterministička Turingova mašina

U teoriji računarstva, 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.

Nedeterministička Turingova mašina može formalno da se definiše šestorkom ${\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )}$, gde su:

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