18 - Nerozhodnutelnost
pátek 13. května 2016
10:28
Nerozhodnutelnost (problém zastavení TS, princip diagonalizace a redukce, Postův korespondenční problém).
[link]
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
(Cantorova) diagonalizace
Lemma: Pro neprázdnou a konečnou množinu 𝜮 je množina 𝟐𝚺* 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
Diagonalizace pro množinu jazyků
Předpokládejme, že 𝟐𝚺* je spočetná (tj. každému jazyku lze přiřadit nějaké přirozené číslo - bijektivní zobrazení 𝑓)
Uspořádáme řetezce 𝜮∗ do nějaké posloupnosti 𝑤1,𝑤2,𝑤,… (podle libovolného klíče)
Např. ε, x, y, xx, xy, yx, yy, xxx, ... pro Σ = {x, y}.
Bijektivní zobrazení jazyků na přirozená čísla lze nyní zobrazit jako nekonečnou matici:
Uvažme jazyk 𝑳=𝒘𝒊𝒂𝒊𝒊=𝟎} (diagonála matice, tj. prvky se stejnými indexy)
Je-li 𝑎𝑖𝑖=0, pak 𝑤𝑖 patří do jazyka.
Je-li 𝑎𝑖𝑖=1, pak 𝑤𝑖 nepatří do jazyka.
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 𝑖𝑤0 patří do jazyka 𝐿0. Tedy 𝑎00=1 a z toho plyne, že řetězec 𝑤0∉𝐿. Pokud by ovšem 𝑎00=0, tedy řetězec 𝑤0 nepatřil do jazyka 𝐿0, pak by tento řetězec patřil do jazyka 𝐿 a tím by se tedy tyto dva jazyky zase odlišovaly.
To je spor a předpoklad, že 𝟐𝚺* je spočetná tedy neplatí.
Co vlastně rozhodujeme a na čem? 
Rozhodujeme, zda daný řetězec je přijat TS a zda stroj zastaví.
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)
[link]
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ý).
Důkaz HP
Problému zastavení odpovídá rozhodování jazyka 𝑯𝑷={〈𝑴〉#〈𝒘〉| 𝑴 𝒛𝒂𝒔𝒕𝒂𝒗í 𝒑ř𝒊 𝒘}, kde <M> je kód TS M a <w> je kód vstupní pásky TS M.
Částečná rozhodnutelnost
Sestavíme univerzální TS, který simuluje běh původního TS tak, aby zastavil přijetím vstupu <M>#<w> právě když by zastavil původní TS přijetím vstupu 𝒘 - převod abnormálního zastavení na zastavení přechodem do koncového stavu
Nerozhodnutelnost (co-HP?)
Počáteční předpoklad: Předpokládejme, že problém zastavení lze rozhodnout. To znamená, že existuje nějaký program Zastaví(program, vstup), který je univerzálním řešením problému zastavení.
Ten funguje tak, že pokud volání program(vstup) po konečném počtu kroků skončí, pak Zastaví(program, vstup) vrátí hodnotu ANO, v opačném případě (pokud by se volání program(vstup) zacyklilo) vrátí hodnotu NE.
Zkonstruujme program Paradox(x), který se záměrně zacyklí, pokud volání programu Zastaví(x, x) vrátí ANO, a zastaví se, pokud volání programu Zastaví(x, x)vrátí NE.
Nyní se ptejme, co je výsledkem volání Paradox(Paradox).
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.
Protože jsme vyčerpali všechny možnosti a vždy došli ke sporu, musí být nepravdivý počáteční předpoklad. Z toho vyplývá, že program Zastaví(program, vstup), tak jak byl definován, neexistuje.
Ještě jedna reprezentace problému
1 void Q(void) {
2   if (zastavi(Q))
3     while(1) { }
4 }
Ukažme si, že funkce Q je nesmysl. A protože jediné sporné, co v této funkci používáme, je funkce zastavi, ukážeme tím i, že ona funkce zastavi je vlastně nesmysl. Poznamenejme ještě, že každý program buď zastaví, a nebo nezastaví, nic mezi tím (žádné „polozastavení“) neexistuje.
Dejme tomu, že funkce Q zastaví. Pak ale bude splněna podmínka na řádku 2 a z toho nám vyplyne, že vlastně nezastaví.
Dejme tomu, že funkce Q nezastaví. Pak ale podmínka na řádku 2 splněna nebude a z toho nám vyplyne, že vlastně zastaví.
Funkci zastavi nelze naprogramovat. Tedy nemůžeme rozhodnout jestli program zastaví. 
Je to trošku na palici, ale ukazuje to, proč analyzátory kódu mají problém s dokazováním toho, jestli program (ne)zastaví, když potom používá svůj vlastní kód.
Nerozhodnutelnost problémů
Důkaz nerozhodnutelnosti 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 𝑓 každé instanci 𝐼 problému 𝑃 přiřadí instanci 𝑓(𝐼) problému 𝑄 tak, že řešení 𝑓(𝐼) je právě řešením 𝐼.
značíme 𝑨≤𝑩 (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ě 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ů
Rozhodnutelné problémy
TS má alespoň 𝒙 stavů
TS učiní alespoň 𝒙 kroků pro vstup 𝑤
Částečně rozhodnutelné problémy
Jazyk TS má alespoň 𝒙 slov
Nerozhodnutelné
Jazyk TS má maximálně 𝒙 slov
Jazyk TS je konečný
PCP
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 systém
Postův systém je tvořen neprázdným seznamem S dvojic neprázdných řetězců:
Řešením Postova systému je každá neprázdná posloupnost přirozených čísel 𝐼:
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 𝑆1=𝑏,𝑏𝑏𝑏, (𝑏𝑎𝑏𝑏𝑏,𝑏𝑎),(𝑏𝑎, 𝑎) má řešení 𝐼=2,1,1,3 (babbb b b ba = ba bbb bbb a).
Systém 𝑆2=(𝑎𝑏,𝑎𝑏𝑏),(𝑎,𝑏𝑎),(𝑏,𝑏𝑏) řešení nemá, jelikož délka |𝛼𝑖| < |𝛽𝑖|, pro všechny 𝑖. Nikdy tedy nebude délka |𝛼| rovna |𝛽|.
Problém prázdnosti jazyka kontextové gramatika pomocí PCP
Redukce z komplementu PCP (co-PCP)
Mějme PCP S = (alfa_1, beta_1), (alfa_2, beta_2), … , (alfa_k, beta_k)
Průnik La a Lb je řešením S, protože jako výsledek dostaneme stejný řetězec u#v v obou jazycích, kde u u je poskládané z alf (v La) nebo z bet (Lb) a v je řešení PCP (indexy jak se mají prvky S poskládat, aby alfy se rovnaly betám)
La a Lb jsou DBKJ a jejich průnik je KJ
Průnik La a Lb je prázdný právě tehdy, když PCP S nemá řešení (co-PCP). 
Co-PCP je nerozhodnutelný a tedy i otázku prázdnosti kontextového jazyka je nerzohodnutelná
Membership problem
Částečně rozhodnutelný problém
Redukce z HP:
Mějme TS M, který řeší MP
Transformaci z M na M' (M' řeší HP) lze udělat pomocí úplného TS M_r. M_r vezme výsledek M a v případě, že by M přijmul nebo odmítnul, tak M_r přijme. Stačí dodat chybějící přechody do qf v případech, kdy by se TS zastavil a přechod do qf pro abnormální zastavení. V ostatních případech se M + M_r zacyklí, stejně jako M'.
Tím jsme schopni redukovat MP úplným TS na HP (MP <= HP) a tím se dokazuje, že MP je také částečně rozhodnutelný (protože o HP víme, že je částečně rozhodnutelný)
Notes
1. Otazka (predmet) (okruh): Nerozhodnutelnost (TIN)
Kdo me primarne zkousel: Vojnar
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Zajímal ho jenom důkaz diagonalizací, řekl, že si mám z těch dvou, které znám vybrat ten jednodušší, takže jsem s jeho pomocí zreprodukoval důkaz existence jazyků mimo třídu typu 0. Věděl jsem jak na to, občas jsem nebyl schopný se vymáčknout, ale Vojnar mi vždy pomohl. Příjemný rozhovor. Nemluvil jsem ani ty 4 minuty, po konci důkazu mi řekl, že to stačí.
From <[link]> 
2. Otazka (predmet) (okruh): Nerozhodnutelnost (problém zastavení TS, princip diagonalizace a redukce, Postův korespondenční problém)
Kdo me primarne zkousel: Mgr. Adam Rogalewicz, Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Otázka z nočních můr, kterou jsem fakt nechtěla. Na lístečku bylo napsáno Nerozhodnutelnost (rozhodnutelný, částečně rozhodnutelný a nerozhodnutelný problém) a problém zastavení. Měla jsem naprosto okno, tak jsem začala velmi hloupě, že řešíme tři případy - rozhodnutelný, částečně rozhodnutelný a nerozhodnutelný problém. Na což se mě zeptal, co vlastně rozhodujeme a na čem. Tak ze mě později vydoloval něco o turingových strojích a že řešíme, zda daný řetězec je přijat a zda stroj zastaví. Snažila jsem se odbočit z otázky, že rozhodnutelný problém je popsán úplným TS a částečně rozhodnutelný TS a popsat tyto TS. Ale držel mě striktně u dané otázky. Pak chtěl od každého problému konkrétní případ. Dost jsem motala odpovědi, že ani nevím, co jsem řekla správně a co ne. Odcházela jsem s pocitem šílenství, že nejlépe za E nebo i za F. A pak při vyhodnocení mi oznámili, že za B. Nechápu, kde to vzali. Ale v tom zmateném blekotání jsem asi řekla něco, co bylo správně. 
From <[link]> 
1. Otazka (předmět) (okruh): 18. nerozhodnutelnost, redukce
Kdo me primarne zkousel: Češka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Problematiku jsem chápal, definice jsem moc neuměl. Nemyslím si, že bych řekl někdy něco vyloženě špatně, spíše značně neformálně a nepřesně. První čtyři minuty nám trvalo, než jsme se shodli na tom, co je to nerozhodnutelnost, problém, jak je reprezentujeme apod. Pak jsme se dostali k redukci a jak souvisí s nerozhodnutelností. Obecně jsem to popsal, tady ode mě chtěl slyšet něco, co jsem mu nakonec asi ani neřekl. Několika způsoby jsem popsal redukci, jak dokazujeme (ne)rozhodnutelnost, nakreslil graf. On kroutil hlavou, já opakoval různé variace toho svého. Nakonec to vzdal a řekl, že na vyhození to není. D.
From <[link]> 
1. Otazka (předmět) (okruh): 18. Nerozhodnutelnost - HP + dukaz diagonalizaci
Kdo me primarne zkousel: prof. Vojnar
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: prvne definici HP to bylo vpohode a pak chtel princip dukazu ze HP je castecne rozhodnutelny. Tedy dukaz pomoci diagonalizace. ten jsem se vubec neucil, tak to ze me tahal asi 5min nakonec jsem to nejak vymyslel, nakonec se zeptal na nejaky jazuk ktery je nerozhodnutelny, tak jsem rekl co-HP. Vysledna E
From <[link]> 
1. Otazka (předmět) (okruh): 18. Nerozhodnutelnost (sp. diagonalizace)
Kdo me primarne zkousel: prof. Ceska
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Chtela jsem zacit s tou diagonalizaci, ale Ceska me usmernil, ze by rad nejaky uvod k nerozhodnutelnosti. Tak jsem rekla neco o problemech a ze jsou specifikovany jazyky a TS atd. Pak me pustil k te diagonalizaci. Zacla jsem to popisovat a chtel, at mu k tomu rovnou i kreslim na tabuli tu tabulku, tak jsem to udelala. Kdyz videl, ze tomu rozumim, zastavil me. Presel na rozhodnutelne vs. nerozhodnutelne problemy a chtel znat nejake predstavitele. Trochu vypadek byl, kdyz jsem si nakonec uz nevzpomnela na zadny nerozhodnutelny (co-HP).
From <[link]> 
1. Otazka (předmět) (okruh): 18 - TIN - Nerozhodnutelnost
Kdo me primarne zkousel: Janoušek Vladimír, doc. Ing., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Toto jsem celkem věděl, ale zjišťuji, že na sobě začínám pociťovat klasické syndromy nerdovství. Měl jsem problém se pořádně vyjádřit, předat ty znalosti. Přestože jsem znal odpověď na každou otázku, šlo to ze mě relativně pomalu. Navíc si celkem potrpěl na to, aby ty věci byly řečené opravdu korektně.
Chtěl znát, co je to (ne)rozhodnutelnost, jak určíme, že je jazyk (ne)rozhodnutelný. Nějaký příklad nerozhodnutelného jazyka. Jak je to s tímto příkladem (řekl jsem prázdnost u typu 0) u ostatních typů jazyků. Popsat problém zastavení a jak bych ho dokázal.
From <[link]> 
1. Otazka (předmět) (okruh): TIN - Nerozhodnutelnosť a diagonalizace.
Kdo me primarne zkousel: Vojnár Tomás
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Túto otázku som vedel docela dobre, povedal som všetko. Hlavne som rozprával v klúčových slovách 
že k tomu rozumiem. Po 2 minutách Vojnár povedal, že to mu stačí. Bol veľmi fájn... chcel veľmi pomocť. Nakoniec A.
From <[link]> 
1. Otazka (předmět) (okruh): 18. Nerozhodnutelnost (problém zastavení TS, princip diagonalizace a redukce, Postův korespondenční problém).
Kdo me primarne zkousel: Holík Lukáš, Mgr., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Zacal jsem pekne zesiroka co je rozhodnutelny, nerozhodnutelny a castecne rozhodnutelny problem. U kazdeho se navic uvedl priklad takoveho problemu. Zkousejici mi do monologu vubec nezasahoval a pouze prikyvoval. Pak jsem zacal popisovat problem zastaveni. U jazyku HP jsem rekl o jaky jazyk se jedna (rekurzivne vycislitelny, neni rekurzivni). To same u co-HP (neni ani rekurzivne vycislitelny). Pak chtel jen abych zminil diagonalizaci a Postuv korespondencni problem. U toho chtel navic popsat jak to funguje. To jsem tam nekde v pameti mel, ale rozhodne ne presne, tak jsem se mu to snazil vysvetlit. Na to rikal, ze tusim a ze jestli bych mu to mohl napsat na tabuli. Napsal jsem a to mu stacilo.
From <[link]> 
2. TIN - nerozhodnutelnost (diagonalizace):
Kdo me primarne zkousel: Vojnar
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Ukazal jsem mu tu prvni cast kdy se dokaze ze mnozina jazyku neni spocetna. Na to mi rekl, ze bych ted mel ukazat jak dokazu, ze lezi jazyky mimo tu tridu 0. Tam jsem se zasekl ale Vojnar me tim provedl
Znamka: D
From <[link]> 
2. Otazka (okruh): Nerozhodnutelnost
Kdo me primarne zkousel: pouze Janoušek Vladimír
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začal jsem koktat o rozhodnutelnosti jazyka. Byl jsem namířen k TS a následně k HP. To jsem popsal. Zmínka o MP a cílená otázka na PSP. Všechno jsem jen řekl, na tabuli jsem psal pouze jazyk HP a ještě to bylo spíš neformálně. Janoušek řekl, že stačí. Žádný důkaz, žádná diagonalizace. 
From <[link]> 
1. Otazka (předmět) (okruh): TIN - Nerozhodnutelnost, redukce
Kdo me primarne zkousel: Češka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: nez jsem se stacil nadechnout, zacal se ptat on, nejdriv co to je nerozhodnutelnost, jak se to deli a jaky jsou typicky priklady pro ty rozhodnutelny, cast. rozhodnutelny a nerozhodnuntelny problemy. To jsem popsal celkem v poho, jen u tech rozhodnutelnych jsem zavahal ale vzpomnel jsem si. Pak jsem sel na redukci. nakreslil jsem ty dve prsa a popsal sigma, jen sem nejak nerek ze musi byt rekurzivni, protoze kdyz je totalni (coz jsem rek) tak jsem nejak predpokladal ze to je jasny a pak sem nejak znervoznel a delal ze nevim. Pak sem vysvetlil jak je to s tema problemama presne podle Vojnara ze STI (jak pro blbi), coz se mu moc nelibilo, ale nakonec jsme to dali dokupy. Nakonec pry lepsi B 
From <[link]> 
18 - Nerozhodnutelnost
Kdo me primarne zkousel:
Rogalewicz Adam, Mgr., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začal jsem co je to rozhodnutelnost, chtěl vědět nějaké příklady rozhodnutelných a nerozhodnutelných problémů, pak HP vysvětlit a naznačit jak se dokáže částečná rozhodnutelnost. Nakonec chtěl popsat Postův kor. problém.
From <[link]> 
1. Otazka (okruh): 18 - Nerozhodnutelnost, redukce
Kdo me primarne zkousel: Vojnar
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Na tabuli sem vystrih redukci, neco malo o tom rek. Pak se me zacal ptat na to, jak to pouziju, pokud vim, ze je jeden z tech jazyku rozh./neni rozh., chtel zapsat HP a MP (jejich jazyky) a jestli vim, jak tu redukci pouzit na prevod HP -> MP. Tam jsem se dost zamotal, ale hodne mi Vojnar pomoh.
From <[link]> 
2. Otazka (okruh): 18 - Nerozhodnutelnost (princip redukce)
Kdo me primarne zkousel: Vojnar
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: K čemu to je, co znamená to zobrazení, trochu jsme se nemohli dohodnout, chtěl vědět, že se řetězce abecedy jednoho jazyka zobrazí na řetězce abecedy druhého jazyka. Nakonec jsme to nějak dali dohromady, řekl jsem mu ty příklady, že "Pokud A není RE/R, pak ani B není RE/R" a obměnu. Pak se ptal, jak bych redukci ukázal na problému HP > MP. Tady už jsem to trošku nějak pomotal, ale nakonec docela dobrej pocit. Na závěr jsem zapotil úplnou perlu, tak řekl "To mi stačí." 
From <[link]> 