23 - Nerozhodnutelnost (problém zastavení TS, princip diagonalizace a redukce, Postův korespondenční problém) Flashcards
Základní pojmy (jazyky mimo třídu 0)
Jazyky mimo třídu 0
Existují jazyky ležící mimo typ 0 Chomského hierarchie.
• Množina všech TS je spočetná (TS lze zakódovat jako binární řetězce a ty počítat dle pořadí)
• Množina všech jazyků je nespočetná (viz diagonalizace)
• Množiny tedy mají rozdílnou mohutnost
-> Existují jazyky, které nejsou vyčíslitelné žádným TS, a problémy, které žádný TS není schopen rozhodnout
Základní pojmy (Diagonalizace)
(Cantorova) diagonalizace
Lemma: Pro neprázdnou a konečnou množinu Σ je množina 2^(Σ^* ) nespočetná (množina Σ * obsahuje nekonečně mnoho řetězců)
• používá se pro důkaz nespočetnosti množiny
poprvé použita pro důkaz rozdílné mohutnosti přirozených a reálných čísel
Pointa -> zapišme do matice všechny možné kombinace, dále vytvoříme jazyk z prvků diagonály matice a uděláme inverzi (0 patří do jazyka, 1 nepatří)
= jazyk který touto operací vznikne se liší od každého jazyka v matici, ale zároveň patří do množiny 2^(Σ^* ) -> spor
Diagonalizace pro množinu jazyků
1. Předpokládejme, že 2^(Σ^* ) je spočetná (tj. každému jazyku lze přiřadit nějaké přirozené číslo - bijektivní zobrazení f)
2. Uspořádáme řetezce Σ^∗ do nějaké posloupnosti w1,w2,w,… (podle libovolného klíče)
○ Např. ε, x, y, xx, xy, yx, yy, xxx, … pro Σ = {x, y}.
3. Bijektivní zobrazení jazyků na přirozená čísla lze nyní zobrazit jako nekonečnou matici:
4. Uvažme jazyk L ̅={w_i ┤| a_ii=0} (diagonála matice, tj. prvky se stejnými indexy) + inverze
○ Je-li a_ii=0, pak w_i patří do jazyka.
○ Je-li a_ii=1, pak w_i nepatří do jazyka.
5. Tento jazyk se liší od každého jazyka v matici (minimálně prvkem, kde se diagonála protíná s řádkem jazyka), zároveň ale patří do 2^(Σ^* ).
○ Proč se ten jazyk L liší od každého jazyka v matici? Dejme tomu, že řetězec 〖iw〗_0 patří do jazyka L_0. Tedy a_00=1 a z toho plyne, že řetězec w_0∉L. Pokud by ovšem a_00=0, tedy řetězec w_0 nepatřil do jazyka L_0, pak by tento řetězec patřil do jazyka L a tím by se tedy tyto dva jazyky zase odlišovaly.
6. To je spor a předpoklad, že 2^(Σ^* ) je spočetná tedy neplatí.
Rozhodovací problémy TS (co rozhodujeme a typy)
Rozhodujeme, zda daný řetězec je přijat TS a zda stroj zastaví.
Rozhodovací problém
• funkce s oborem hodnot {true, false}
• obvykle je specifikován množinou všech možných instancí problému a podmnožinou pro které je výsledek roven true
• V teorii formálních jazyků používáme k zakódování problémů řetězce nad abecedou - jazyky pak představují podmnožiny pro které je výsledek roven true
Rozhodnutelný problém
• Vždy je možné rozhodnout zda je výsledek true nebo false
○ Tedy vždy víme, jestli daný TS přijme řetězec nebo jej nepřijme.
• Rozhodnutelné jsou problémy reprezentované rekurzivními jazyky.
Nerozhodnutelný problém
• Není možné vždy rozhodnout zda je výsledek true nebo false
Částečně rozhodnutelný problém
• Pokud řetězec nepatří do jazyka, tak se může TS zacyklit.
• pro výsledek true vždy (po konečné době) rozhodne, ale pro výsledek false buď rozhodne nebo donekonečna cyklí (rozhodnutí trvá nekonečnou dobu)
• částečně rozhodnutelné jsou problémy reprezentované rekurzivně vyčíslitelnými jazyky
Problém zastavení TS (HP - Halting problem)
jazyk HP = { < Mx, x > | Mx je TS, který zastaví pro x }
Problém zda daný TS pro daný vstupní řetězec zastaví není rozhodnutelný, ale je částečně rozhodnutelný.
• Znáte-li zdrojový kód programu a jeho vstup, rozhodněte, zda program zastaví, nebo zda poběží navždy bez zastavení.
Nerozhodnutelnost problému zastavení lze dokázat sporem (vyjdeme z nějakého předpokladu, ale dojdeme k paradoxu, což znamená, že náš předpoklad by špatný).
Částečná rozhodnutelnost - vytvoříme TS který necyklí ale skončí ve speciálním stavu
Sestavíme univerzální TS, který simuluje běh původního TS tak, aby zastavil přijetím vstupu # právě když by zastavil původní TS přijetím vstupu w - převod abnormálního zastavení na zastavení přechodem do koncového stavu
NErozhodnutelnost (buďto diagonalizace, nebo): - prostě když předpokládáme že se zastaví, tak cyklí a když předpokládáme že bude cyklit tak se zastaví
- vytvořme program Zastaví(program, vstup), pokud zastaví -> ANO, jinak vrací NE
- vytvořme program paradox(x), který má jako parametr program Zastaví, který se zacyklí pokud program vrátí ANO, jinak vrátí NE• Předpokládejme na chvíli, že Zastaví(Paradox, Paradox) vrací ANO. Z definice programu Paradox pak víme, že se Paradox(Paradox) zacyklí. Podle definice programu Zastaví ale platí, že pokud Paradox(Paradox) zacyklí, pak musí Zastaví(Paradox, Paradox) vracet NE. Došli jsme ke sporu.
Předpokládejme na druhou stranu na chvíli, že Zastaví(Paradox, Paradox) vrací NE. Z definice programu Paradox pak víme, že se Paradox(Paradox) zastaví. Podle definice programu Zastaví ale platí, že pokud Paradox(Paradox) zastaví, pak musí Zastaví(Paradox, Paradox) vracet ANO. Opět jsme došli ke sporu.
Nerozhodnutelnost problémů (redukcí)
Redukce
Redukce je základní technikou klasifikace problémů z hlediska vyčíslitelnosti. Jedná se o algoritmický převod problému na jiný problém (převod jednoho jazyka na jiný úplným TS)
• Redukční funkce f každé instanci I problému P přiřadí instanci f(I) problému Q tak, že řešení f(I) je právě řešením I.
• značíme A≤B (A je redukovatelný na B)
Důkaz redukcí
• víme, že jazyk A není rekurzivní (rekurzivně vyčíslitelný)
• zkoumáme jazyk B
• ukážeme, že A lze úplným TS převést (redukovat) na B
• to znamená, že B také není rekurzivní (rekurzivně vyčíslitelný)
Pokud lze A redukovat na B tak platí, že:
• A není rekurzivní -> B není rekurzivní
• A není rekurzivně vyčíslitelný -> B není rekurzivně vyčíslitelný
• B je rekurzivní -> A je rekurzivní
• B je rekurzivně vyčíslitelný -> A je rekurzivně vyčíslitelný
tj. pokud lze jazyky navzájem redukovat (oběma směry) tak platí, že:
• [oba jsou rekurzivní] nebo [oba nejsou rekurzivní]
• [oba jsou rekurzivně vyčíslitelné] nebo [oba nejsou rekurzivně vyčíslitelné]
Příklady problémů pro TS
Rozhodnutelné problémy • TS má alespoň x stavů • TS učiní alespoň x kroků pro vstup w Částečně rozhodnutelné problémy • TS má neprázdný jazyk • Jazyk TS má alespoň x slov Nerozhodnutelné • Jazyk TS je prázdný • Jazyk TS má maximálně x slov • Jazyk TS je konečný • PCP
Problém náležitosti (MP) - redukujeme na halting problem - dokážeme že není rozhodnutelný (částečně)
Postův korespondenční problém
Postův korespondenční problém (PCP) je nerozhodnutelný problém (problém je algoritmicky nerozhodnutelný). Redukce z PCP nebo jeho doplňku se používají k důkazům nerozhodnutelnosti. (Postův problém je nerozhodnutelný (dokazuje se redukcí z problému náležitosti))
Problém náležitosti (MP)
- redukujeme na halting problem - dokážeme že není rozhodnutelný (částečně)
- libovolný TS lze upravit na TS který přijme, pokud původní TS zastaví (stačí dodat chybějící přechody a ochránit levý okraj) -> pak jde o problém zastavení a ten není rekurzivní.
Postův systém
Postův systém je tvořen neprázdným seznamem S dvojic neprázdných řetězců:
• S=⟨(α_1,β_1 ),…,(α_k,β_k)⟩ , kde k≥1 a α_i, β_i jsou řetězce nad nějakou abecedou, která obsahuje alespoň dva symboly (v případě abecedy s jedním symbolem je problém rozhodnutelný).
Řešením Postova systému je každá neprázdná posloupnost přirozených čísel I:
• I=⟨i_1,…,i_m ⟩, kde 1≤i_j≤k a m≥1, pro kterou platí α_i1…α_im=β_i1…β_im
Postův korespondenční problém = je pak rozhodnout, zda pro daný konkrétní Postův systém existuje řešení či nikoli.
Příklady
• Systém S_1=⟨(b,bbb), (babbb,ba),(ba, a)⟩ má řešení I=⟨2,1,1,3⟩ (babbb b b ba = ba bbb bbb a).
• Systém S_2=⟨(ab,abb),(a,ba),(b,bb)⟩ řešení nemá, jelikož délka |α_i | < |β_i |, pro všechny i. Nikdy tedy nebude délka |α| rovna |β|.
