tin ukol3

´ uc ˇen´ı technicke ´ v Brne ˇ Vysoke ˇn´ıch technologi´ı Fakulta informac Teoretick´a informatika Tˇret´ı u ´kol 2011 Jan Tr´avn´ıˇcek  1. Tato u ´loha je ˇreˇsena Turingov´ ym strojem, kter´ y je zobrazen na obr´azku 1, kter´ y si m˚ uˇzeme rozdˇelit na tˇri samostatn´e ˇc´ asti. Jednotliv´e ˇc´ asti jsou v obr´azku naznaˇceny pˇreruˇsovan´ ymi ˇcarami. V prvn´ı ˇc´asti se prov´ad´ı pouze kontrola, zda je na vstupn´ı p´asce validn´ı vstup ve tvaru ∆A#B∆ω , kde A, B ∈ {0, 1}+ . Ve druh´e ˇc´asti je vstup zarovn´ an tak, aby oba operandy byly zobrazeny na stejn´em poˇctu bit˚ u. T´ımto si zjednoduˇs´ıme n´ asledn´e sˇc´ıt´ an´ı, kter´e m˚ uˇzeme prov´adˇet obecnˇeji a nemus´ıme tuto skuteˇcnost oˇsetˇrovat pˇri samotn´em sˇc´ıt´ an´ı. Ve tˇret´ı ˇc´asti je pak jiˇz provedeno pouze samotn´e sˇc´ıt´an´ı dvou bin´arn´ıch ˇc´ısel stejn´e d´elky. V´ ysledek sˇc´ıt´an´ı je pak uloˇzen na p´ asce dle zad´ an´ı. R R ¬0,1 # R ¬0,1,# L } LΔ ¬0,1 ¬0,1,# R #L R } ΔRΔL } ΔLΔωL } Δ ΔRΔSRLΔ0L#RR # ΔRΔλL Δ } ΔRΔSRLΔLSRLΔ0 RΔλL # R R0L L Δ RS L Δ # 0,1 } ω S R L 0,1 } λ S R L Δ L 0 0R S L 0L Δ R Δ # 0 λ 1 1R S L 0L Δ R Δ # 0 ω 1 λ 0 1 0RΔSRLΔ1L# 0 λ 1 0 1R S L 0L 1 ω Δ R Δ # 1 λ 0 0R S L 1L Δ R Δ # 1 1R S L 1L Δ R Δ # Obr´ azek 1: Turing˚ uv stroj reprezentuj´ıc´ı sˇc´ıt´an´ı dvou bin´arn´ıch ˇc´ısel. 1  2. Tˇr´ıdu jazyk˚ u pˇrij´ıman´ ych turingov´ ym strojem oznaˇcme LT S . Tˇr´ıdu jazyk˚ u pˇrij´ıman´ ych dvojz´ asobn´ıkov´ ym automatem oznaˇcme LDA . Jsou-li tyto dvˇe tˇr´ıdy jazyk˚ u ekvivalentn´ı, je tˇreba dok´azat obˇe inkluze LT S ⊆ LDA a LDA ⊆ LT S . • Prvn´ı inkluzi LT S ⊆ LDA dok´ aˇzeme algoritmem, kter´ y k turingovu stroji sestroj´ı odpov´ıdaj´ıc´ı dvojz´asobn´ıkov´ y automat. Idea tohoto algoritmu je pops´ana slovnˇe. – Zvolme Z0 = #. Bez ujmy na obecnosti m˚ uˇzeme prohl´asit, ˇze # ∈ / Σ. Symbol # je tedy dno z´ asobn´ıku. – Vstup dvojz´ asobn´ıkov´eho automatu odpov´ıd´a ˇretˇezci w, kter´ y odpov´ıd´a ˇretˇezci neblankov´ ych symbol˚ u poˇc´ ateˇcn´ı konfigurace p´asky turingova stroje, kter´a je ve tvaru ∆w∆ω . – Na prvn´ı z´ asobn´ık vloˇz´ıme symbol ∆. Vrchol prvn´ıho z´asobn´ıku odpov´ıd´a pozici hlavy simulovan´eho turingova stroje. – D´ale je tˇreba definovat operace, kter´e umoˇzn ˇuje turing˚ uv stroj, tedy z´apis, posun doprava a posun doleva. – Pˇri posunu doprava je tˇreba rozliˇsovat tˇri moˇzn´e varianty, kter´e mohou nastat. Pokud je na druh´em z´ asobn´ıku pouze symbol # (dno z´asobn´ıku) a vstup dvojp´askov´eho z´asobn´ıku obsahuje jeˇstˇe nepr´ azdn´ y ˇretˇezec, pˇreˇcteme symbol z p´asky a uloˇz´ıme jej na vrchol prvn´ıho z´asobn´ıku. Pokud je na druh´em z´asobn´ıku pouze symbol # a na vstupu automatu je jiˇz pr´azdn´ y ˇretˇezec, vloˇz´ıme na vrchol prvn´ıho z´asobn´ıku symbol ∆. Pokud je na druh´em z´asobn´ıku mimo symbol # jeˇstˇe jin´ y symbol, vezmeme symbol z vrcholu druh´eho z´asobn´ıku, odebereme ho z druh´eho z´ asobn´ıku a uloˇz´ıme ho na vrchol prvn´ıho z´asobn´ıku. – Pˇri posunu doleva se pˇreˇcte symbol z vrcholu prvn´ıho z´asobn´ıku a pˇresune se na druh´ y z´asobn´ık. Pokud je na vrcholu prvn´ıho z´asobn´ıku symbol dna z´asobn´ıku #, pˇredstavuje to situaci, kdy bˇeh odpov´ıdajic´ıho turingova stroje posunul ˇctec´ı hlavu doleva pˇred zaˇc´ atek p´asky. – Pˇri z´ apisu znaku na m´ısto ˇctec´ı hlavy (vrchol prvn´ıho z´asobn´ıku) je znak z vrcholu odebr´ an a nahrazen nov´ ym zpˇet na vrchol prvn´ıho z´asobn´ıku. – Pˇri simulaci TS pˇri pˇrechodu mezi stavy se znak z prvn´ıho z´asobn´ıku pˇreˇcte a vr´at´ı zpˇet. – Pˇri ˇr´ adne formalizaci popsan´eho algoritmu pak nen´ı teˇzk´e uk´azat, ˇze v´ ysledn´ y dvojz´ asobn´ıkov´ y automat simuluje turing˚ uv stroj. • Druhou inkluzi LDA ⊆ LT S dok´ aˇzeme slovn´ım popisem algoritmu simulace dvojz´asobn´ıkov´eho automatu pomoc´ı turingova stroje. – Pouˇzijeme tˇr´ıp´ askov´ y turingov´ y stroj, kde na prvn´ı p´asku poloˇzme vstupn´ı ˇretˇezec dvojz´asobn´ıkov´eho automat. Druhou a tˇret´ı p´asku budeme povaˇzovat za dva z´asobn´ıky. Jiˇz bylo dok´ az´ ano, ˇze v´ıcep´ askov´e turingovy stroje nezvyˇzuj´ı s´ılu a tud´ıˇz jsou ekvivalentn´ı s jednop´ askov´ ymi turingovy stroji. – Druhou a tˇret´ı p´ asku, budeme pouˇz´ıvat tak, jak jsme zvykl´ı z pr´ace se z´asobn´ıky. Budeme tedy vˇzdy pracovat pouze s posledn´ım symbolem, kter´ y pˇredstavuje vrchol z´asobn´ıku. Z´asobn´ıkov´e“ operace jistˇe lze prov´adˇet pomoc´ı turingova stroje. ” – Pˇri ˇr´ adn´e formalizaci popsan´eho postupu m˚ uˇzeme dok´azat, ˇze dvojz´asobn´ıkov´ y automat lze simulovat tˇr´ıp´ askov´ ym turingov´ ym strojem, tedy i jednop´askov´ ym turingov´ ym strojem. • Tˇr´ıdy jazyk˚ u LT S a LDA jsou tedy ekvivalentn´ı, jak bylo dok´azano neform´aln´ım popisem obou stran inkluze. 2  3. 1. Nerozhodnutelnost • Redukc´ı z probl´emu zastaveni TS. • Probl´em zastaven´ı lze charakterizovat jazykem HP = {<M >#<w>|M je TS takov´ y, ˇze zastav´ı, je-li spuˇstˇen na ˇretˇezci w}. • Probl´em, zda jazyk dan´eho TS obsahuje alespoˇ n jedno slovo z jazyka L3 = {ww|w ∈ ∗ {a, b} }, lze charakterizovat jazykem P = {<M >|(L(M ) ∩ L3 ) 6= ∅}. • Sestroj´ıme redukci σ : {0, 1, #}∗ → {a, b}∗ z jazyka HP na jazyk P . • TS Mσ vyˇc´ıslujic´ı σ pˇriˇrad´ı kaˇzd´emu vstupu x ∈ {0, 1, #}∗ ˇretˇezec <Mx >, kde Mx je TS, kter´ y na vstupu w ∈ {a, b}∗ pracuje tatko: (a) Mx smaˇze ˇretˇezec w ze sv´eho vstupn´ı p´asky. (b) Na vstupn´ı p´ asku zap´ıˇse ˇretˇezec x. (c) Mx ovˇeˇr´ı, zda x m´ a strukturu x1 #x2 , kde x1 je k´od TS a x2 k´od jeho vstupu. Nem´ a-li tuto strukturu, odm´ıtne. (d) Mx odsimuluje na sv´e p´ asce bˇeh TS s k´odem x1 na ˇretˇezci s k´odem x2 . Vede-li simulace k zastaven´ı, pˇrijme, jinak cykl´ı. • Mσ lze zˇrejmˇe realizovat jako u ´pln´ y TS – jedn´a se o v´ ypis pˇredpˇripraven´ ych komponent TS (body a, c, d) a o k´ od TS, tker´ y pˇrep´ıˇse zadan´ y ˇretˇezec x na p´asku (bod b). • Pro jazyk TS Mx plat´ı: – L(Mx ) = ∅ ⇔ (L(Mx ) ∩ L3 ) = ∅ ⇔ x nen´ı platnou instanc´ı probl´emu zastaven´ı nebo pokud x = x1 #x2 a TS s k´odem x1 nezastav´ı na ˇretˇezci s k´odem x2 (x ∈ / HP ). – L(Mx ) = {a, b}∗ ⇔ (L(Mx ) ∩ L3 ) 6= ∅ ⇔ x = x1 #x2 a TS s k´odem x1 zastav´ı na ˇretˇezci s k´ odem x2 ⇔ x ∈ HP . ˇ asteˇcnou rozhodnutelnost nen´ı ze zad´an´ı tˇreba dokazovat. 2. C´ 3  4. Turingovu stroji M4 odpov´ıd´ a gramatika G4 = ({S, A, B}, {a, b}, P, S), kde P je koneˇcn´a mnoˇzina pravidel definov´ an´ ych n´ asledovnˇe P: S −→ a | aA A −→ bB B −→ bB | aS Mˇejme ˇretˇezec w = abbbaabaa, pro kter´ y jistˇe plat´ı, ˇze w ∈ L(M4 ). Bˇeh stroje M4 pro tento ˇretˇezec po t´e vypad´a n´ asledovnˇe pro poˇc´ ateˇcn´ı konfiguraci p´asky ∆w∆ω . (0, ∆abbbaabaa∆ω , 1) ` (1, ∆abbbaabaa∆ω , 2) ` (2, ∆abbbaabaa∆ω , 3) ` (3, ∆abbbaabaa∆ω , 4) ` (3, ∆abbbaabaa∆ω , 5) ` (3, ∆abbbaabaa∆ω , 6) ` (1, ∆abbbaabaa∆ω , 7) ` (2, ∆abbbaabaa∆ω , 8) ` (3, ∆abbbaabaa∆ω , 9) ` (1, ∆abbbaabaa∆ω , 10) ` (2, ∆abbbaabaa∆ω , 11) ` (5, ∆abbbaabaa∆ω , 10) ` (6, ∆abbbaaba∆ω , 10) ` (5, ∆abbbaaba∆ω , 9) ` (6, ∆abbbaab∆ω , 9) ` (5, ∆abbbaab∆ω , 8) ` (6, ∆abbbaa∆ω , 8) ` (5, ∆abbbaa∆ω , 7) ` (6, ∆abbba∆ω , 7) ` (5, ∆abbba∆ω , 6) ` (6, ∆abbb∆ω , 6) ` (5, ∆abbb∆ω , 5) ` (6, ∆abb∆ω , 5) ` (5, ∆abb∆ω , 4) ` (6, ∆ab∆ω , 4) ` (5, ∆ab∆ω , 3) ` (6, ∆a∆ω , 3) ` (5, ∆a∆ω , 2) ` (6, ∆∆ω , 2) ` (5, ∆∆ω , 1) ` (7, ∆∆ω , 2) ` (8, ∆Y ∆ω , 2) ` (8, ∆Y ∆ω , 1) Dan´e slovo w je generov´ ano gramatikou G4 n´asleduj´ıc´ı posloupnost´ı derivac´ı: S ⇒ aA ⇒ abB ⇒ abbB ⇒ abbbB ⇒ abbbaS ⇒ abbbaaA ⇒ abbbaabB ⇒ abbbaabaA ⇒ abbbaabaa. 4