Redukce – příklady ve cvičeních (řešení) 12.1 Rozhodněte, zda platí následující implikace. Své rozhodnutí zdůvodněte. a) ≤ ⇒ ≤ b) ≤ a B je regulární ⇒ A je regulární. c) A je rekurzivně spočetná a ≤ ⇒ je rekurzivní. d) A je rekurzivně spočetná a ≤ ⇒ je rekurzivní. e) ≤ a A je rekurzivní ⇒ B je rekurzivní f) A je rekurzivně spočetná ⇒ ≤ Řešení: a) Platí. Buď ⊆ Σ∗ , ⊆ Γ∗ . Zopakujme definici m-redukce: ≤ právě tehdy, když existuje totálně vyčíslitelná funkce : Σ∗ → Γ∗ taková, že ∗ ∈ ⟺ ∈ Vztah (*) můžeme upravit: ∉ ⟺ ∉ , resp. ∗∗ ∈ ⟺ ∈ Vztah (**) však odpovídá definici m-redukce ≤ , což bylo dokázat. b) Neplatí. Uvedeme protipříklad. Nechť = { . ∣ ∈ { , }∗ }, ⊆ {0, 1}∗ , = {0}. Jazyk A je rekurzivní, jazyk B regulární. Zkonstruujme funkci : { , }∗ → {0, 1} pro redukci ≤ : ! = 0, je-li ! tvaru . , kde ∈ { , }∗ , ! = 1 jinak. Tato funkce je totálně vyčíslitelná, protože pro ni existuje Turingův stroj M, který rozhoduje jazyk A, tudíž funkci lze na jakémkoliv vstupu z { , }∗ algoritmicky spočítat. Našli jsme tedy neregulární jazyk A a regulární jazyk B, pro něž jsme zkonstruovali redukci ≤ . Spor s tvrzením v zadání. c) Platí. Nejprve uveďme jednu z vlastností m-redukce: (*) Pokud Y rekurzivně spočetný a platí " ≤ #, pak X je též rekurzivně spočetný. Porovnejme vztah (*) s předpoklady věty v zadání: A je rekurzivně spočetná a ≤ . Dle vztahu (*) tedy musí platit, že i jazyk je rekurzivně spočetný. Ukázali jsme, že oba jazyky , jsou rekurzivně spočetné. Z toho však vyplývá, že jazyk A je rekurzivní. d) Platí. Ze vztahu ≤ vyplývá i vztah ≤ (viz definice m-redukce). Dále již postupujeme analogicky jako v případě c). e) Neplatí. Uvažujme následující dva jazyky: = ∅, ⊆ Σ∗ = , tj. jazyk nad abecedou {0, 1, #} obsahující kódy 〈', 〉, kde M je Turingův stroj a výpočet M na slově w je konečný. Sestrojme funkci f, která bude pro jakýkoliv vstup vracet slovo nad abecedou {0, 1, #} nepatřící do B (tedy nebude to smysluplný kód tvaru 〈', 〉). Jde o totálně vyčíslitelnou funkci, přičemž ! ∈ Σ∗ platí ! ∉ ⟺ ! ∉ . Tedy ≤ , přičemž A je regulární, tedy i rekurzivní jazyk, naopak B je pouze rekurzivně spočetný jazyk, nikoliv rekurzivní. f) Platí. Jestliže A je rekurzivně spočetný jazyk, existuje pro něj Turingův stroj M, který je akceptuje. Je-li ⊆ Σ∗ , pak na slovech ∈ Turingův stroj M akceptuje, na slovech ) ∉ zamítá či cyklí. Sestrojíme funkci : Σ∗ → {0, 1, #}∗ takto: = 〈*, 〉, kde N vznikne z M tak, že přechody do stavu +,-. upravíme tak, aby v N cyklily. Taková funkce je určitě totálně vyčíslitelná. Výstup funkce , tj. kód 〈*, 〉 přesměrujeme do Turingova stroje pro jazyk HALT. Jistě platí: 〈', 〉 ∈ ⟺ 〈*, 〉 ∈ ! ∈ ⟺ ! ∈ Našli jsme tedy redukci ≤ . 12.2 Je dán jazyk = {〈'〉 | výpočet TM M na slově 0 je konečný}. • Dokažte, že A není rekurzivní. (Návod: najděte redukci problému zastavení na A.) • Je jazyk A rekurzivně spočetný? • Je komplement jazyka A rekurzivně spočetný? Řešení: Důkaz, že jazyk A není rekurzivní Zopakujme si nejdříve definici jazyku HALT. Jedná se o jazyk nad abecedou {0, 1, #} obsahující kódy 〈', 〉, kde M je Turingův stroj a výpočet M na slově w je konečný. Zkonstruujme funkci : {0, 1, #}∗ → {0, 1, #}∗ , která zobrazí slovo ! = 〈', 〉 na jiné slovo ! = 〈*, 〉 tak, že výpočet M na w je konečný právě tehdy, když výpočet N na 0 je konečný. ! = 〈 1〉, pokud ! ≠ 〈', 〉, kde 1 je TM, který pro každý vstup (tedy i prázdné slovo) cyklí. ! = 〈*, 3〉, pokud ! = 〈', 〉, kde stroj N pro libovolný vstup u sestrojíme takto: 1. Spustíme simulaci stroje M na slově w. 2. Pokud M zastaví svůj výpočet, akceptujeme. Funkce f je určitě vyčíslitelná. • V případě, že vstupem funkce není kód 〈', 〉 Turingova stroje a vstupu, výsledkem je kód stroje 1, který pro každý vstup cyklí. Takový stroj jsme jistě schopni vymyslet. • V opačném případě zkonstruujeme Turingův stroj N, který při své činnosti simuluje činnost stroje M na vstupu w. I takový stroj sestrojíme jednoduše, stejně tak si poradíme s výstupem v případě, že M na vstupu w zastaví. Pokud by výpočet M na w cyklil, 〈', 〉 ∉ , tak bude cyklit výpočet N na libovolném slově u, tedy i 0, tj. 〈*, 3〉 ∉ . Funkce f je též totální, protože je definována pro každý vstup. Jejím výsledkem je vždy řetězec nad abecedou {0, 1, #} reprezentující buď pouze kód TM nebo kód dvojice TM, vstup. Platí: 〈', 〉 ∈ ⟺ 〈*, 3〉 ∈ (Výpočet M na w je konečný ⟺ výpočet N na libovolném slově u, tedy i 0, je konečný) ! ∈ ⟺ ! ∈ ≤ Protože jazyk HALT není rekurzivní, není ani jazyk A rekurzivní. Důkaz, že jazyk A je rekurzivně spočetný Důkaz faktu, že jazyk A je rekurzivně spočetný, provedeme redukcí ≤ 44. Protože je jazyk ACC rekurzivně spočetný, jistě je i jazyk A rekurzivně spočetný. Zkonstruujme funkci ′: {0, 1, #}∗ → {0, 1, #}∗ , která zobrazí slovo ! = 〈'〉 na slovo ) ! = 〈*, 0〉, kde M, N jsou Turingovy stroje, pro které platí, že výpočet M na prázdném slově 0 zastaví právě tehdy, když N akceptuje 0. ) ! = !, není-li x kódem Turingova stroje. ) ! = 〈*, 0〉, je-li ! = 〈'〉, kde N zkonstruujeme následujícím způsobem: 1. Univerzálnímu TM U dáme na vstup dvojici 〈', 0〉. 2. Pokud U akceptuje, stroj N také akceptuje. 3. Pokud U zamítá, stroj N akceptuje. Funkce f‘ je jistě vyčíslitelná. TM N při svém výpočtu využívá univerzálního TM U, který jsme schopni zkonstruovat. Funkce f‘ je totální, je definovaná jak pro špatné vstupy (x není kódem TM), tak pro korektní vstupy (x je kódem TM). Platí: 〈'〉 ∈ ⟺ 〈*, 0〉 ∈ 44 ! ∈ ⟺ ′ ! ∈ 44 ≤ 44 Jazyk A je tedy rekurzivně spočetný. Důkaz, že jazyk co-A není ani rekurzivně spočetný Sporem předpokládejme, že jazyk co-A je rekurzivně spočetný. Protože i jazyk A je rekurzivně spočetný, z faktu, že oba jazyky jsou rekurzivně spočetné, vyplývá, že jazyk A je rekurzivní. To je však spor s naším důkazem, že A není rekurzivní. Proto jazyk co-A není ani rekurzivně spočetný. 12.3 Nalezněte řešení následujícího Postova systému: 67 8 , 9 : , 9 : , 9 :; Řešení: 1343421343222 7 8 ⋅ 9 : ⋅ 9 : ⋅ 9 : ⋅ 9 : ⋅ 9 : ⋅ 7 8 ⋅ 9 : ⋅ 9 : ⋅ 9 : ⋅ 9 : ⋅ 9 : ⋅ 9 : 2243311 9 : ⋅ 9 : ⋅ 9 : ⋅ 9 : ⋅ 9 : ⋅ 7 8 ⋅ 7 8 12.5 Ukažte, že problém ekvivalence dvou Turingových strojů => = {〈'?, '@〉 ∣ '?, '@ jsou ' ∧ '? = '@ } je nerozhodnutelný. Řešení: Z přednášky víme, že jazyk *F*='G # = {〈'〉 ∣ ' je ' ∧ ' ≠ ∅} není rekurzivní. Uvažujme nyní ='G # = {〈'〉 ∣ ' je ' ∧ ' = ∅}. Naším plánem je ukázat, že není rekurzivní, a následně jej použít v redukci ='G # ≤ =>, čímž bychom dokázali, že i jazyk => není rekurzivní. Až na řetězce 〈I〉, které nekódují žádný TM, je jazyk ='G # doplňkem jazyka *F*='G #. Sjednotíme-li tedy množiny ='G # a = {〈I〉 ∣ I není kódem '}, měli bychom dostat jazyk, který není rekurzivní. Pokud by byl, musel by být díky uzávěrovým vlastnostem rekurzivní i *F*='G #. Tedy (*) ='G # ∪ není rekurzivní. Jazyk ='G # však také není rekurzivní. Není totiž složité najít Turingův stroj, který by rozhodoval jazyk B, tedy B je rekurzivní. Jazyk ='G # tím pádem není rekurzivní – pokud by byl, bylo by i sjednocení ='G # ∪ díky uzávěrovým vlastnostem rekurzivní, což je spor s výše uvedeným závěrem (*). Nyní přistupme k popsání redukce ='G # ≤ =>. Sestrojme funkci : {0, 1, #}∗ → {0, 1, #}∗ , která zobrazí slovo ! = 〈'〉 na slovo ! = 〈', '?〉 tak, že ! ∈ ='G # ⟺ ! ∈ =>, přičemž '? = ∅. Předpokládejme, že existuje TM R rozhodující jazyk =>. ! = 〈', '?〉, kde '? je TM zamítající jakýkoliv vstup. Nyní ověřme: 〈'〉 ∈ ='G # ⟺ ' = ∅ ⟺ 〈', '?〉 ∈ => ! ∈ ='G # ⟺ ! ∈ => ='G # ≤ => Není-li x kódem Turingova stroje, platí ! = ∅, tj. ! ∈ ='G #. TM R tento kód porovnává s kódem TM '?, pro který taktéž platí '? = ∅. Q tedy přijímá. V opačném případě, kdy ! = 〈'〉, kde ' je nějaký TM, připravíme vstup 〈', '?〉 pro TM R rozhodující jazyk =>. R přijímá pouze tehdy, když ' = '? = ∅, tedy když ! = 〈', '?〉 ∈ =>. Funkce f je totální, jelikož každému vstupu x přiřazuje kód 〈', '?〉. Je i vyčíslitelná, jelikož při své práci pouze simuluje činnost TM R. Protože však jazyk ='G # není rekurzivní, nemůže být rekurzivní ani jazyk =>.