Turingov stroj

09.02.2019. - Reading time: 36 minutes

Turingov stroj je apstraktni stroj kojega je 1936. godine opisao britanski znanstvenik A. M. Turing u matematičkom časopisu „Proceedings of the London Mathematical Society“ u članku pod nazivom „On Computable Numbers, with an Application to the Entscheidungsproblem“. U njegovu čast stroj se zove Turingov stroj, a model na kojem se stroj temelji Turingov model. Turingov stroj je teorijski koncept te jedan od najvažnijih objekata teorijskog računarstva. Stroj postupak računanja rasčlanjuje na vrlo jednostavne elementarne operacije te zbog toga može biti prilagođen simuliranju logike bilo kojeg računalnog algoritma.

Turingov stroj - definicija

Turingov stroj možemo formalno opisati osmorkom ( Q , S , T , P , b , q0 , qf , δ ). Pri čemu je Q = {q0,q1,...,qN} konačan skup unutarnjih stanja stroja ( uspoređujemo s radnom memorijom današnjih računala ), Skonačan skup vanjske abecede stroja, T je skup elemenata vanjske abecede bez praznog simbola b ∈ S / T (blank), P ∈ Q skup naredbi za pomak glave za čitanje i pisanje, q0  ∈ Q početno stanje stroja, qf  ⊆ Q  konačno stanje stroja i δ  logička funkcija stroja δ : S x Q → S x P x Q , gdje je x Kartezijev produkt.

Iako  na prvi pogled definicija stroja djeluje komplicirano, sama interpretacija stroja je jednostavna te nalikuje na današnja računala. Da bismo u potpunosti razumjeli definiciju potrebno je uvesti i objasniti sve sastavnice stroja.

Turingov stroj ima vanjsku memoriju koju čini beskonačna vrpca, vrpca koja nije ograničena niti s lijeva niti s desna. Vrpca se dijeli na polja tako da svako polje vrpce može sadržavati točno jedan simbol iz S (skupa vanjske abecede). Turingov stroj radi s konačnim brojem simbola koji su elementi skupa S uključujući i prazan simbol b . Prazan simbol se pojavljuje u svim problemima koje rješava Turingov stroj. Kada se prazni simbol upiše u neko polje vrpce on briše taj simbol. Također, prazna vrpca podrazumijeva da se u svim poljima nalazi simbol b . Vrpcu uspoređujemo s hard diskom u današnjim računalima.

Za upis i čitanje simbola na vrpci služi glava za čitanje i pisanje koja je pomična. Glava se može micati za jedni mjesto lijevo ili desno ili mirovati. Po traci se možemo kretati koliko god želimo bez da znamo koliko je duga.

Memorije q i p čine unutarnje memorije stroja. q pohranjuje trenutno unutarnje stanje stroja dok p pohranjuje trenutnu naredbu za pomak glave za čitanje i pisanje. To može biti jedna od triju naredbi: pomak ulijevo L, pomak udesno D i nema pomaka N . Svaka naredba podrazumijeva pomak za točno jedno polje, odnosno mirovanje ako nema pomaka. Dakle vrpcu je potrebno čitati po redu,  ne možemo „skočiti“ na određeno mjesto.

Turingov stroj ima logički blok L u kojem se odvija obrada informacija. U njemu je realizirana logička funkcija stroja δ : S x Q → S x P x Q . Dakle, ulazna dvojka, koju čine simbol koji se nalazi u polju na kojem je trenutno pozicionirana glava za čitanje i pisanje, i unutarnje stanje stroja, koje se nalazi u unutarnjoj memoriji q , se preslikava u izlaznu trojku koju čine simbol iz vanjske abecede koji će se upisati u polje na kojem je glava za čitanje i pisanje, naredba za pomak glave za čitanje i pisanje koja se sprema u memoriju p i novo unutarnje stanje stroja koje se sprema u memoriju q. 

Rad Turingovog stroja

Rad Turingovog stroja se odvija u taktovima (diskretnim vremenskim trenucima). Na početku rada stroja na vrpci se nalazi neki zapis , početni niz simbola iz skupa vanjske abecede (ulazni podaci) , a stroj je u unutarnjem stanju q0 (početno stanje stroja). Također se definira na kojem polju na vrpci se nalazi glava za čitanje i pisanje.

