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ž /.je rekursivní ■ nerozhodnutelný, právě když L není rekursivní ■ částečně rozhodnutelný (semirozhodnutelný), právě když Z_ 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 e {0,1}* \ \ w\ je dělitelná 13} IB102 Automaty, gramatiky a složitost, 30.11.2015 10/25 Redukce - Intuice IB102 Automaty, gramatiky a složitost, 30.11.2015 Turingovy stroje a funkce Jednopáskový deterministický Turingův stroj lze vnímat jako funkci, jejíž hodnotou pro daný vstup je obsah pásky po skončení výpočtu. Přesněji, pokud stroj M na vstupu w zastaví s obsahem pásky >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 0(*) = 1 pokud x = (M,w) a výpočet .M na w je konečný _L jinak 1 pokud x = w) a výpočet .M 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 jsou jazyky. Řekneme, že /A se m-redukuje na e, píšeme A >4 je rekursivní. ■ B\e rekursivně spočetný =4> /A je rekursivně spočetný. Důkaz. Nechť f je redukce A na a .Me je TM akceptující R Stroj .M/\ akceptující /A na vstupu w D spočítá f(w) B spustí .Me na vstupu f(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, 30.11.2015 Redukce a rozhodnutelnost Důsledek. Nechť A B není rekursivní. ■ A není rekursivně spočetný =4> není rekursivně spočetný. Důsledek. Nechť A =m fí. ■ /A je rekursivní <^> je rekursivní. ■ A je rekursivně spočetný <=^> 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 w# > q'w# ... # > ... qacc... # IB102 Automaty, gramatiky a složitost, 30.11.2015