Teorie vyčíslitelnosti. Konečné automaty jsou dobrým modelem takových zařízení, která využívají jen velmi málo paměti. Zásobníkové automaty mají k dispozici teoreticky neomezeně velkou paměť, ale lze ji využívat jen v režimu LIFO (last in – first out) - PowerPoint PPT Presentation
41
Teorie vyčíslitelnosti Konečné automaty jsou dobrým modelem takových zařízení, která využívají jen velmi málo paměti. Zásobníkové automaty mají k dispozici teoreticky neomezeně velkou paměť, ale lze ji využívat jen v režimu LIFO (last in – first out) K řešení mnoha praktických úloh vystačíme s KA a ZA, ale současně víme, že i poměrně jednoduše definované jazyky (například L = {a i b i c i |i1} ) nelze těmito zařízeními rozpoznávat. Potřebujeme tedy nutně ještě obecnější model.
Transcript
Teorie vyčíslitelnosti
Konečné automaty jsou dobrým modelem takových zařízení, která využívají jen velmi málo paměti.
Zásobníkové automaty mají k dispozici teoreticky neomezeně velkou paměť, ale lze ji využívat jen v režimu LIFO (last in – first out)
K řešení mnoha praktických úloh vystačíme s KA a ZA, ale současně víme, že i poměrně jednoduše definované jazyky (například L = {aibici |i1} ) nelze těmito zařízeními rozpoznávat.
Potřebujeme tedy nutně ještě obecnější model.
Turingův stroj
Byl navržen Alanem Turingem (1912-1954) v roce 1936
Má neomezenou paměť (pásku), tj. páska může být libovolně dlouhá
Z pásky symboly nejen čte, ale také si na pásku zapisuje
Čtecí (a současně i zapisovací) hlava se nad páskou pohybuje v obou směrech
Má přijímací stav qaccept, a zamítací stav qreject, jejichž dosažením je určen výsledek výpočtu
Může se stát, že stroj nedosáhne ani přijímacího ani zamítacího stavu a v takovém případě se zacyklí, neustále provádí příslušné kroky a nikdy se nezastaví
Turingův stroj
DEF: Turingův stroj M je sedmice M=(Q, , , , q0, qaccept, qreject), kde
Q je konečná množina vnitřních stavů stroje je konečná množina vstupních symbolů neobsahující prázdný znak Ø ( „mezeru“), je konečná množina páskových symbolů, pro kterou platí Ø a je přechodová funkce : Qx Qxx{L,R}q0 je počáteční stav stroje (q0Q)
qaccept je přijímací stav stroje (qaccept Q)
qreject je zamítací stav stroje (qrejectQ)
Turingův stroj
Také Turingův stroj pracuje po krocích (taktech).
Činnost stroje je určena přechodovou funkcí .
Příklad: : (q1,c) (q2,x,R)
Ve stavu q1 a při čtení symbolu c přejdi do stavu q2, na pásku zapiš symbol x a posuň hlavu o jedno políčko doprava.
a b c d e f
q1
1 krok
a b x d e f
q2
Turingův stroj
DEF: Konfigurací Turingova stroje rozumíme zápis uqv, kde u je dosud přečtená část vstupního slova, q je aktuální vnitřní stav stroje a hlava stroje se nachází nad prvním písmenem dosud nepřečtené části slova v.
abq1cdef abxq2def
Počáteční konfigurací TS je konfigurace q0w, tj. TS je v počátečním stavu a hlava je nad prvním písmenem vstupního slova
a b c d e f
q1
1 krok
a b x d e f
q2
Turingův stroj
Poznámka: Předpokládáme, že vstupní slovo w je zapsáno na prvních n. TS začíná svoji práci na prvním políčku pásky a pokud by se kdykoliv v průběhu výpočtu chtěl posunout z tohoto pole ještě více vlevo (i kdyby mu to předepisovala přechodová funkce ), nepovede se to a hlava zůstane nad prvním políčkem pásky.
Koncovou konfigurací TS je libovolná konfigurace, při které je TS ve stavu qaccept (přijímající koncová konfigurace) nebo qreject (zamítající koncová konfigurace)
a b c d e f
q1
X
OK
..…
Turingův stroj
Analogicky jako v předchozích případech definujeme relaci přechodu, která koresponduje s jedním krokem TS.
DEF: Buď M =(Q,,,,q0,qaccept,qreject) Turingův stroj. Potom nad množinou všech konfigurací definujeme relaci přechodu pro q1,q2Q, u,w *, a,b,c následovně:
uaq1bw uq2acw jestliže (q1,b)= (q2,c,L)
respektive (při posunu hlavy doprava)uaq1bw uacq2w jestliže (q1,b)= (q2,c,R)
Již popsaná zvláštní situace na levém konci pásky znamená:q1aw q2bw jestliže (q1,a)= (q2,b,L)
Turingův stroj
Na pravém konci pásky žádný problém nevzniká, protože předpokládáme, že páska je neomezeně dlouhá a je vyplněna mezerami (symbol Ø, resp. ), a proto:
waq1 je totéž jako waq1Ø
a není nutné přijímat žádné další opatření, protože Ø .
DEF: Turingův stroj M =(Q,,,,q0,qaccept,qreject) přijímá slovo w, jestliže existuje posloupnost konfigurací
q0w * uqacceptv
Turingův stroj
DEF: Turingův stroj M =(Q,,,,q0,qaccept,qreject) zamítá (nepřijímá) slovo w, jestliže existuje posloupnost konfigurací
q0w * uqrejectv
nebo pokud se při výpočtu zacyklí a nikdy nezastaví.
Poznámka: Zatímco přijetí slova je zřejmé (v konečném čase
dostaneme na otázku zda wL odpověď ANO), zamítnutí je obtížnější. Po konečném čase můžeme dostat odpověď NE (TS se dostal
do stavu qreject a ukončil výpočet), ale my dopředu nevíme, jak dlouho máme čekat, a ukončení výpočtu uživatelem v libovolném čase T může znamenat pouze nedostatek trpělivosti.
Rozpoznatelnost vs. rozhodování
DEF: Turingův stroj M =(Q,,,,q0,qaccept,qreject) rozpoznává jazyk L, jestliže přijímá všechna slova jazyka L a nepřijímá slova, která do tohoto jazyka nepatří.
(Někdy se namísto „rozpoznává“ uvádí termín TS „přečísluje“ jazyk)
Poznámka: U slov, která nepatří do jazyka L není důležité, zda je Turingův stroj zamítne skrze zamítací konfiguraci, nebo zda se výpočet zacyklí (tj. požadujeme pouze, aby se pro wL stroj zastavil v přijímací stavu).
DEF: Jazyky rozpoznatelné Turingovým strojem se nazývají rekurzivně vyčíslitelné (či rekurzivně spočetné).
Rozpoznatelnost vs. rozhodování
DEF: Turingův stroj M =(Q,,,,q0,qaccept,qreject) rozhoduje jazyk L, jestliže se pro každé slovo w * výpočet stroje po konečném počtu kroků zastaví.
Poznámka: U slov, která patří do jazyka L, skončí výpočet v přijímací konfiguraci a u slov, která do L nepatří, skončí v zamítací konfiguraci (tj. požadujeme jasnou odpověď typu ANO-NE).
DEF: Jazyky rozhodnutelné Turingovým strojem se nazývají rekurzivní.
Rozpoznatelnost vs. rozhodování
Je zřejmé, že každý turingovsky rozhodnutelný jazyk je turingovsky rozpoznatelný, neboli množina rekurzivních jazyků je podmnožinou rekurzivně spočetných jazyků.
Existují jazyky, které jsou rekurzivně spočetné (turingovsky rozhodnutelné), ale nikoliv rekurzivní
Existují ovšem i jazyky, které jsou turingovsky nerozhodnutelné
Rekurzivně spočetné jazyky
Rekurzivní jazyky
Příklady TS
Příklad 1: Sčítačka dvou přirozených čísel.Čísla jsou uložena na pásce za sebou tak, že číslo n reprezentuje n+1 znaků x a oddělena jsou znakem #
Myšlenka: Smažu prostřední znak # a poté smažu poslední dva znaky x (jeden prázdný, druhý #)(zbyde mi n+1+1+m+1-2=n+m+1 znaků x)
Příklady TS
Postup výpočtu (4+2=6): 1. q0xxxxx#xxx# 8. xxxxxxxq1xx#
Stejnou úlohu by uměl vyřešit i zásobníkový automat
Jde o jazyk L={xi#xj# |i,j>0}
Otázka: Daný Turingův stroj jazyk L rozpoznává nebo rozhoduje?
Příklady TS
Pro jednoduchost obvykle nekreslíme do obrázku stav qreject, ale většinou je zřejmé, jak jej doplnit.
Stačí, když u každého stavu, kde není definován přechod pro některý symbol z doplníme přechod do stavu qreject a ohodnotíme ji příslušným symbolem z (na nově zapisovaném symbolu nezáleží).
Příklady TS
Po doplnění chybějícího stavu a příslušných šipek je zřejmé,že tento TS rozhoduje jazyk L={xi#xj# |i,j>0}.
Příklady TS
Příklad 2: TS rozpoznávající (rozhodující) jazyk L={w#w|w{0,1}*}
Myšlenka: Smažu první 1 nebo 0 (přepíšu např. na x), pokračuji až za oddělovací # a potom zkontroluji první znak druhého slova. Je-li správný, přepíšu jej na x a jedu zpět pro druhý znak prvního slova atd. Kyvadlově pokračuji až dokud při čtení prvního slova nenarazím na znak # a poté již jen zkontroluji,že z druhého slova žádný znak na pásce nezbyl (jsou tam jen samá x)
Poznámka: Turingovy stroje (TS) již jsou poměrně komplikované pro zcela detailní formální popis jako tomu bylo v případě KA a ZA.
Proto je obvyklé, že popis TS je proveden pouze na obecné úrovni (princip činnosti) a teprve jestliže je to skutečně potřebné, přistupuje se k detailní formální definici.
Většinou se tedy spokojíme s popisem činnosti stroje na úrovni „myšlenky“a pokud je realizace této myšlenky zřejmá, již ji dále nerozpracováváme.
Další příklady TS
Příklad 3: Navrhněte TS rozpoznávající (rozhodující) jazyk
L={02n |n0}
Myšlenka: Stroj M na vstupní slovo w 1. jede vpravo a každý druhý symbol 0 přepíše na x2. pokud páska obsahovala jedinou 0, potom accept3. pokud páska obsahovala více než jedinou 0 a
počet nul je lichý, potom reject4. návrat hlavy na začátek pásky (zpět úplně vlevo)5. pokračuj krokem číslo 1
Další příklady TS
Příklad 4: Navrhněte TS rozpoznávající (rozhodující) jazyk
L={aibjck |i,j,k1 a současně i×j=k}
Myšlenka: Stroj M na vstupní slovo w 1. ověří, zda na pásce je slovo a+b+c+, jinak reject 2. návrat hlavy na začátek pásky (zpět úplně vlevo)3. přepiš první a na x a potom přejdi na první b. „Cestuj
mezi b-čky a c-čky a škrtej obojí dokud zbývá nějaké b. Pokud dojdou c-čka předčasně, potom reject.
4. zrekonstruuj sekvenci b-ček a potom pokračuj krokem 3 jestliže na pásce zbývá ještě nějaký symbol a. Pokud ne, zkontroluj, zda na pásce už není ani žádné c. Pokud není, potom accept, jinak reject.
Shrnutí příkladů
Všechny dosud uvedené příklady jazyků byly rekurzivní, tj. existuje Turingův stroj který příslušný jazyk rozhoduje.
Samozřejmě,že tyto jazyky jsou automaticky i rekurzivně spočetné, protože nutně existuje Turingův stroj, který je rozpoznává.
Existují jazyky, které jsou rekurzivně spočetné, ale nejsou rekurzivní.
Varianty TS
Turingův stroj je velmi robustní model, neboť se ukazuje, že celá řada variant TS, které využívají jistého rozšíření, má naprosto shodnou výpočetní sílu.
Co když například umožníme Turingovu stroji při výpočtu vykonávat nejen posunout vlevo a vpravo, ale i zůstat na stejné pozici?
Tj., přechodová funkce bude mít tvar
: Qx Qxx{L,R,S}, kde S znamená „zůstaň“
Takový TS bude rozpoznávat zcela stejnou třídu jazyků, protože „setrvání“ na místě lze snadno nasimulovat na „standardním“ TS pomocí dvou po sobě jdoucích přechodů (jdi vpravo a potom jdi vlevo).
Varianty TS
Vícepáskový Turingův stroj má na rozdíl od zde již definovaného TS k dispozici hned několik pásek.
Každá páska má vlastní čtecí/zapisovací hlavu.Přechodová funkce je upravena tak, aby bylo možné
pracovat na několika nebo dokonce všech páskách současně:
: Qxk Qx k x{L,R,S} k, kde k je počet pásek
Potom například výraz:
(qi,a1,..,ak)= (qj,b1,..,bk,L,R,…,R)
předepisuje, že pokud je TS ve stavu qi, na první pásce čte symbol a1, na druhé ….., potom přejde do stavu qj, na první pásku zapíše symbol b1 a posune příslušnou hlavu vlevo, …
Varianty TS
Ačkoliv vícepáskový TS se na první pohled zdá být mocnější,není tomu tak.
Věta: Ke každému vícepáskovému TS lze sestrojit ekvivaletní TS s jedinou páskou.
Důkaz: Činnost vícepáskového TS lze simulovat na jediné pásce tak, že obsahy k pásek napíšeme za sebe a oddělíme vhodným oddělovačem (#).
Dále je nutné simulovat činnost k hlav,a proto musím znát jejich pozici nad danou částí pásky. K tomu se obvykle použije nějaký vhodný znak (tečka nad symbolem atd.). Do páskové abecedy je potom nutné přidat všechny znaky originální plus tytéž znaky s tečkou.
Varianty TS
Ačkoliv vícepáskový TS se na první pohled zdá být mocnější,není tomu tak.
q1
a b a a b
q1
..…
c c c ..…
a a ..…
a b a a b #c c c #a a # ..…
Simulace vícepáskového TS
TS prochází pásku a zjišťuje symboly pod virtuálními hlavami (ty jsou označené tečkou)
Při dalším průchodu mění (zapisuje) symboly dle přechodové funkce a současně posunuje i virtuální hlavy (posunuje „tečky“ nad příslušnými symboly)
Při práci může zjistit, že na některé z pásek (v některém úseku) nemá dostatek místa k zapisování (pozná tak,že dojde na symbol #), potom zapíše do tohoto políčka pásky mezeru a posune všechny symboly počínaje znakem # až po poslední # na pásce o 1 políčko vpravo.Tím si vytvoří v daném úseku místo a poté pokračuje dále v simulaci.
Varianty TS
Nedeterministický Turingův stroj nemá jednoznačně definovanou přechodovou funkci, ale pracuje se zobrazením : Qx P(Qx x{L,R})
V některých krocích výpočtu se tento výpočet dělí do více větví a pokud alespoň jedna větev dojde do stavu qaccept, je výpočet úspěšný.
Ani nedeterminismus nerozšiřuje možnosti TS.
Věta: Ke každému nedeterministickému TS lze sestrojit ekvivaletní deterministický TS.
Varianty TS
Důkaz: Sestrojíme deterministický TS, který simuluje činnost nedeterministického TS na třech páskách.
Na vstupní pásce je slovo w, které se nemění. Slovo w se překopíruje na pásku simulační a zde se s ním pracuje. Pokud dojde k větvení, zapíše se příslušná konfigurace na adresní
pásku, kde čeká na vyřízení (odsimulování) požadavku Pozor – nelze provést prohledáváním do hloubky! Hrozí zacyklení!
0 0 1 1
qx
..…
x x #0 1 1 x ..…
1 2 2 1 ..…
x
3 1 1 2 3 1 2
..… vstupní páska
..… simulační páska
..… adresní páska
Varianty TS
Jiná definice umožňuje Turingovu stroji využívat oboustranně neohraničenou pásku, ale ani tentokrát se možnosti stroje nezmění.
Pokud ovšem omezíme možnosti TS tak, že TS nikdy neopustí políčka pásky, na kterých je napsáno vstupní slovo w, potom jde o lineárně omezený TS a jeho možnosti jsou ve srovnání s TS podstatně menší.
Lze dokázat,že Turingovy stroje rozpoznávají jazyky typu 0 (bez omezení), zatímco lineárně omezené TS rozpoznávají jazyky kontextové (jazyky typu 1).
Ekvivalence s jinými modely
Kromě různých variant Turingova stroje existují i jiné modely (např. RAM – Random Access Machine –stroj s libovolným přístupem, ZA se dvěma zásobníky, či -kalkul), které rozpoznávají stejnou třídu jazyků (neboli jsou ekvivalentní z hlediska výpočetní síly).
Tyto modely mají i přes velkou rozdílnost některé společné rysy (přístup k neomezené paměti, omezený rozsah činnosti,kterou lze vykonat v jediném kroku,atd.)
Přes rozdílnost modelů zůstává tatáž třída jazyků, které lze pomocí příslušných modelů rozpoznávat, což má závažné matematické,filozofické, ale i praktické důsledky.
Ekvivalence s jinými modely
Jakousi paralelou k tomuto zjištění je volba vhodného programovacího jazyka.
Přestože například C++, Pascal či Prolog jsou naprosto rozdílné programovací jazyky, využitím kteréhokoliv z nich dostaneme naprosto stejnou třídu algoritmů, které lze naprogramovat.
Každý jazyk má určité přednosti a výhody, které umožňují programátorovi postupovat někdy rychleji, ale výsledná třída algoritmů je ve všech případech stejná.
Definice algoritmu
Algoritmus je těžké definovat formálně matematicky, přestože matematika algoritmy používá (zjištění prvočísla, nejmenšího společného násobku atd.)
Algoritmus chápeme intuitivně jako určitý postup, proceduru, či recept.
V roce 1936 definoval Alonzo Church algoritmus pomocí formalismu zvaného -kalkul a Alan Turing pomocí „svého“ stroje, přičemž obě definice se ukázaly být ekvivalentními.
Teprve mnohem později (s nástupem skutečných počítačů) se objevuje model RAM, který je bližší našemu chápání počítače, ale přesto je svými možnostmi ekvivalentní TS
Churchova teze
Ať už se na otázku vyčíslitelnosti díváme z jakéhokoliv úhlu, zkoumáme ji použitím různých formalismů, vždy docházíme ke stejnému závěru.
Churchova (Churchova-Turingova) teze:
Každý algoritmus je ekvivalentní s výpočtem příslušného Turingova stroje.
Každý jazyk, který lze popsat konečným výrazem, je rekurzivně spočetný.
Není to matematická věta (jen teze), a proto nelze dokázat.
Churchova teze
Z dnešního pohledu se nám může zdát nepříliš významná, protože jsme obklopeni počítači a máme „jasnou“ představu, co je to algoritmus.
Je třeba mí na paměti, že byla formulována v době, kdy žádné počítače ani programovací jazyky neexistovaly.
Jde o první model, který bylo možné považovat za „programovatelný“.
I přes jistý kriticismus (TS neuvažuje interaktivní výpočty atd.) TS zůstávají pevným základem teorie vyčíslitelnosti.
Příklady TS
Příklad 5: Navrhněte TS rozpoznávající (rozhodující) jazyk
L={aibici |i0}
Myšlenka: ???
Stavový diagram: ???
Příklady TS
Příklad 6: Navrhněte TS, který zdvojí slovo zapsané na vstupní pásce (např. pro vstup abb bude výstupem abbabb)
Myšlenka:
Stavový diagram:
Příklady TS
Příklad 7: Navrhněte TS, který k číslu zapsanému na pásce ve dvojkové soustavě přičte jedničku (např. pro vstup 11100 bude výstupem 11101, pro vstup 11 bude výstupem 100 atd.)
