Turingova mašina
Sa Wikipedije, slobodne enciklopedije
Turingova mašina je matematički model izumljen od strane britanskog matematičara Alan Turinga, za stvaranje klase od predvidljivih funkcija. Ona je predstavljena od strane David Hilberta 1920, specijalno za rješavanje problema u odlučivanju, u djelu On Computable Numbers, with an Application to the Entscheidungsproblem. Alan Turing je namjeravao stvoriti jedan model matematički radećeg čovjeka.
Turingova mašina se sastoji od:
- jedne neograničeno duge trake sa neograničeno mnogo polja. U svakom od tih polja se može snimiti jedan znak.
- jedne programski upravljanje čitace odnosno pisače glave, koja se po traki samo po jedno polje pokreće i znakove mijenja.
Turingova mašina modificira unos na traci po jednom datom programu. Ako je preračuvanje završeno, onda se rješenje nađe na traci. Tako se svakoj ulaznoj vrijednosti dodijeljuje izlazna. Turingova mašina ne mora za sve ulazne vrijednosti da staje. U tom slučaju je funkcija unosa nedefinisana.
Kao rješenje se nekad definiše redoslijed znakova, koji poslije zastavljanja na traci stoji. Turingova mašina se najčesće koristi (također sa mnogim drugim automatima) za probleme odlučivanja, znači za pitanja, koja se sa da ili ne mogu odovoriti. Pri tome se zaustavljanje Turingove mašine interpretiralo kao da, a ne zaustavljanje kao ne.
[uredi] Primjer
Sljedeca deterministicka jednotrakna turingmasina M ocekuje jedan niz od jedinica na traci. Ona udvostrucuje broj jedinica pri cemu jedan blank-symbol ostaje u sredini. Iz "111" se naprimjer pravi "1110111". Pisaca odnosno citaca glava se nalzi inicijalno na prvoj jedinici. Pocetna stanje je s1, a zadnje stanje je s6. Nulla stoji za prazno mjesto i traka je sve do napisanih jedinica popunjena praznim znakovima.
M = (Q,Σ,Γ,δ,s1,0,F) * Q = {s1,s2,s3,s4,s5,s6} * Σ = {1} * Γ = {1,0} * F = {s6} staro procit. pisa. novo glava- staro procit. pis. novo Glava- stan. simbol simbol stan. pravac stan. simbol simbol stan. pravac ------------------------------------ ------------------------------------ s1 1 -> 0 s2 R s4 1 -> 1 s4 L s1 0 -> 0 s6 0 s4 0 -> 0 s5 L s2 1 -> 1 s2 R s5 1 -> 1 s5 L s2 0 -> 0 s3 R s5 0 -> 1 s1 R s3 0 -> 1 s4 L s3 1 -> 1 s3 R
R - right(desno) L - left(lijevo) 0 - nema pomjeranja
M prolazi naprimjer kod unosa "11" sljedeca stanja, pri cemu je trenutna pozicija glave debelo napisano:
Korak Stanje Traka Korak Stanje Traka
------------------- -------------------
1 s1 11000 9 s2 10010
2 s2 01000 10 s3 10010
3 s2 01000 11 s3 10010
4 s3 01000 12 s4 10011
5 s4 01010 13 s4 10011
6 s5 01010 14 s5 10011
7 s5 01010 15 s1 11011
8 s1 11010 16 s6 -stani-
