IB107 Vyčíslitelnost a složitost opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém Jan Strejček Fakulta informatiky Masarykova univerzita vyčíslitelnost funkcí ■ funkce f: Nk -> N je vyčíslitelná když ■ funkce f je totálně vyčíslitelná, je-li vyčíslitelná a dom(f) = Nk IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 2/35 numerace vyčíslitelných funkcí pro každé k > 0 lze všechny vyčíslitelné funkce typu f(k) . N/c N -očíslovat" jako (k) (k) (k) tak, aby platily věta o numeraci věta o parametrizaci IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 3/35 vyčíslitelné vlastnosti množin ■ množina A c Nk je rekurzivní, je-li její charakteristická funkce Xa • ^k -> N vyčíslitelná, kde ■ množina A c Nk je rekurzivně spočetná (r.e.), pokud A = dom(f) pro nějakou vyčíslitelnou funkci ř: -> N ■ problém zastavení /C ■ doplněk problému zastavení (problém nezastavení) K IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 4/35 numerace r.e. množin a uzáverové vlastnosti ■ pro každé k > 0 lze všechny r.e. podmnožiny Nk "očíslovat" jako l/l/0(/c), w\k\ l/l/2(/c\... třída rek. třída r.e. množin množin u, n aplikované na relace stejné arity doplněk kartézský součin x projekce řez vzor při tot. vyčíslitelném zobrazení vzor při vyčíslitelném zobrazení obraz při (tot.) vyčíslitelném zobrazení IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 5/35 další vlastnosti r.e. množin ■ věta o projekci ■ 1. Riceova věta ■ 2. a 3. Riceova věta IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 6/35 množiny a problémy: přehled terminologie problém množina Má objekt 0 vlastnost V? A = {(0)\Omá vlastnost V] Q N je rozhodnutelný A je rekurzivní, tj. xa j^ totálně vyčíslitelná, ? tj. 3 program rozhodující x e A je nerozhodnutelný A není rekurzivní je částečně rozhodnutelný neboli semirozhodnutelný A je rekurzivně spočetná, tj. A = dom(f) pro nějakou vyč. fci f, tj. 3 program, který zastaví jen na vstupech z a, tj. 3 program, který generuje A je rozhodnutelný <=^> je částečně rozhodnutelný a jeho doplněk taky A je rekurzivní <^> /A je rekurzivně spočetná a její doplněk taky IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 7/35 intuice pro redukci A = {ne N | nje dělitelné 13} B= {n e N | nje dělitelné 26} IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 8/35 intuice pro redukci K = {/' e N | A je rekurzivní. B B je rekurzivně spočetná =4> A je rekurzivně spočetná. Důkaz. A B není rekurzivní Q A není rekurzivně spočetná =4> B není rekurzivně spočetná. Důsledek NechíA=m B. O /A ye rekurzivní <^> 6 ye rekurzivní. B >A ye rekurzivně spočetná <=^> 6 ye rekurzivně spočetná. IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 14/35 typické aplikace ■ důkaz (částečné) rozhodnutelnosti A ■ důkaz nerozhodnutelnosti B IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 15/35 r.e. množiny a K Věta Je-li A c N r.e., pak A ); x-| := 1 end IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém těžká a úplná množina Definice (těžká a úplná množina) Necht C je třída podmnožin množiny N a A c N. Řekneme, že A je C-těžká, právě když pro každou množinu B e C platí B , U, Ô, Cfo, Qacc, Qrey), fafe ■ Q ye konečná množina, jejíž prvky nazýváme stavy, ■ Z ye konečná množina, tzv vstupní abeceda, ■ r ye konečná množina, tzv pracovní abeceda, icr, ■ > g r \ Z ye /evá koncová značka, ■ u g r \ Z je symbol označující prázdné políčko, ■ ô : (Q \ {Qacc, Qrey}) x ľ -> Q x ľ x {L, R} je totální přechodová funkce, m q0 g Q je počáteční stav, ■ Qacc e Q 7© akceptující stav, m qrej g Q ye zamítající stav. IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 18/35 Tu ringů v stroj Dále požadujeme, aby pro každé q e Q \ {qacc, q rej} existoval p e Q takový, že 5(q, >) = (p, >, f?) (tj. nelze sjet hlavou z pásky ani přepsat >). Notace: uw = uuuuuu... Definice (konfigurace Turingova stroje) Konfigurace Turingova stroje je trojice (g, z, n) g Q x {yu^ | y g P} x N, taře ■ q ye stóK ■ yuu je obsah pásky, m n značí pozici hlavy na pásce. Počáteční konfigurace pro vstup i^gF je trojice (g0, >wuUJ, 0). Akceptující konfigurace je každá trojice tvaru (qaCc, z,n). Zamítající konfigurace je každá trojice tvaru (grey, z, n). IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 19/35 krok výpočtu Tu ringová stroje Definice (krok výpočtu) Na množině všech konfigurací stroje M definujeme binární relaci krok výpočtu m jako m < (g, z', n + 1) pokud 6(p, zn) = (g, ď, fí) (g, z;, n - 1) pokud 5{p, zn) = (g, ď, L) kde zn je n-tý znak z (přičemž z0 je nejlevější znak z) a z1 vznikl ze z nahrazením znaku zn znakem b. IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 20/35 výpočet Tu ringová stroje Definice (výpočet) Výpočet TM M na vstupu w je maximální (konečná nebo nekonečná) posloupnost konfigurací K0, Kí, K2,..kde K0 je počáteční konfigurace pro w aK, \— K/+1 pro všechna i > 0 ■ stroj M akceptuje slovo w, právě když výpočet M na w je konečný a jeho poslední konfigurace je akceptující ■ stroj M zamítá slovo w, právě když výpočet M na w je konečný a jeho poslední konfigurace je zamítající ■ stroj M pro vstup w cyklí, právě když výpočet M na w je nekonečný ■ jazyk akceptovaný strojem M definujeme jako množinu L(M) = {w g 51* | .m akceptuje 1/1/} IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 21/35 vícepáskový Turingův stroj Věta Pro každý vícepáskový Turingův stroj existuje (jednopáskový) Turingův stroj akceptující stejný jazyk. IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 22/35 nedeterministický Turingův stroj Definice (nedeterministický Turingův stroj) Nedeterministický Turingův stroj M je definován stejně jako det. TM s výjimkou přechodové funkce S, která je definována jako totální funkce ô : (Q\ {QaccQrey}) x l~ 2°^^R\ ■ většina pojmů se definuje stejně jako u deterministického TM ■ v definici kroku výpočtu |— píšeme (q, b, R) e 5(p, zn) namísto 5(p, zn) = (q, ď, f?) a podobně pro (q, ď, L) ■ stroj .m akceptuje slovo w, právě když existuje výpočet M na w, který je konečný a jeho poslední konfigurace je akceptující Věta Pro každý nedeterministický TM existuje deterministický TM akceptující stejný jazyk. IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 23/35 Turingovy stroje a třídy jazyků Věta Jazyk L je rekurzivně spočetný neboli re. (tj. generovaný gramatikou typu 0) <=^> L je akceptovaný nějakým Turingovým strojem. Definice (úplný Turingův stroj, rekurzivní jazyk) Turingův stroj se nazývá úplný, je-li každý jeho výpočet konečný (akceptující nebo zamítající). Jazyk se nazývá rekurzivní, pokud je akceptovaný nějakým úplným Turingovým strojem. Terminologie ■ (obecný) TM M akceptuje/rozpoznává/přijímá jazyk L(M) ■ úplný TM M rozhoduje jazyk L(M) IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 24/35 uzáverové vlastnosti rekurzivních a r.e. jazyků třída rek. třída r.e. jazyků jazyků u, n zřetězení, mocniny (pozitivní) iterace doplněk Věta Jazyk L je rekurzivní, právě když jsou jazyky La L r.e. IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 25/35 kódování a univerzální Turingův stroj ■ každý TM M lze zakódovat do řetězce (M) e {0,1 }* ■ každé slovo w lze zakódovat do řetězce (w) e {0,1 }* ■ dvojice (M, w) lze zakódovat jako {M, w) = (M)#(w) Věta Existuje univerzální Turingův stroj U, který dokáže simulovat libovolný zadaný TM na zadaném vstupu w: U akceptuje (M, w) M akceptuje w IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 26/35 problém zastavení (halting problem) Definice (problém zastavení) Problém zastavení je problém rozhodnout, zda daný TM M má na daném slově w nad jeho vstupní abecedou konečný výpočet. Problém ztotožníme s jazykem H ALT = {{M,w) | M je TM a výpočet M na w je konečný}. Věta Problém zastavení je částečně rozhodnutelný. Věta Problém zastavení je nerozhodnutelný. IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 27/35 Tu ringový stroje a funkce ■ obsah páskyjednopáskového deterministického Turingova stroje po skončení výpočtu lze vnímat jako jeho výstup ■ pokud stroj M na vstupu w zastaví s obsahem pásky >yuu (kde y nekončí na u), pak y je jeho výstupem značeným M(w) Definice ((totálně) vyčíslitelná funkce) Funkce f: Z* * je vyčíslitelná, pokud existuje TM M, který zastaví právě na vstupech z dom(f) a pro každé slovo w e dom(f) platíM(w) = f(w). Funkce je totálně vyčíslitelná, pokud je vyčíslitelná a totální IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 28/35 redukce jazyků Definice (m-redukce) NechíA c z* a B c * /sol/ jazyky. Řekneme, že A se m-redukuje na B, píšeme A * taková, že w e A <=^> e 6. Funkci f nazveme redukcí A na B. Věta A/ecA?/ /A c Z* a 6 c 0* /sou yazy/cy a/l A je rekurzivní. B 6 je rekurzivně spočetný =4> /A je rekurzivně spočetný. IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 29/35 problém akceptování Definice (problém akceptování) Problém akceptování 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 nerozhodnutelný. Důkaz. H ALT P má řešení začínající 1. p={ ba b b bab b i bb i abb i a IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 34/35 nerozhodnutelnost PCP ACC w# > (fw# ... # > ... qacc ■ ■ ■ # IB107 Vyčíslitelnost a složitost: opakování, redukce, Turingovy stroje a redukce, Postův korespondenční problém 35/35