U jednom taktu stroj čita simbol s polja na kojem se nalazi glava za čitanje i pisanje, označimo ga sa si. Stanje u kojem se stroj trenutno nalazi označimo s qm . Zatim se (si , qm) preslikava u (sj , p , qk) pri čemu je sj  simbol koji će se upisati u polje na kojem se nalazi glava za pisanje i čitanje, p je naredba za pomak glave za čitanje i pisanje koja će se upisati u unutarnju memoriju p , a qk je novo unutarnje stanje stroja koje se upisuje u unutarnju memoriju q .Na kraju takta glava za čitanje i pisanje se pomiče ovisno o naredbi koja se nalazi u unutarnjoj memoriji p .

Novi takt započinje s unutarnjim stanjem qk  te čitanjem simbola na kojem se nalazi glava za čitanje i pisanje nakon pomaka. Stroj se zaustavlja kada dođe u završno stanje qf  i napravi pomak. Napredovanje u taktovima tada prestaje , a zapis koji preostane na vrpci je rezultat obrade. Budući da stroj tijekom svojeg rada, napredovanjem po taktovima, postepeno mijenja zapis na vrpci, od početne informacije prema završnom rezultatu, zapis na vrpci na kraju svakog takta smatramo međuinformacijom.

„Program“ za Turingov stroj

Kao što sam već spomenuo turingov stroj rješava problem obavljanjem jednostavnih operacija. Možemo reći da su te operacije skoro nedjeljive, odnosno elementarne.

Operacija zamjene znaka i promjena unutarnjeg stanja stroja mijenja znak si u sj . Ako je i = j znak u polju na kojem se nalazi glava za čitanje i pisanje se ne mijenja. Ako je sj = b (blank) onda se znak u polju na kojem se nalazi glava briše. Također, mijenja unutarnje stanje qm u qk . Ako je m = k tada se unutarnje stanje ne mijenja. Promjenu određuje logička funkcija δ : ( si , qm)   →  ( sj , p , qk).

Operacija pomaka glave za čitanje i pisanje pomiče glavu za jedno polje lijevo ako je naredba L, za jedno polje desno ako je naredba D , odnosno ne miče glavu ako je naredba N, tada glava ostaje na trenutnom polju.

Obrada informacija se odvija u logičkom bloku L i definirana je funkcijom δ . Realizaciju te funkcije predstavlja „program“ za Turingov stroj. Predočava se pomoću tablice preslikavanja, a naziva se funkcionalna shema Turingovog stroja.

U prvom retku tablice nalaze se sva unutarnja stanja stroja bez konačnog stanja gf  . U prvom stupcu tablice nalaze se simboli iz vanjske abecede (skupa S). U unutarnjim poljima tablice nalaze se trojke (s , p , q) tako da je s ∈ S, p ∈ P i q ∈ Q . Pretpostavim da se stroj nalazi u stanju qm te da glava za čitnaje i pisanje pročita simbol si, trojku koja odgovara preslikavanju dvojke (si , qm ) određujemo tako da očitamo sadržaj u polju tablice koje se nalazi na sjecištu retka si i stupca qm .

Napomenimo još samo da postoji više modela Turingovih strojeva: nedeterministički (δ nije funkcija, nego relacija), višetračni (stroj radi na više traka odjednom), s poluograničenom trakom (traka je ograničena s jedne strane). U ovom seminaru radit ćemo samo s determinističkim jednotračnim Turingovim strojem kakvog sam do sada opisao.

Stroj je primjenjiv za početnu informaciju ako se nakon konačno mnogo taktova zaustavi i pritom je na vrpci zapisana konačna informacija (stroj daje rezultat). Ako stroj nikad ne staje (nikad ne dosegne završno stanje) tada on nije primjenjiv za početnu informaciju. Opet uspoređujemo s današnjim računalima. Ako je program ispravno napisan on će uredno dati rezultat i završiti. U suprotnom, ako ima neku grešku (npr. beskonačna petlja), program neće završiti te je potrebno napraviti restart.

Objasnimo sada rad Turingovog stroja na konkretnom primjeru.

Neka je na vrpci Turingovog stroja zapisan po volji odabran broj (dekadski). Napisat ćemo program za Turingov stroj koji taj broj poveća za jedan (inkrementira). Stroj se na početku nalazi u stanju q0  ,a položaj glave je lijevo od najmanje značajne znamenke broja na nepoznatoj poziciji.

