1511

Turing gép
IB baratomnak biztos tetszeni fog :)
A fogalmat Alain Turing vezette be 1936-ban. (Turing Machine: TM) Algoritmusok modellezésére szolgál. A legáltalánosabb absztrakt automata. Elméletszámítási modell szerepét tölti be a matematikában és a számítástechnikában is.
Képzeljünk el egy végtelen szalagot, amin vannak “cellák”, vagy bárminek nevezhetjük, lényegtelen. A szalagon reguláris kifejezések állnak (w), a szavak a Σ (szigma)ábécé jeleit tartalmazzák.
  …. | a1 | aa | ….. | ai | ….. | an | BB | …..  

(w∈Σ) Van egy fej, ami mozoghat balra és jobbra is egy-egy lépést. A fej írhat a szalagra minden lépésnél egy jelet (Γ output ábécé). Értelmezett az üres (Blank) utasítás, jelölése ‘B’. Σ⊆Γ, B∈Γ.
Működése: A fej az ai jel beolvasása után a cellába egy másik ai∈Γ jelet ír, majd elmozdul eggyel jobbra vagy balra.
Formálisan a TM gép: M=(Q,Σ,Γ,δ,q0,B,F) ahol Q=állapotok halmaza (véges); Σ=input ábécé; Γ=verem ábécé; δ=tranzíciós függvények; q0=kezdőállapot(ok); B=blank szimbólum; F=végállapotok hamaza.
(ai,qj) -δ→ (qp,Y,R|L)
δ: Q × Γ → Q × Γ × {L,R} (L: balramozgás; R: jobbramozgás)
A δ tranzíciós függvény parciális, nem mindenütt értelmezett függvény.
Ł(M)={w∈Σ* | w hatására a TM q0-ból indulva egy qf∈F végállapotba kerül, a fej pedig egy jobbszélső cellába (a szó elfogy) }
Í TM miután beolvas egy akceptált szót, megáll. Arra is lehetőség van, hogyha egy nem akceptált szót olvasunk be, soha ne álljunk meg, azaz a gép ciklusba kerül (hajjajaj :) Mellesleg a TM által elfogadott nyelvet rekurzívan felsorolhatónak nevezzük. (Rekurzív nyelv pl: {ww | w∈(0+1)*} ) A Turing gépet felfoghatjuk úgy is, mint úgynevezett egész függvényeket kiszámító berendezést.

 
Ezzekkel a dolgokkal mondjuk szerettem szoszmotolni :)) Mellesleg az a tantargy ahol ezt is tanultuk messze a legkonnyebb tantargyunk volt, de meg ez is olyan durva tantargy volt, hogy barki, temaban nem jaratos ember kinzasara alkalmas lenne, (vagy a vilagbol valo kikergetesre :) Meglehetosen absztrakt matematika ez. (Ne mondja nekem senki, hogy a matematika fekete-feheren tenyek, meg konkret dolgok… aki ilyet mond, csak alapfokon ismeri a matematika tudomanyat, nem tud az semmit… olyan elvont dolgok vannak benne, hogy meg az absztrakt muveszek is megirigyelhetnek :)

Leave a Reply

Your email address will not be published. Required fields are marked *