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, 30.11.2015 1/25 Rozhodnutelnost problémů Definice. Problém P odpovídající jazyku L = {(O) | O má vlastnost P} je ■ rozhodnutelný, právě když L\e rekursivní ■ nerozhodnutelný, právě když L není rekursivní ■ částečně rozhodnutelný (semirozhodnutelný), právě když L je rekursivně spočetný IB102 Automaty, gramatiky a složitost, 30.11.2015 2/25 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, 30.11.2015 3/25 Věta. Problém akceptování je nerozhodnutelný. Důkaz. (Sporem:) 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ěď 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, 30.11.2015 4/25 Diagonalizace IB102 Automaty, gramatiky a složitost, 30.11.2015 Problémy a jazyky: přehled terminologie Problém Jazyk Má objekt 0 vlastnost P? {(0) | 0 má vlastnost P} je rozhodnutelný je rekursivní, tj. 3 úplný TM, který ho akceptuje, tj. 3 TM, který ho rozhoduje je nerozhodnutelný není rekursivní je částečně rozhodnutelný neboli semirozhodnutelný je rekursivně spočetný, tj. 3 TM, který ho akceptuje je rozhodnutelný <=^> je částečně rozhodnutelný a jeho doplněk taky je rekursivní <^> je rekursivně spočetný a jeho doplněk taky IB102 Automaty, gramatiky a složitost, 30.11.2015 6/25 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. Důsledek. Třída rekursivně spočetných jazyků není uzavřená na doplněk. IB102 Automaty, gramatiky a složitost, 30.11.2015 7/25 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, 30.11.2015 8/25 Věta. Problém zastavení je nerozhodnutelný. Důkaz. (Sporem:) 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 M! 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, 30.11.2015 9/25 Redukce - Intuice A = {w e {0,1}* | \w\ je dělitelná 26} B = {w yuu (kde y nekončí na u), pak y označíme jako M(w). IB102 Automaty, gramatiky a složitost, 30.11.2015 12/25 Vyčíslitelné funkce Definice. Funkce f: 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, 30.11.2015 13/25 Příklady f{x) = 1 pokud x = (M, w) a výpočet M na w je konečný 0 jinak 000 = 1 pokud x = (M,w) a výpočet .M na w je konečný _L jinak 1 pokud x = (M, w) a výpočet na w není konečný _L jinak k(x) = [ 1 pokud x = a výpočet .M na w skončí po nejvýše 100 krocích [ 0 jinak IB102 Automaty, gramatiky a složitost, 30.11.2015 14/25 Redukce Definice. Nechť A c Z* a B c 0* jsou jazyky. Řekneme, že >4 se m-redukuje na 6, píšeme A • O* taková, že Funkci / nazveme redukcí A na B. >4 a S jsou m-ekvivalentní, psáno A =m B, pokud /A /A je rekursivní. ■ B\e rekursivně spočetný =^> A je rekursivně spočetný. Důkaz. Nechť f je redukce A na 6 a A^e je TM akceptující 6. Stroj Ma akceptující A na vstupu w □ spočítá /"(i/i/) H spustí A^e na vstupu /"(i/i/) a vrátí stejný výsledek jako A^e Je-li Mb úplný, pak je i Ma úplný. IB102 Automaty, gramatiky a složitost, 30.11.2015 Redukce a rozhodnutelnost Důsledek. Nechť A B není rekursivní. ■ A není rekursivně spočetný =4> 6 není rekursivně spočetný. Důsledek. Nechť A =m E. ■ /A je rekursivní <^> 6 je rekursivní. ■ A je rekursivně spočetný <=^> 6 je rekursivně spočetný. IB102 Automaty, gramatiky a složitost, 30.11.2015 19/25 Typické aplikace ■ důkaz (částečné) rozhodnutelnosti A ■ důkaz nerozhodnutelnosti B IB102 Automaty, gramatiky a složitost, 30.11.2015 20/25 Problém neprázdnosti Problém neprázdnosti je problém rozhodnout, zda daný TM akceptuje neprázdný jazyk. NONEMPTY = {(M) \ M je TM a L(M) ^ 0} Věta. Problém neprázdnosti není rozhodnutelný. Důkaz. ACC kde P' má řešení P má řešení začínající 1. p={ ba b b bab b i bb i abb i a IB102 Automaty, gramatiky a složitost, 30.11.2015 ACC w# > (fw# ... # > ... qacc ■ ■ ■ # IB102 Automaty, gramatiky a složitost, 30.11.2015