Tjuringova masina

Tjuringova mašina

, Visoka tehnološka škola strukovnih studija, Šabac

Sadržaj –

Ovaj rad govori o veoma bitnom čoveku za veliki

doprinos svetu kompijutera Alanu Matison Tjuringu kao i
deteljnije o njegovom najpoznatijem radu ili masini koja je
dobila ime po njemu Tjuringova mašina.

Ključne reči –

MAŠINA, RAČUNAR, ALGORITAM,

KOMPONENTA

1. Uvod

          Tjuringove mašine su izuzetno jednostavni uređaji za
manipulisanje simbolima, koji, uprkos svojoj jednostavnosti,
mogu   da   budu   prilagođeni   da   simuliraju   logiku   bilo   kog
računara koji bi mogao da se konstruiše. Tjuringve mašine je
1936.   Godine   opisao   Alan   Tjuring.   Mada   su   smišljene   da
budu tehnički moguće, Tjuringove mašine nisu smišljene kao
praktična   računarska   tehnologija,   već   kao   misaoni
eksperiment ogranicama mehaničkog računanja, stoga se  u
praksi   ove   mašine   ne   konstruišu.   Proučavanje   njihovih
apstraktnih   svojstava   donosi   značajne   uvide   u   računarsku
nauku i teoriju kompleksnosti.

2.Alan Matison Tjuring

          Alan Matison Tjuring (Alan Mathison Turing) (1912-
1954)   je   britanski   matematičar   i   kriptograf   koji   se   smatra
ocem modernih kompjutera. Za vreme drugog svetskog rata
radio je u Bletčli Parku (Bletchley Park) i sagradio mašinu
pomoću   koje   su   saveznici   mogli   čitati   nemačke   poruke
šifrovane preko Enigma, uređaja koji je imao 15x

〖

^19

kombinacija.

Posle rata je sagradio prve kompjutere i bavio se problemima
veštačke   inteligencije.   Poznat   po   ekcentričnom   životnom
stilu,   bio   je   uhapšen   godine   1952.   zbog   povrede   javnog
morala i osudjen. Dve godine kasnije je izvršio samoubistvo,
iako   postoje   teorije   zavere   koje   tvrde   da   je   likvidaran   od
strane britanske tajne službe zbog toga što je pod ucenom
mogao odati državne tajne stranim agentima.

Poznat je i po tome što je definisao test inteligentnosti
veštačke intelgencije. Cilj ovog testiranja je da se odredi da li
je mašina zaista inteligentna, ili je tek simulacija
inteligencije. Do sada ni jedna mašina nije uspela da prođe
tjuringov test, dok ga ljudi prolaze.

3. Tjuringova mašina

Tjuringova mašina ima vrlo jedostavnu konstrukciju.

Sastoji se od beskonačne trake, koja ima na sebi kućice u
koje mogu da se upisuju simboli i glave koja može da čita i
piše simbole. Za Tjuringovu mašinu se definiše azbuka
simbola koja će se u njoj koristiti, i spisak stanja u kojima
glava za čitanje i pisanje može da se nalazi. Definišu se
početno stanje (C_1), i završno stanje (C_k).

Početno stanje je stanje u kome se mašina nalazi na

početku rada, a kada mašina dođe u završno stanje, prestaje
sa radom.

Glava može da se pomera za jedno polje ulevo (L), za

jedno polje udesno (D), ili da ostane u mestu (M). U
zavisnosti od stanja u kome se glava nalazi, i od simbola koji
se nalaze u kućici, iznad koje je glava postavljena, glava će u
tu kućicu pisati određeni simbol, pomeriti se levo ili desno
(ili ostati u mestu), i promeniti svoje stanje. Ovaj proces se
ponavlja dok Tjuringova mašina ne stigne u završno stanje.

Ideja je nastala u prvoj polovini XX veka iz takozvanih

„nevažnih“ oblasti matematike, koji su pokušali da daju
odgovore da li je neke još nedokazane matematičke teoreme
imaju dokaze. Tim povodom je David Hilbert postavio tri
pitanja:



Da li je Matematika kompletna?



Da li je matematika konzistentna (dosledna,

neprotivrečna)?



Da li je matematika odlučiva (da li postoji

algoritam koji pokazuje da je neka formula

ispravna)?

Matematičar Kurt Gedel 1930.godine odgovorio je na

prva dva pitanja da Matematika nije kompletna, i da će uvek
biti   nedokazanih   teorema.   Ovi   dokazi   su   tridesetih   godina
izazvali   veliko   razočarenje   među   matematičarima.   Alan
Tjuring je 1936 godine dao odgovor na treće pitanje I to na
neobičan   način.   Pošto   je   uočio   određene   ptavilnosti   u
svakodnevnom računanju, zamislio je takozvanu Tjuringovu
mašinu, koja na traci sa simbolima simulira računanje. Ova
zamišljena   (apstraktna-imaginarna)   mašina   nije   stvarno
napravljena. Služila je da pokaže da li se svaki matematički
problem   može   rešiti   korišćenjem   algoritma   (algoritam-
grafički   tok   razmišljanja).   Donela   je   velike   novine,   i
definisala nešto što će kasnije postati kompjuterski algoritam.
Ubrzo zatim je ovu mašinu unapredio i stvorio Univerzalnu
Tjuringovu mašinu, pomoću koje je dao negativan odgovor
na   treće   Hilbertovo   pitanje.   Na   ovaj   Način   su   postavljene
osnove softvera.

Sve što se može izračunati pomoću algoritma, može se

realizovati tjuringovom mašinom.

Slika 1

.Alan Tjuring

4. Komponente (delovi) Tjuringove mašine

Delovi Tjuringove mašine

• Beskonačna traka sadrži polja označena celim

brojevima i služi samo za čitanje i pisanje. Svako polje
(kvadratić) može da sadrži samo jedan od znakova (0, 1,
prazno) koje mašina može pročitati ili napisati. Znaci 0 i 1 su
binarne oznake i služe za zapis informacija. Prazno označava
kraj zapisa

• Glava za čitanje i pisanje se pozicionira iznad

znakova i može da izvrši sledeće operacije na traci



Da pročita jedan znak sa trake iznad polja gde
se nalazi glava



Da napišejedan znak u polje na traci iznad

kojeg se nalazi glava



Pomeri se za jedno polje udesno (+1) ili jedno

polje ulepo (-1)