Modeli Turingovog stroja

U teoretskom računarstvu, posebice u teoriji automata, Turingov stroj (TS) predstavlja najopćenitiji mogući matematički model izračunljivosti. Osnovni se model Turingovog stroja može na razne načine proširiti ili pojednostavniti, i na taj se način odgovarajuće promijeniti neki od njegovih fundamentalnih svojstava, prije svega vremenska i prostorna složenost prihvaćanja jezika.

Prošireni modeli Turingovog stroja

Osnovni je model TS moguće proširiti na više načina. Šest osnovnih načina proširenja osnovnog modela TS su: TS s dvostranom beskonačnom trakom, TS s višestrukim trakama, nedeterministički TS, TS s višedimenzionalnim ulaznim poljem, TS s više glava za čitanje i pisanje, te neizravni TS.

Turingov stroj s dvostranom beskonačnom trakom

Za razliku od osnovnog modela TS, ulazna traka jest beskonačna na lijevu stranu i na desnu stranu. Nema krajnje lijeve ni krajnje desne ćelije. Osim u dva slučaja, relacija $\succ$ je jednaka relaciji osnovnog modela.

Osnovni model TS nema pomaka lijevo od krajnje lijeve ćelije ulazne trake. Budući da prošireni model TS ima beskonačnu traku na lijevu stranu, u slučaju pomaka lijevo od krajnje lijevog znaka X, glava za čitanje i pisanje postavlja se na praznu ćeliju:

Ako je $\delta (q,X)=(p,Y,L)$, onda je $qX\alpha \succ pBY\alpha$

Za razliku od osovnog modela TS koji funkcijom $\delta (q,X)=(p,B,R)$ prelazi iz konfiguracije $qX\alpha$ u konfiguraciju $Bp\alpha$, gdje je oznaka prazne ćelije B lijevo od stanja p, za TS s dvostranom beskonačnom trakom vrijedi:

Ako je $\delta (q,X)=(p,B,R)$, onda je $qX\alpha \succ p\alpha$

U novoj konfiguraciji nema oznake prazne ćelije B lijevo od oznake stanja p.

Može se pokazati da je TS s dvostranom beskonačnom trakom istovjetan osnovnom modelu TS.

Turingov stroj s višestrukim trakama

TS ima k glava za čitanje i pisanje i k dvostrano beskonačnih traka. Upravljačka jedinka TS donosi odluku na temelju dviju skupina parametara:

1. stanje upravljačke jedinke;
2. k pročitanih znakova sa k traka.

Jednim prijelazom TS:

1. promijeni stanje;
2. zapiše k znakova na k traka
3. pomakne bilo koju od k glava nezavisno u desno ili lijevo

Na jednu traku, koja se zove ulazna traka, zapiše se niz koji se ispituje. Sve ostale trake nazivaju se radnim trakama.

TS s višestrukim trakama istovjetan je osnovnom modelu TS.

Može se pokazati da je broj pomaka glave TS s jednom trakom kvadratna funkcija broja pomaka glave TS s više traka. Pretpostavi li se da pomak glave troši jedinično vrijeme, smanjivanje više traka TS na jednu traku značajno usporava vrijeme prihvaćanja jezika.

Nedeterministički Turingov stroj

Za razliku od funkcije prijelaza $\delta$ determinističkog TS koja je jednoznačna, funkcija $\delta$ nedeterminističkog TS nije jednoznačna:

$\delta (q,X)=\left\{{(p_{1},Z_{1},D_{1}),(p_{2},Z_{2},D_{2}),...,(p_{k},Z_{k},D_{k})}\right\}$

Čitanjem znaka X sa ulazne trake, pri čemu je upravljačka jedinka u stanju q, TS prelazi u neko od stanja $p_{i}$, na traku zapiše znak $Z_{i}$, te miče glavu u smjeru $D_{i}$. Promijeni li se stanje u $p_{i}$, na traku nije moguće zapisati znak $Z_{j}$ ili pomaknuti glavu u smjeru $D_{j}$, gdje je $i\neq j$. Završi li barem jedan slijed prijelaza prihvatljivim stanjem, niz se prihvaća. Ne završi li niti jedan slijed prijelaza prihvatljivim stanjem, niz se ne prihvaća.

Nedeterminizam ne omogućava prihvaćanje šireg skupa jezika, te je nedeterministički TS istovjetan determinističkom TS.

Turingov stroj s višedimenzionalnim ulaznim poljem

