Turingovy stroje a jazyky TM M akceptuje/rozpoznává/přijímá jazyk L(M). Jazyk L(M) je rekursivně spočetný. Je-li TM M úplný, říkáme, že M rozhoduje jazyk L(M). Jazyk L(M) je rekursivní. Věta. Jazyk ke akceptovaný Turingovým strojem, právě když je generovaný nějakou (frázovou) gramatikou. Důkaz. Neuveden. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 1/30 Uzáverové vlastnosti rekursivních a rekursivně spočetných jazyků Věta. Rekursivně spočetné i rekursivní jazyky jsou uzavřené na sjednocení. Důkaz. Nechť /.-i, Z-2 jsou jazyky akceptované TM M\, M2 s disjunktními množinami stavů. Stroj M akceptující u L2 se nedeterministicky rozhodne, zda na svém vstupu spustí M\ nebo A^2- Pokud spuštěný stroj akceptuje nebo zamítne, stroj M udělá totéž. Pokud M\, M2 byly úplné, je i M úplný. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 2/30 Uzáverové vlastnosti rekursivních a rekursivně spočetných jazyků Věta. Rekursivně spočetné i rekursivní jazyky jsou uzavřené na průnik. Důkaz. Nechť /.-i, Z-2 jsou jazyky akceptované TM M\, M2 s disjunktními množinami stavů. Stroj M akceptující n L2 spustí na svém vstupu w nejprve M\ a pokud akceptuje, pak na w spustí i AÍ2- M akceptuje jen pokud oba stroje akceptují. Pokud , M2 byly úplné, je i M úplný. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 3/30 Uzáverové vlastnosti rekursivních a rekursivně spočetných jazyků Věta. Rekursivně spočetné i rekursivní jazyky jsou uzavřené na zřetězení. Důkaz. Nechť Li, Z-2 jsou jazyky akceptované TM M\, M2 s disjunktními množinami stavů. Dvojpáskový stroj M akceptující Z.1 ./_2 vstupní slovo nedeterministicky rozdělí na dvě části, každou část dá na jednu pásku). Na první části slova spustí M\. Pokud akceptuje, spustí na druhé části AÍ2- M akceptuje jen pokud oba stroje akceptují. Pokud M\, Mz byly úplné, je i M úplný. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 4/30 Uzáverové vlastnosti rekursivních a rekursivně spočetných jazyků Věta. Rekursivně spočetné i rekursivní jazyky jsou uzavřené na iteraci. Důkaz. Nechť /.-i je jazyky akceptovaný TM M^. Zkonstruujeme dvojpáskový TM M rozpoznávající Ľv M akceptuje, pokud je na první pásce prázdné slovo. V opačném případě nedeterministicky přesune nějaký neprázdný prefix slova z první pásky na druhou pásku, kde nad ním spustí M\. Pokud M\ zamítne, tak i M zamítne. Jinak opakuje celou proceduru. Je-li M\ úplný, je i M úplný. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 5/30 Uzáverové vlastnosti rekursivních a rekursivně spočetných jazyků Věta. Rekursivní jazyky jsou uzavřené na doplněk. Důkaz. Nechť Li je jazyky akceptovaný úplným TM M\. Úplný stroj M rozhodující co-Li získáme záměnou akceptujícího a zamítajícího stavu. IB102 Automaty, gramatiky a složitost, 25.11.2013 Uzávěrové vlastnosti rekursivních a rekursivně spočetných jazyků Věta. Třída rekursivně spočetných jazyků není uzavřená na doplněk. Důkaz. Provedeme později. □ Třída rekursivně spočetných jazyků je uzavřená na sjednocení, průnik, zřetězení, iteraci, pozitivní iteraci, mocniny. Třída rekursivních jazyků je uzavřená na sjednocení, průnik, zřetězení, iteraci, pozitivní iteraci, mocniny, doplněk. IB102 Automaty, gramatiky a složitost, 25.11.2013 7/30 Vztah rekursivních a rekursivně spočetných jazyků Věta. Jazyk L je rekursivní, právě když jsou jazyky L a co-L rekursivně spočetné. Důkaz. "=4>" plyne z uzavřenosti rekursivních jazyků na komplement a z toho, že každý rekursivní jazyk je i rekursivně spočetný. "<==": Nechť M\, M2 jsou TM rozponávající L a co-/.. Sestrojíme dvojpáskový stroj M rozhodující L M nejprve zkopíruje vstupní slovo w na druhou pásku. Pak paralelně vykonává běh M\ na první pásce a běh stroje M2 na druhé pásce. Pokud stroj akceptuje, pak w e La stroj M také akceptuje. Pokud stroj M2 akceptuje, pak w 0 L a stroj M zamítá. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 8/30 Problémy jako jazyky Problém rozhodnout, zda daný řetězec w má vlastnost P lze ztotožnit s množinou {w | w má vlastnost P}. Objekty O lze kódovat jako slova (O). Problém, zda O má vlastnost P ztotožníme s jazykem {(O) | O má vlastnost P}. Příklad. Problém rozhodnout, zda daný konečný graf je souvislý, ztotožníme s jazykem {(G) | G je konečný souvislý graf}. IB102 Automaty, gramatiky a složitost, 25.11.2013 9/30 Kódování TM Každý TM lze zakódovat do binárního řetězce. Předpokládáme, že M ■ má stavy Q = {qA, cfe, cfe,..., qn} ■ Qi je iniciál ní stav, q2 akceptující stav, q3 zamítající stav ■ má páskovou abecedu l~ = {X1, X2,..., Xz] ■ X1 = > je levá koncová značka, X2 = u je symbol pro prázdné pol Přechod S(qh Xj) = (qk, Xh L) kódujeme řetězcem 0''1 (V 10*10710. Přechod S{qhXf) = (tfr,X/, R) kódujeme řetězcem OMCVIO^IO'lOO. Z kódů jednotlivých přechodů (v libovolném pořadí) sestavíme kód .M: (A4) = 111 kódA 11 /cdd2 11 ... 11 kódr 111 Řetězce nekódující žádný TM považujeme za kód TM akceptujícího 0. Slova kódujeme podobně. Celkem (M, w) = (M)#(w). IB102 Automaty, gramatiky a složitost, 25.11.2013 Univerzální Turingův stroj Věta. Existuje univerzální Turingův stroj U, který dokáže simulovat libovolný zadaný TM na zadaném vstupu: U akceptuje (M)#(w) <=^> M akceptuje w Důkaz. Stroj U je třípáskový. Nejprve ověří, že vstup je tvaru {0,1 }*#{0,1 }* (pokud ne, zamítá). Na první pásce je kód simulovaného stroje M, na druhé pásce probíhá jeho výpočet, na třetí je uložen jeho stav. V každém kroku se na základě simulovaného stavu a obsahu pásky najde na první pásce příslušný přechod, který se pak provede. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 11/30 Rozhodnutelnost problémů Definice. Problém P odpovídající jazyku L = {(O) | O má vlastnost P} je ■ rozhodnutelný, právě když Z_je rekursivní ■ nerozhodnutelný, právě když /.je není rekursivní ■ částečně rozhodnutelný (semirozhodnutelný), právě když L je rekursivně spočetný IB102 Automaty, gramatiky a složitost, 25.11.2013 12/30 Problém akceptování Problém akceptování (problém příslušnosti pro Turingovy stroje) je problém rozhodnout, zda daný TM M akceptuje dané slovo w nad jeho vstupní abecedou. Problém ztotožníme s jazykem ACC={(M, w) | M je TM a M akceptuje w}. Věta. Problém akceptování je částečně rozhodnutelný. Důkaz. Plyne z existence univerzálního Turingova stroje. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 13/30 Věta. Problém akceptování je nerozhodnutelný. Důkaz. Předpokládejme, že existuje TM A rozhodující problém akceptování. Tedy A akceptuje {M,w), právě když M akceptuje w. S využitím A zkonstruujeme TM V: dostane-li V na vstupu zakódovaný stroj (M), zeptá se stroje A, zda M akceptuje svůj vlastní kód (M) a následně odpověd otočí. Tedy V akceptuje (M), pokud M neakceptuje (M) a V neakceptuje (M), pokud M akceptuje (M). Nyní spustíme V na vstupu (V)\ V akceptuje (V), pokud V neakceptuje (V) a V neakceptuje (V), pokud V akceptuje (V). To je spor. Stroj A tedy neexistuje a problém akceptování je nerozhodnutelný. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 14/30 Ne-semirozhodnutelné problémy Věta. Doplněk problému akceptování není ani částečně rozhodnutelný, tedy co-ACC není rekursivně spočetný. Důkaz. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 15/30 Problém zastavení Problém zastavení (halting problém) je problém rozhodnout, zda daný TM M má na daném slově w nad jeho vstupní abecedou konečný výpočet (tedy zda M na vstupu w zastaví). Problém ztotožníme s jazykem HALT={{M, w) | M je TM a výpočet M na w je konečný}. Věta. Problém zastavení je částečně rozhodnutelný. Důkaz. Pomocí univerzálního Turingova stroje simulujeme M na w. Pokud simulovaný výpočet skončí, akceptujeme. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 16/30 Věta. Problém zastavení je nerozhodnutelný. Důkaz. Předpokládejme, že existuje úplný TM H rozhodující problém zastavení. Pak ovšem umíme sestrojit TM A rozhodující problém akceptování. Stroj A dekóduje dvojici {M, w) ze vstupu a změní M tak, že místo přechodů do zamítajícího stavu začne cyklit. Modifikovaný stroj Mf zastaví, právě když M akceptuje. Nyní stačí spustit H na vstupu (M', w). Dostáváme tedy úplný TM A rozhodující problém akceptování. To je spor. Úplný stroj H tedy neexistuje. □ IB102 Automaty, gramatiky a složitost, 25.11.2013 17/30 Redukce - Intuice IB102 Automaty, gramatiky a složitost, 25.11.2013 Turingovy stroje a funkce Turingův stroj může reprezentovat i funkci. Výsledek je na výstupní pásce při akceptování. Pokud stroj M na vstupu w zastaví s obsahem pásky \>yuu (kde y nekončí na u), pak y označíme jako M(w). f : Z* -> 0 9 : Nj -> N0 IB102 Automaty, gramatiky a složitost, 25.11.2013 19/30 Vyčíslitelné funkce Definice. Funkce /: Z* * je vyčíslitelná, pokud existuje TM M, který na vstupu w zastaví, právě když f{w) je definovaná a navíc f(w) = M(w). Funkce je totálně vyčíslitelná, pokud je vyčíslitelná a totální. IB102 Automaty, gramatiky a složitost, 25.11.2013 20/30 Redukce Definice. Nechť KTaBcr jsou jazyky. Řekneme, že A se m-redukuje na B, píšeme A * taková, že iv G >A G B. Funkci / nazveme redukcí A na B. /A a B jsou m-ekvivalentní, psáno >A =m B, pokud /\ >4 je rekursivní. ■ B\e rekursivně spočetný =^> A je rekursivně spočetný. Důkaz. Nechť / je redukce A na B a .Me je TM akceptující fí. Stroj M a akceptující A na vstupu w D spočítá /(w) B spustí M b na vstupu /(w) a vrátí stejný výsledek jako M b Je-li A^íe úplný, pak je i M a úplný. IB102 Automaty, gramatiky a složitost, 25.11.2013 Redukce a rozhodnutelnost Důsledek. Nechť A B není rekursivní. ■ A není rekursivně spočetný =4> fí není rekursivně spočetný. Důsledek. Nechť A =m fí. ■ /A je rekursivní <^> fí je rekursivní. ■ A je rekurisvně spočetný <=^> fíje rekursivně spočetný. IB102 Automaty, gramatiky a složitost, 25.11.2013 23/30 HALT =m ACC HALT = {(M, w) | M je TM a výpočet M na w je konečný} /ACC = {(M, w) j X je TM a M akceptuje w} HALT