=Algoritmicky nerozhodnutelné problémy (halting problem) (9×🎓)=
{{Zkazky|
* '''Halting problém (2013, Kolman)''' - Tu som zadefinoval TS, spomenul som kódovanie TS (nič konkrétne iba že to je číslo), Postovu vetu a dokázal som, že L HALT nie je rekurzivný, na záver som spomenul, že to isté sa dá urobiť aj cez množiny. Žiadne doplnkové otázky.
* '''Algoritmicky nerozhodnutelné problémy (2012)''' - Napsal jsem Halting problém + ten jednoduchý důkaz. Dále jsem napsal Riceovu větu a jak souvisí s halting problémem. Nakonec jsem napsal Postův korespondenční problém. To zkoušejícímu stačilo a nebyly žádné další otázky.
* '''Nerozhodnutelné problémy (2012, Kucera)''' - Halting problem - jak se dokazuje, Postuv problem, rozhodnuti zdali dana funkce vycisluje dany program
* '''Algoritmicky nerozhodnutelne problemy (2012, Dvorak)''' - Zacal sem Church-Turingovou tezi a pojem algoritmus vztahl k TS. Pak sem zadefinoval Rekurzivne spocetne a rekurzivni jazyky. Halting problem, Diagonalni jazyk, Univerzalni jazyk, Postova veta. Pak sem presel od TS k CRF tady sem jako priklad uvedl K a K0, definoval CRF a ORF + intuitivni srovnani s TS U vetsiny veci sem mel i dukazy ( vycislitelnosti sem se bal nejvic z okruhu takze sem to mel celkem nadrceny ). Pak se dvorak ptal jak zjistim ze nejakekj problem je nerozhodnutelny ( aniz by clovek musel furt vymyslet specialni dukazy ) to sem chvili vahal ale pak sem si vzpomel na prevoditelnost Rekurzivnich a rekurzivne spocetnych mnozin pomoci prevodni fce ktera musi byt ORF coz se ukazalo jako spravna odpoved. Posledni sada otazek uz smerovala k tomu co se bude dit kdyz budu mit TS s orakulem, jestli potom budou vsechny problemy budou rozhodnutelne...tady sem nevedel, odpovidal sem hodne diplomaticky ( spravna odpoved je TS s 1 orakulem umi resit nejaky problemy, TS s 2 orakulama umi resit jeste vic problemu atd...ale nikdy nelze pokryt vsechny jazyky ) Jeste dodam ze tohle nakonec Dvorak okomentoval slovy ze je to spis takova zajimavost, nic zasadniho pro statnice.
* '''Algoritmicky nerozhodnutelné problémy (2012)''' - Napsal jsem Halting problém + ten jednoduchý důkaz. Dále jsem napsal Riceovu větu a jak souvisí s halting problémem. Nakonec jsem napsal Postův korespondenční problém. To zkoušejícímu stačilo a nebyly žádné další otázky.
* '''Algoritmicky nerozhodnutelné problémy (2011, Kucera)''' - Způsob zkoušení: Zdá se, že mu jde o témata, které mají praktický dopad (např. halting problem). Ptal se, jestli znám ještě další nerozhodnutelný problém. Dostali jsme se i k Riceově větě, ale bránil mi ji dokazovat, protože to nebylo v otázce. Známku mi neříkal. S Majerechem zkoušeli někoho společně. Uklidňovali ho, že mu chtějí pomoct.
* '''Algoritmicky nerozhodnutelné problémy (2010)''' - Co to je rozh. problém, halting problém, že to souvisí s tím, že množina K není rekurzivní, Riceova věta s důkazem.
* '''Alg. nerozhodnutelne problemy (2010, P. Kucera)''' - klasika, definice co to je problem, rozdil mezi rekurzivne spocetnym a rekurzivnim, Churchova teze a ekvivalence s TS, dale halting problem + ten snadny dukaz, Riceho veta a jeste jeden dva dalsi problemy jako zajimavost.
* '''Nerozhodnutelne problemy (2009, Mlcek)''' - Halting a Riceova s dokazom, ostatne len nazov
}}
'''instance problému''' - vstup
'''rozhodovací problém'''(odpověď typu ano/ne) - jazyk řetězců popisujících pozitivní instance a otázku, zda dané slovo – instance problému – patří do tohoto jazyka (kladná instance daného problému)
Jazyk <math>L</math> je '''rekurzivní''' (také '''rozhodnutelný'''), pokud ∃ TS <math>M</math>, který se vždy zastaví a <math>L = L(M)</math>.
[[Image:Diag.jpg|right|thumb|460px|<math>L_{DIAG}</math>]]
{{theorem
| <math>L_{DIAG} = \{w_i ∈ \{0, 1\}^* | w_i ∉ L(M_i) \}</math> není RSJ (tedy ani RJ)
| diagonalizační jazyk
}}
;Dk (sporem)
: Předpokládáme že <math>L_{DIAG}</math> je RSJ ⇒ ∃ TS M že <math>L_{DIAG} = L(M_e)</math> z čekož nám vychází ale '''spor''':
: <math>w_e \in L(M_e) ⇔ w_e ∈ L_{DIAG} ⇔ w_e \notin L(M_e)</math>, kde první ekvivalence vyplývá z toho, že <math>L_{DIAG} = L(M_e)</math> a druhá ekvivalence z definice <math>L_{DIAG}</math>
===univerzální jazyk===
{{theorem
| <math>L_u = L(U)</math> (kde U je UTS) je RSJ, ale není RJ
| univerzální jazyk
}}
;Dk (sporem)
: To, že <math>L_u</math> je RSJ jsme ukázali tím, že jsme popsali UTS, který jej přijímá.
: Zbývá tedy ukázat, že není rekurzivní. Z Postovy věty stačí dokázat pouze, že <math>\overline L_u</math> není RSJ.
: Sporem nechť <math>\overline L_u = L(M)</math>. Pomocí stroje <math>M</math> zkonstruujeme stroj <math>M’</math>, který bude přijímat diagonalizační jazyk <math>L_{DIAG}</math>. Už víme, že <math>L_{DIAG}</math> není RSJ a dospějeme tím tedy ke '''sporu'''.
: <math>M’</math> dostane na vstupu slovo <math>w</math> a má rozhodnout, zda <math>w ∈ L_{DIAG}</math>, tedy jestli stroj s kódem <math>w</math> odmítne slovo <math>w</math>.
: <math>M’</math> udělá pouze to, že zkontroluje, zda w kóduje Turingův stroj způsobem, jaký jsme popsali při popisu UTS. Pokud <math>w</math> nekóduje syntakticky správně TS, odpovídá prázdnému TS, který slovo <math>w</math> určitě nepřijme a <math>M’</math> tedy skončí přijetím. V opačném případě připíše <math>M’</math> za <math>w</math> kód <math>111</math> (kód „;“) a za ně okopíruje opět slovo <math>w</math>. Poté <math>M’</math> spustí na tomto slově stroj <math>M</math>, pokud <math>M</math> přijme, přijme i <math>M’</math>, pokud se <math>M</math> zastaví a odmítne, odmítne i <math>M’</math>, pokud se <math>M</math> nezastaví, nezastaví se ani <math>M’</math>.
: <math>M’</math> ale přijímá jazyk <math>L_{DIAG}</math>, protože <math>M’(w)</math> přijme ⇔ <math>w</math> je validním kódem TS <math>N</math> a <math>N(w)</math> nepřijme, což je ekvivalentní tomu, že <math>U(w;w)</math> nepřijme a <math>M(w; w)</math> přijme. Fakt, že <math>L(M’) = L_{DIAG}</math>, je však ve '''sporu''' s tím, že <math>L_{DIAG}</math> není RSJ.
===problém zastavení===
{{theorem
| <math>L_{HALT} = \{w; x |~ w~ kóduje~ TS~ M~ a~ M(x)↓\}</math> je RSJ, ale není RJ
| problém zastavení
}}
;Dk
: sporem mejme f(x,y) ktera dobehne prave kdyz F(x,y) se zacykli; vezmeme kod f=e a pustme f(e,e) - kdyz dobehne, mela se F(e,e) zacyklit, a kdyz nedobehne, mela F(e,e) dobehnout, ale F je univ. funkce => spor
;Dk (sporem)
: Že <math>L_{HALT}</math> je RSJ je zřejmé z existence UTS. <math>w;x \in L_{HALT} \Leftrightarrow U(w;x)↓</math>
: Diagonalizací ukážeme, že <math>\overline L_{HALT}</math> není RSJ, čímž bude důkaz dokončen díky Postové větě.
: Předpokládejme pro spor, že ∃ TS <math>M</math>, že <math>\overline L_{HALT} = L(M)</math>.
: Nyní definujme jazyk <math>L = \{w_i \in \{0, 1\}^*| M_i(w_i)↑\}</math>, jde vlastně o diagonálu <math>\overline L_{HALT}</math>. S pomocí TS <math>M</math> sestrojíme nyní TS <math>M_e</math> přijímající jazyk <math>L</math>.
: Pokud <math>M(w_i;w_i)</math> přijme, pak přijme i <math>M_e(w_i)</math>, v opačném případě <math>M_e(w_i)↑</math>. To učiní i v případě, zjistí-li, že <math>w_i</math> nekóduje syntakticky správně TS a odpovídá tedy prázdnému TS (to je zde nutné odlišit jen proto, že kdyby <math>w_i</math> obsahovalo oddělovač „;“, pak by <math>w_i;w_i</math> mohlo odpovídat výpočtu jiného TS nad jiným vstupem).
: TS <math>M_e</math> přijme svůj vstup ⇔ <math>M_e↓</math>. Zřejmě platí, že <math>L(M_e) = L</math>.
: Nyní se podívejme, jestli <math>w_e \in L</math> (<math>w_e</math> je kód <math>M_e</math>):
:# Pokud <math>w_e ∈ L</math>, znamená to, že se <math>M_e(w_e)</math> zastaví a přijme, protože <math>L = L(M_e)</math>, to ale současně znamená, že <math>M_e(w_e)↑</math> podle definice <math>L</math>, což je pochopitelně ve '''sporu'''.
:# Nyní předpokládejme, že <math>w_e \notin L</math>, ale podle definice <math>L</math> to znamená, že <math>M_e(w_e)↓</math>. Z toho jsme dostali <math>w_e ∈ L(M_e) = L</math>, což je však ve '''sporu''' s předpokladem.
: Jazyk <math>L</math> použitý v důkazu není nic jiného než <math>L_{DIAG}</math>, pokud bychom předpokládali, že TS přijímají zastavením v jakémkoli stavu.
{{Statnice I2}}