U skladu s ranije navedenom definicijom imamo:

Skup vanjske abecede, njega čine sve znamenke dekatskog brojevnog sustava i prazni simbol b . Imamo  S = {0,1,2,3,4,5,6,7,8,9,b}

Skup unutarnjih stanja, njega čini početno stanje stroja q0 , završno stanje stroja qf  i neki određeni broj unutarnjih stanja, u našem slučaju dva q1  i q2. Dakle Q = { q0, q1, q2, qf }. Broj unutarnjih stanja ovisi o algoritmu, elegantnije rješenje ima manji broj unutarnjih stanja.

Da bi smo rješili problem moramo dovesti glavu za čitnaje i pisanje do najmanje značajne znamenke jer neznamo gdje se glava početno nalazi, može biti na praznom polju ili na nekoj znamenci. Kada pozicioniramo glavu na najmanje značajnu znamenku preostaje pročitati koja je to znamenka, te ako je znamenka 0 zamijeniti ju s 1, ako je znamenka 1 zamijeniti ju s 2, i tako dalje. Ako je znamenka 9 mijenjamo ju s 0, pomičemo glavu u lijevo i ponovno ponavljamo isti postupak.

Funkcionalna shema za ovaj primjer izgleda ovako:

Promotrimo sada kako bi stroj izvršio zadatak za broj 2469 takt po takt s početnim položajem kao na slici.

Glava za čitanje i pisanje čita prazni znak b, stroj se nalazi u početnom stanju q0 . Iz funkcionalne sheme čitamo ćeliju ( b , q0 ). To je trojka ( b , D , q0) što znači da glava ponovno upisuje znak b , odnosno ne mijenja sadržaj polja, glavu pomičemo za jedno polje u desno, ostajemo u početnom stanju q0. Kraj prvog takta.

U sljedećem taktu imamo analognu situaciju kao i u prvom.

U trećem taktu glava čita 2 a stroj se nalazi u stanju q0 . Prema shemi zaključujemo da glava ponovno piše 2, pomiče se za jedno polje u desno te stroj prelazi u stanje q1.

Stroj analogno postupa u sljedećih nekoliko taktova.

U ovom taktu stroj čita b te se nalazi u stanju q1 . To znaći da smo pronašli najmanje značajnu znamenku. Ona se nalazi jedno polje u lijevo. Točno to će i stroj učiniti prema shemi. Neće mijenjati zapis u polju, pomaknut će glavu jedno polje u lijevo i preći u stanje q2 .

Sada kada je najmanje značajna znamenka pronađena , ona se može inkrementirati. Glava čita 9, stroj je u stanju q2 . Prema shemi glava upisuje 0, pomiče se jedno mjesto u lijevo , stroj ostaje u stanju q2.

Konačno, ( 6, q2 ) → (7 , N , qf  ), glava upisuje 7, ne pomiče se, stroj ulazi u završno stanje qf  te se zaustavlja, na vrpci je prikazano konačno rješenje.

Zaključak

Turingov stroj je apstraktni stroj izvršitelj. Ima neograničenu vanjsku memoriju u obliku beskonačne vrpce koja je podijeljena na polja. Stroj radi u taktovima te se u svakom taktu glavu za čitanje i pisanje može pomaknuti za samo jedno polje. Stroj ima dvije unutarnje memorije q i p u kojima pamti unutarnje stanje i naredbu za pomak glave za čitanje i pisanje.Obradu informacija stroj vrši u logičkom bloku gdje je realizirana logička funkcija stroja.

Turingov stroj ne koristi se u praktične svrhe, samo u istraživanju računalnih algoritama te čini temelj današnjih računala.

Literatura

1. Slobodan Ribarić, Građa računala : Arhitektura i organizacija računarskih sustava, Algebra grupa, 2011.
2. Vedran Šego, Turingovi strojevi, (Skripta za vježbe)
3. Wikipedia, Turingov stroj, http://en.wikipedia.org/wiki/Turing_machine, 28.10.2014.

---

Citiraj

Novak, Siniša (09.02.2019.). Turingov stroj. Sustav. Preuzeto s https://sustav.sino.com.hr/turingov-stroj ()