Tjuringova mašina

Iz projekta Википедија

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. Tjuringove 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 o granicama 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.

[uredi] Primer

Tjuringova mašina ima vrlo jednostavnu 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 (S₁), i završno stanje (S_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 nalazi u kućici iznad koje je glava postavljena, glava će u tu kućicu upisati 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. Sledi primer tjuringove mašine koja sabira dva broja:

• Azbuka nad kojom Tjuringova mašina radi je sledeća: „1“ (cifra broja), „+“ (znak za sabiranje) „α“ (prazne kućice)

Mašina treba da od niza 1^m+1ⁿ napravi niz 1^m+n. Na primer, od niza ..αα1111+111αα.. treba da napravi niz ..αα1111111αα..

• Stanja mašine su:
  • S₁ 1 -> α S₂ D - ako je glava u stanju 1, i nalazi se nad poljem u kome je upisano 1, u to polje se upisuje α, glava se pomera desno, i prelazi u stanje 2
  • S₂ 1 -> 1 S₂ D - ako je glava u stanju 2, i nalazi se nad poljem u kome je upisano 1, u to polje se upisuje 1, glava se pomera udesno, i ostaje u stanju 2
  • S₂ + -> 1 S₃ L - ako je glava u stanju 2, i nalazi se nad poljem u kome je upisano +, u to polje se upisuje 1, glava se pomera ulevo, i prelazi u stanje 3
  • S₃ 1 -> 1 S₃ L - ako je glava u stanju 3, i nalazi se nad poljem u kome je upisano 1, u to polje se upisuje 1, glava se pomera ulevo, i ostaje u stanju 3
  • S₃ α -> α S_k D - ako je glava u stanju 3, i nalazi se nad poljem u kome je upisano α, u to polje se upisuje α, glava se pomera udesno, i prelazi u završno stanje, k

Komentar: Mašina polazi iz stanja 1, a glava se nalazi nad poljem gde je prva cifra prvog sabirka. Ona tu prvu „1“ briše (upisuje „α“), i zatim se pomera desno sve dok ne naiđe na znak „+“. Umesto znaka plus, upisuje se „1“, i time se dva broja spajaju u jedan. Zatim se glava pomera levo, sve dok ne naiđe na „α“, onda se vraća za jedno polje desno (kako bi bila na početku novog broja), i tu se rad završava. Ovo vraćanje na početak nije bilo neophodno.