Umjesto jednodimenzionalne trake, koristi se k-dimenzionalno polje ćelija koje je beskonačno u svim smjerovima, pri čemu je k konačni broj. Na temelju stanja i pročitanog znaka, TS odlučuje o promjeni stanja, zapiše novi znak u ćeliju i odlučuje o pomaku glave. Glavu je moguće pomaknuti uzduž svake od k osi u pozitivnom ili negativnom smjeru. Sveukupno je 2k različitih načina pomaka glave. Na početku rada ulazni niz je zapisan uzduž jedne od k osi i glava je postavljena na krajnje lijevi znak ulaznog niza.

Budući da je u ulaznom nizu konačni broj znakova i jer TS u bilo kojem trenutku rada pomakne glavu konačni broj puta, samo konačni broj ćelija bilo koje osi je neprazan. Neprazne ćelije u k-dimenzionalnom polju je moguće smjestiti u k-dimenzionalni prostorni kvadar, a sadržaj ćelija k-dimenzionalnog kvadra moguće je spremiti na jednodimenzionalnu traku. Slijedi da je TS s dvodimenzionalnim poljem ćelija istovjetan TS s jednodimenzionalnom trakom.

Turingov stroj s više glava za čitanje i pisanje

Model TS s više glava za čitanje i pisanje ima jednu traku i k glava za čitanje i pisanje. Glave se nezavisno miču u lijevo ili desno. TS donosi odluku na temelju stanja i na temelju k pročitanih znakova.

TS s k glava za čitanje i pisanje istovjetan je TS s jednom glavom za čitanje i pisanje.

Neizravni Turingov stroj

Neizravni TS jest model automata koji se koristi u istraživanju prostorne složenosti prihvaćanja jezika i prostorne složenosti računanja cjelobrojnih funkcija. Neizravni TS ima više radnih traka i jednu ulaznu traku. Ulaznu traku moguće je samo čitati. Niz na ulaznoj traci omeđen je graničnicima $\not c$ i $. Glavu za čitanje ulazne trake nije moguće pomaknuti izvan područja omeđenog graničnicima.

Neizravni TS istovjetan je TS s višestrukim trakama.

Pojednostavljeni modeli Turingovog stroja

Stogovni stroj

Stogovni stroj je deterministički TS s jednom ulaznom trakom i više stogova. Ulaznu traku moguće je samo čitati. Stog jest posebna radna traka pojednostavljenih funkcija prijelaza: pomakne li se glava u lijevo, u ćeliju se obavezno zapiše oznaka prazne ćelije. Sve ćelije stoga desno od glave za čitanje i pisanje su prazne.

TS s jednom trakom moguće je simulirati primjenom stogovna stroja sa dva stoga.

Stroj s brojilima

Model stogovnog stroja s dva stoga moguće je još više pojednostavniti. Umjesto dva stoga, stroj koristi četiri brojila. Skup znakova stoga ograniči se na dva znaka: oznaku dna stoga X i oznaku prazne ćelije B. Oznaka dna stoga X je u krajnje lijevoj ćeliji. Glavu nije moguće pomaknuti lijevo od oznake dna stoga X. Pomakne li se glava stoga u desno za i ćelija od znaka X, vrijednost brojila jednaka je i. Pomakne li se glava u desno ili lijevo za jednu ćeliju, povećava se ili smanji vrijednost brojila za jedan. Čita li glava oznaku dna stoga X, vrijednost brojila jednaka je 0. Dodavanje konstantne cjelobrojne vrijednosti k postiže se dodatnom komponentom stanja koja omogući k pomaka glave u desno, a oduzimanje vrijednosti postiže se dodatnom komponentom stanja koja omogući k pomaka glave u lijevo.

TS s jednom trakom moguće je simulirati primjenom stroja sa četiri brojila. Također, stroj sa četiri brojila moguće je simulirati primjenom stroja s dva brojila.

Turingov stroj s ograničenim brojem stanja i znakova trake

Ako se istodobno ograniči broj znakova trake, broj traka i broj stanja, onda je ograničen broj različitih Turingovih strojeva koje je moguće izgraditi. Zato TS s ograničenim brojem znakova trake, s ograničenim brojem traka i s ograničenim brojem stanja ne prihvaća isti skup jezika kao i osnovni model TS. Međutim, ne ograniči li se broj znakova trake, dovoljno je za prihvaćanje bilo kojeg rekurzivno prebrojivog jezika imati jednu traku i tri stanja, od čega su dva stanja neprihvatljiva i jedno stanje prihvatljivo.

Nadalje, ako se ne ograniči broj stanja, tada je moguće ograničiti broj znakova trake na ${0,1,B}$, što je dovoljno za prihvaćanje bilo kojeg rekurzivno prebrojivog jezika.

Izvori

• Siniša Srbljić (2003). Jezični procesori 1. Element. ISBN 953-197-129-3