{{TOC limit}} pozn. státnicové otázky pro I2/3 jsou označené touto ikonkou: (🎓)

Vyčíslitelnost

Def. TS, RJ a RSJ. Uzavřenost RJ na doplňky. Postova v. (🎓)

Definice Turingova stroje, rekurzivního a rekurzivně spočetného jazyka. Uzavřenost rekurzivních jazyků na doplňky. Postova věta.

{{Zkazky|

  • stačilo na 1*A4: definice TS, M(w)↓ a M(w)↑, definice RS a RSJ, věty o doplňcích RJ a RSJ (bez dk), postova věta s lehkým důkazem uvedeným zde, bez dalších dotazů

}}

{{thesis | Ke každému algoritmu v intuitivním smyslu existuje TS, který jej implementuje.

| Churchova-Turingova (1936) }}

{{multiple image

|align = tright |direction = horizontal

| image1 = Tm.jpg

| width1 = 310 | caption1 = TS <math>M = (Q, ∑, δ, q_0, F)</math>

| image2 = ZSV 3729090544640692881.png

| width2 = 310 | caption2 = 💡 ∀RJ je i RSJ

}}

Turingův stroj

  • (k-páskový deterministický) TS je 5-tice: M = (Q, ∑, δ, q0, F)

    • Q je konečná množina stavů (řídící jednotky)

    • ∑ je konečná pásková abeceda

      • obsahuje znak λ pro prázdné políčko

    • <math>δ : Q \times ∑^k -> Q \times ∑^k \times \{R, N, L\}^k ∪ \{⊥\}</math> je přechodová fce

      • ⊥ je nedefinovaný přechod

    • q0 ∈ Q je počáteční stav

    • F ⊆ Q je množina přijímajících stavů.

  • Konfigurace TS obsahuje:

    • stav řídící jednotky

    • slovo na pásce

      • 💡 (od nejlevějšího neprázdného políčka do nejpravějšího)

    • pozice hlavy na pásce

      • 💡 čtené políčko v rámci slova

výpočet TS

  • M(w)↓ tj. výpočet konverguje pokud výpočet nad vstupem w skončí

    • TS přijímá slovo w

      • po skončení se nachází v přijímacím stavu

    • TS odmítá slovo w

      • po skončení se NEnachází v přijímacím stavu

  • M(w)↑ tj. výpočet diverguje pokud výpočet nad vstupem w nikdy neskončí

  • fce f turingovsky vyčíslitelná pokud ex. TS který jí počítá (💡 tj. f(x)↓=y)

  • ∀ k-páskový TS se dá převezt na 1-páskový

Rekurzivní a rekurzivně spočetný jazyk

  • L(M) označíme jazyk slov přijímaných TS M

  • L je rekurzivně spočetný (také částečně rozhodnutelný), pokud ∃TS M t.ž.: L = L(M).

  • L je rekurzivní (také rozhodnutelný), pokud ∃TS M t.ž.: sevždy zastaví a L = L(M)

💡 RSJ je spočetně ⇒ ∀ jazyk není RSJ

Uzavřenost rekurzivních jazyků na doplňky

  • L je RJ ⇒ {{overline|L}} je RJ

  • L i {{overline|L}} jsou RSJ ⇒ L je RJ

z toho nám vyjde:

Postova věta

{{theorem | L je RJ ⇔ L i {{overline|L}} jsou RSJ

| Postova }}

Dk (přes oba směry implikace)

⇒ L je RS, pro {{overline|L}} vytvořím TS M, {{overline|L}}=L(M) který přijme když původní TS (rozhodující RJ L) odmítne a zacyklí se když původní TS přijme

⇐ pustím oba TS a čekám na 1. co se zastaví (jeden se určo zastaví protože jeden přijíma A a druhý {{overline|A}})

GČ, UTS (🎓)

Gödelovo číslo, univerzální Turingův stroj.

Gödelovo číslo

  • přiřadí každému symbolu a formuli unikátní přirozené číslo

  • Je-li w_e kod TS M => e je Gödelovo číslo stroje M

💡 1 TS může mít ∞ mnoho bin. řetězců co ho kódují => má i ∞ mnoho GČ

Kódování instrukcí TS M = (Q, ∑, δ, q0, F)

Nejdřív do abecedy Γ = {0, 1, L, N, R, |, #, ; }, pak z abecedy <math>Γ</math> do binární.

<math>Q = \{q_0, q_1, . . . , q_r\}</math>, r ≥ 1, kde <math>q_0</math> označuje počáteční, <math>q_1</math> jediný { BÚNO } přijímající stav.

<math>Σ = {X_0, X_1, X_2, . . . , X_s}, s ≥ 2</math>, <math>X_0, X_1, X_2</math> označují postupně symboly <math>0, 1, λ</math>.

<math>(x)_B</math> značí binární zápis čísla <math>x</math>.

<math>C_n = (i)_B|(j)_B|(k)_B|(l)_B|Z</math> je kódem instrunkce <math>δ(q_i, X_j) = (q_k, X_l, Z)</math>, kde <math>Z ∈ \{L, N, R\}</math> (v abecedě <math>Γ</math>)

<math>C_1\#C_2\# . . . \#C_{n−1}\#C_n</math> je kódem TS <math>M</math>, jde o konkatenací kódú všech instrukcí TS <math>M</math> (v abecedě <math>Γ</math>)

Bin. kód <math>M</math> získáme přes: 0→000, 1→001, L→010, N→011, R→100, |→101, #→110, ; →111.

Bijekce <math>1w = e ∈ N</math>, určuje pro TS <math>M</math> s bin kódem <math>w</math> GČ <math>e</math>, pak TS značíme <math>M_e</math>

Univerzální Turingův stroj

  • Univerzální Turingův stroj U umí simulovat libovolný jiný TS M nad libovolným vstupem w.

  • Vstup: dvojice w;x, kde w je bin kódem TS M, x je vstupní slovo pro M

{{zarovka |

  • U(e,w) ≃ M(w), počítá stejnou funkci.

  • Zakódování TS navíc umožní každému TS přiřadit přirozené číslo

  • Svůj kód bude mít i UTS, tedy UTS bude schopen simulovat i sám sebe

  • Pokud se M(w) zacyklí, musí se zacyklit i U(e,w)

| Simulace: <math>U(w; x)↓ ⇔ M(x)↓</math> a <math>U(w; x)↓ = M(x)↓</math> }}

  • Simulace: <math>U(w; x)↓ ⇔ M(x)↓</math> a <math>U(w; x)↓ = M(x)↓</math>

  • 3-páskový UTS (💡 technicky jednodušší než 1-páskový a lze převést na 1-páskový): vstupno/výstupní, pracovní, stavová

Image:Uts.jpg

  • Vstupní páska

    • kód simulovaného stroje M a jeho vstup.

    • oddělovač ’;’ z abecedy Γ.

    • 💡 pouze se čte a na závěr na ni přepíše obsah pásky stroje M po ukončení jeho výpočtu.

  • Pracovní páska M

    • uložení slova z pracovní pásky M

    • Připomeňme si, že páskovou abecedu stroje M jsme nijak neomezovali, její znaky si na tuto zakódujeme v binární abecedě stejně, jako je tomu v kódu přechodové funkce M.

    • Ať b označuje délku nejdelšího zápisu znaku páskové abecedy v kódu w Turingova stroje M (dá se tedy s jistou rezervou říci, že hodnota b odpovídá \lceil log2 |Σ| \rceil, kde Σ je pásková abeceda simulovaného stroje M.

    • Pak tato páska bude rozdělena do bloků délky b oddělených symbolem „|“.

    • Každý blok bude kódovat obsah políčka pracovní pásky stroje M týmž způsobem, jakým je daný znak zakódovaný v kódu w přechodové funkce stroje M, doplněný nulami na začátku na délku b (jde o binárně zapsané číslo symbolu, jehož hodnotu nuly přidané na začátek nemění).

    • Polohu hlavy stroje M si UTS pamatuje polohou hlavy na této pracovní pásce.

  • Stavová páska M

    • stav, v němž se aktuálně stroj M nachází.

    • Stav <math>q_i</math> stroje M zakódován jako <math>(i)_B</math>

      • 💡 totéž číslo, co lze vyčíst z přechodové funkce M uložené v řetězci w na 1. pásce

Algoritmus UTS

  1. Init

    • kontrola vstupu: kontrola správnosti vstupní pásky

    • příprava prac.pásky: překódujeme vstup na pracovní pásku, návrat na začátek pásky

    • příprava stav.pásky: na stavovou pásku zapíšeme 0 (💡 binárně zapsané číslo stavu q0)

  2. Simulace

    • simuluj kroky M dokud ex. instrukce pro konfiguraci

  3. Zakončení

    • úklid: přepíše obsah pracovní pásky do abecedy {0,1}

    • konec: přečte stavovou pásku a podle stavu přejde do přijímacího/odmítacícího stavu

Alg. nerozhodnutelné problémy (🎓)

{{Zkazky|

  • (P. Kucera) Alg. nerozhodnutelne problemy - 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.

  • 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 nerozhodnutelne problemy - 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 - 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.

  • Halting problém (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.

  • 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.

  • Nerozhodnutelné problémy - Stačilo ukázat, že halting problém + definice co to vůbec je problém. Definoval jsem Postův korespondenční problém, pár doplnění, OK.

  • definice co to je problem, rozdil mezi rekurzivne spocetnym a rekurzivnim, Churchova teze a ekvivalence s TS, dale halting problem + ten snadny dukaz

}}

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>.

</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>):

  1. 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.

  2. 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.

PRF, ČRF, RP, RSP a vlast. (🎓)

Definice primitivně a částečně rekurzivních funkcí, rekurzivních a rekurzivně spočetných predikátů. Jejich základní vlastnosti - podmíněný příkaz, omezená minimalizace, uzavřenost na aritmetické operace, (ne)uzavřenost na logické spojky a kvantifikátory (omezené i neomezené). {{Zkazky|

  • Surynek - Základní definice, funkci x+y definovat jako ČRF, detaily ostrých inkluzí PRF/ORF/ČRF. Otázka: Je univerzální funkce pro třídu PRF také PRF? Ne, dokonce není ani ORF, protože nemůže být totální.

}}

Image:ZSV 1.jpg

!! funkce !! predikát !! množina !! problém
částečně rekurzivní /

podmíněná rovnost <math>f(x_1,..,x_n) \mathbf{≃} g(x_1,..,x_n)</math> znamená: hodnota <math>f(x_1,..,x_n)</math> je definována ⇔ definována i hodnota <math>g(x_1,..,x_n)</math>, a pak jsou si také rovny

{{zarovka |

  • h nabývá nejmenší hodnoty y, pro níž je f definováno a rovno 0. Navíc pro všechny hodnoty nižší než y musí být hodnota f definována.

  • Poslední proměnná ve funkci f má zvláštní význam. Snažíme se ji minimalizovat, to jest najít nejmenší y takové, aby f vracela nulu.

  • Pokud se jako f předá funkce, která nikdy nevrací nulu, tak operátor minimalizace vytvoří funkci, která nebude nikde definovaná

(výše uvedený pseudokód se zacyklí). To se u předchozích operátorů stát nemohlo: pokud dostaly na vstupu všude def. fce, vrátily také všude def. funkci.

  • Pokud nechceme zavádět nulární funkce, je nutné definici operátoru minimalizace doplnit o podmínku, že f je funkce alespoň dvou proměnných.

  • Místo <math>↓=</math> (zkratka za konverguje a rovná se) bychom v definici klidně mohli psát jen <math>=</math>. Použití <math>↓≠</math>

(zkratka za konverguje a nerovná se) je ale důležité, například pokud <math>f(x_1,...,x_n,0)↑</math>, tak <math>h(x_1,...,x_n)</math> také není definováno,

i kdyby třeba <math>f(x_1,...,x_n,1)=0</math>.

| minimalizace <math>M_n(f) = h</math> }}

Základní funkce:

  • nulová (konstantní) funkce <math>o(x) = 0</math>

  • následník <math>s(x) = x + 1</math>

  • projekce <math>I^j_n (x_1, .., x_j, .. , x_n) = x_j (∀j,n: 1 ≤ j ≤ n)</math> (💡 vrací hodnotu j-tého parametru)

Operátory:

  • substituce <math>S^m_n(f,g_1,...,g_m) = h</math> kde: <math>h(x_1,...,x_n) ≃ f(g_1(x_1,...,x_n),...,g_m(x_1,...,x_n))</math>

    • 💡 <math>f</math> má <math>m</math> proměnných a <math>g_1, .. , g_m</math> <math>n</math> proměnných

    • 💡 Operátor substituce je základní prvek programování — jednoduše úlohu, kterou mám řešit, vyřeším pomocí funkcí, které už naprogramoval někdo dřív.

  • primitivní rekurze <math>R_n(f,g) = h</math>

    • kde: <math>h(0, x_2, ..., x_n) ≃ f(x_2, ..., x_n)</math>

      <math>h(i+1, x-2, ..., x_n) ≃ g(i, h(i,x_2,...,x_n), x_2,..., x_n)</math>

    • 💡 f je fce n-1 proměnných a fce g n+1 proměnných (n ≥ 2)

    • 💡 operátor primitivní rekurze má sílu for-cyklu.

    • 💡 Proměnná x1 má zvláštní význam — slouží jako čítač

*minimalizace <math>M_n(f) = h</math> (má sílu while-cyklu)

<math>\mathbf{h}(x_1,...,x_n)\downarrow ≃ min \{ y|\mathbf{f}(x_1,...,x_n,y)\downarrow = 0 \quad a \quad \forall z<y: \mathbf{f}(x_1,...,x_n,z)\downarrow \ne 0\}</math>

  • μy[P(x,y)]- fce μ vrátí nejmenší y takové, aby platil predikát P(x,y)

    • Lze jí sestrojit pomocí operátoru minimalizace

PRF ⇐ lze odvodit ze 3 základních fcí a pomocí 2 op. substituce a prim. rekurze (NE minimalizace)

  • 💡 všude definována (=totální) - for-cykly (vždy konvergují)

  • 💡 PRF je ORF bez minimalizace

PRP (ORP) ⇐ ∃ pro něj PRF (ORF) charakteristická funkce

  • predikát <math>R(x_1,...,x_n)</math> je relace nebo libovolný fakt o n proměnných

  • charakteristická fce predikátu R je <math> \chi_P(x_1,\dots,x_n)\simeq \begin{cases}1 \quad & \mbox{ pokud } R(x_1,\dots,x_n) \\ 0 \quad & \mbox{ jinak }\end{cases}</math>

    • 💡 char. fce je ORF

  • 💡 (Obecně) PRM je unární (obecně) PRP.

ČRF (partial μ-recursive functions) ⇐ lze odvodit ze 3 základních funkcí pomocí 3 operátorů (💡 mají navíc while-cyklus ⇒ divergence)

  • ORF - je ČRF def. pro ∀ vstupy (totální)

RSP ⇐ ∃ pro něj ČRF charakteristická funkce

  • částečná char. fce (=ČRF) predikátu <math>R</math> je funkce <math>f_R : N^n → N</math>: <math>f_R(x_1, . . . , x_n)↓ ⇔ R(x_1, . . . , x_n), ∀(x_1, . . . , x_n) ∈ N</math>.

  • 💡 je def.oborem nějaké ČRF

Jejich základní vlastnosti

  • uzavřenost na aritmetické operace

    • (konečný součet a součin) f je PRF 2 proměnných ⇒ je PRF:

      • <math>g(z, x)=\sum_{y<z}f(y, x)</math> (přičemž <math>g(0, x)=0</math>)

      • <math>h(z,x)=\prod_{y<z}f(y, x)</math> (přičemž <math>h(0, x)=1</math>)

    • (důsledek) f je PRF 1 proměnné ⇒ je PRF:

      • <math>g(z)=\sum_{y<z}f(y)</math> (přičemž <math>g(0)=0</math>)

      • <math>h(z)=\prod_{y<z}f(y)</math> (přičemž <math>h(0)=1</math>)

  • (podmíněný příkaz) - analogie switch/case/if-then

**<math>g_1(x), \dots, g_n(x)</math>, <math>n>0</math> jsou PRF a <math>R_1(x), \dots, R_n(x)</math> jsou PRP a <math>\forall x\in{\mathbb N}</math> je splněn !1 z nich. **⇒ tato fce <math>f</math> je PRF: <math>\begin{align} f(x)=g_1(x)&\Leftrightarrow R_1(x)\\ f(x)=g_2(x)&\Leftrightarrow R_2(x)\\ &\vdots&\\ f(x)=g_n(x)&\Leftrightarrow R_n(x) \end{align}</math>

  • kvantifikátory (omezené i neomezené).

    • (omezená kvantifikace) <math>P</math> binární PRP ⇒ <math>V_P(z, x)=(\forall y<z)[P(y, x)]</math> a <math>E_P(z, x)=(\exists y<z)[P(y, x)]</math> jsou PRP.

    • (neomezená kvantifikace): P unární PRP⇒ (∃y)[P(y)] je RSP a (∀y)[P(y)] je doplněk RSP (∃y)[¬P (y)].

  • (ne)uzavřenost na logické spojky

    • (logické spojky)

    <math>P</math> a <math>R</math> unární PRP ⇒ <math>R\wedge P</math>, <math>R\vee P</math> a <math>\neg P</math> jsou PRP

    • (konečná konjunkce a disjunkce)

    <math>P</math> binární PRP ⇒ <math>A(x, z)=\bigwedge_{y<z}P(x, y)</math> a <math>B(x, z)=\bigvee_{y<z}P(x, y)</math> jsou PRP

  • (omezená minimalizace)

    <math>P</math> binární PRP ⇒ tato <math>f</math> je PRF:

    <math>f(x, z)= \begin{cases} \min\{y<z\;|\;P(x, y)\} \quad &\mbox{pokud takové y existuje}\\ z \quad &\mbox{jinak.} \end{cases} </math>

    Funkci <math>f</math> budeme také označovat pomocí <math>f(x, z)=\mu y<z[P(x, y)]</math>.

ČRF ⇔ TS, Kleene, UČRF, s-m-n (🎓)

Ekvivalence ČRF a Turingových strojů (na vyšší úrovni). Kleenova věta o normální formě (bez převodu ČRF na TS), univerzální ČRF, s-m-n věta.

{{Zkazky|

  • Tu ekvivalenci jsem napsal jen v bodech (stylem „zakóduju výpočet TS do stringu“, „sestavím predikát, který kontroluje, zda výpočet TS je korektní“, atd., fakt hodně po povrchu), rozepsal jsem jen to, jak se pomocí TS implementuje substituce, a taky mu to celkem stačilo (měl jsem v plánu toho napsat mnohem víc, tohle byl jen takovej začátek), jen se ptal, jak se něco udělá (nevím už přesně co, něco jako jak se překóduje string do binární reprezentace a zpátky, nevím jestli v TS nebo ČRF), tak jsme to společně nějak vymysleli, a dobrý.

  • (Loebl) - Ekvivalence ruznych definic algoritmicky vycislitelnych funkci - Moc jsem nevedel, co presne u tehle otazky bude chtit videt (jasne, Churchova teze, kterou jsem mimochodem nezformuloval tak uplne ciste spravne, ale dal?:) a tak jsem tam naflakal vsechno - CRF, ORF, PRF, RM, RSM, RSP, ORP, jazyky, DTS, NTS - CRF jsem odvodil ze zakladnich funkci pomoci operatoru, ukazal jsem inkluzi s ORF a PRF, naznacil jsem, jak si odpovidaji CRF a NTS a RSM, ORF a DTS a RM. Loebl byl velmi prijemny, prosel si to, chvili dumal nad tim, co se mnou (asi to nebylo uplne ono co chtel videt), rekl, ze tomu zjevne asi rozumim, ale, ze mu chybi nejake prakticke priklady a konkretni formalni prevody mezi vyjadrenimi a pak mi rekl, at mu tedy napisu jeste neco o UTS, pokud o nem neco vim. Nacrtnul jsem tu ctyrpaskovou konstrukci a kodovani UTS, ani jsem to nedopsal a rekl, ze staci.

  • Majerech, Algoritimicky vycislitelne funkce, definice, vlastnosti. Pana Majerecha jsem se bal, ale nakonec byl opravdu hodny! Zdalo se mi, ze poznal, ze tomu clovek rozumi, par otazek a dal se jiz na nic neptal. Napsal jsem definice pres funkce/operatory, pres TS, dale pak mnoziny/predikaty/jazyky. Inkluze + co za funkce jsou, aby to nebylo ostre [bez definovani], par otazek na overeni, ze tomu rozumim a vse ok. Zadne detaily ci Velmi prijemne zkouseni. Behem zkouseni si k nam prisedl i Martin Mares, ktereho to evidentne bavilo a dokonce mi i jednou napovedel :-) Znamka: 1

*Loebl (SV) -- Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Částečně rekurzivní funkce. - Churchova-Turingova teze. Definoval jsem TS a popsal, jak počítá. Rekurzivně spočetné/rekurzivní jazyky. Postova věta. Definice PRF, ORF, ČRF (a predikáty) - zmínit, jakým programovacím konstruktům odpovídají odvozovací fce. Základní lemmata (konečný součet, popis ekvivalentní fce pro switch, atd.). Nakonec bez důkazu, že ČRF a TS jsou ekvivalentně silné. Ptal se na existenci UTS (stačila idea). Vše jsem měl přesně, takže řekl, že mu to stačí na 1. }}

otázky: vyšší úroveň? , bez převodu ČRF na TS? , smn důkaz? jak se něco udělá (nevím už přesně co, něco jako jak se překóduje string do binární reprezentace a zpátky, nevím jestli v TS nebo ČRF)

💡 efektivně vyčíslitelné = turingovsky vyčíslitelné = algoritmicky vyčíslitelné = algoritmicky řešitelné

Ekvivalence ČRF a TS (na vyšší úrovni)

{{theorem | <math>h</math> je ČRF <math>n</math> proměnných ⇒ <math>h</math> je Turingovsky vyčíslitelná

| ČRF ⇒ TS }}

:💡 Přesněji, existuje Turingův stroj <math>M_h</math> takový, že pro každou <math>n</math>-tici přirozených čísel <math>x_1, x_2, \dots, x_n</math> platí

<math>M_h((x_1)_B\#(x_2)_B\#\dots\# (x_n)_B)\downarrow\Leftrightarrow h(x_1, x_2, \dots, x_n)\downarrow</math>

a platí-li <math>h(x_1, x_2, \dots, x_n)\downarrow=y</math>, potom výpočet Turingova stroje <math>M_h</math> vydá na výstupu řetězec <math>(y)_B</math>.

Dk (konstrukcí TS, )

definujeme TS pro základní funkce a operátory pro odvození <math>h</math>:

  • Základní fce (nulová, následník, projekce) implementuji (vyčíslím) pomocí TS

  • Operátory simuluji na 3 pásk. TS: substituci, primitivní rekurzi jako for-cyklus (počítadlem cyklů), minimalizaci jako while-cyklus (taky počítadlem cyklů)

{{theorem

| Převod je navíc možno učinit efektivně. Jinými slovy, existuje Turingův stroj CRF2TS, který pokud na vstupu dostane kód ČRF <math>h</math>, spočítá Gödelovo číslo <math>e</math> stroje <math>M_e</math>, který počítá funkci <math>h</math>. | 💡

}}

{{theorem

| funkce <math>f</math> turingovsky vyčíslitelná ⇒ je <math>f</math> ČRF | TS ⇒ ČRF

}}

Dk (jeden krok TS je PR - omezené cykly, TS pracuje, dokud neskončí = while-cyklus (tj. minimalizace), tedy program = minimalizace čehosi, kde to cosi už je PR)
  • předpoklady: f je def. jako tur. vyčíslitelná ⇒ ∃ TS <math>M_e</math> co jí počítá (💡 to je z definice tur.vyčíslitelnosti)

  • zakóduju výpočet (tj: posloupnost konfigurací Ki) TS do stringu: K1;...;Kt

{{TODO|jak se to dělá?}}

  • sestavím PRP T(g.č.TS, x, g.č.kódu výpočtu TS), který kontroluje, zda daný řetězec kódu TS kóduje výpočet TS nad vstupem x

  • na predikát pustím minimalizaci y (<math>\mu y[T(e, x, y)]</math>)

  • pomocí fce <math>\cal U</math> z ní vytáhnu g.číslo poslední konfigurace

  • tedy <math>f(x)=\cal U(\mu y[T(e, x, y)])</math>

💡 U je zřejmě PRF

Kleenova věta o n.f. (bez převodu ČRF na TS)

<math>\mathbf{ \varphi_e^{(n)}}</math> je ČRF <math>n</math> proměnných, kterou počítá stroj <math>M_e</math> {{theorem

| <math>\exists PRF \quad \cal U(y)</math> a PRP <math>T_n(e, x_1, \dots, x_n, y)</math>, pro které platí: <math>(\forall n\in\mathbb N) (\forall e\in{\mathbb N})\; \varphi_e^{(n)}(x_1, \dots, x_n) \simeq\cal U(\mu y[T_n(e, x_1, \dots, x_n, y)])</math>

| Kleenova věta o normální formě }}

💡 neboli, každý program se dá zjednodušit na 1 while cyklus :)

Dk

:podle důkazu TS ⇒ ČRF {{theorem

| <math>R</math> je RSP <math>\Leftrightarrow \exists</math> PRP <math>P</math> tak, že: <math>R(x_1, \dots, x_n)\Leftrightarrow(\exists y)[P(x_1, \dots, x_n, y)]</math> | důsledek Kleeneho věty

}} 💡 RP jsou ty, které jsou algoritmicky rozhodnutelné, RSP jsou ty, které jsou algoritmicky ověřitelné, podá-li nám někdo certifikát (tedy <math>y</math>) dokazující jejich platnost. Tedy u RSP nejsme sice obecně schopni efektivně rozhodnout, jestli platí, ale pokud platí a někdo nám dá svědka <math>y</math> stvrzující tento fakt, jsme schopni efektivně ověřit, že jde skutečně o certifikát platnosti.

univerzální ČRF

{{theorem | <math>\forall</math> třídu proměnných <math>n>0</math> <math>\exists</math> univerzální ČRF: <math>\varphi_z^{(n+1)}(e, x_1, \dots, x_n)</math> taková, že <math>\varphi_z^{(n+1)}(e, x_1, \dots, x_n)=\varphi_e^{(n)}(x_1, \dots, x_n)</math> (tedy vyčísluje e-tou funkci)

| O univerzální funkci }}

💡 existuje i univerzální funkce, a to pro každou třídu <math>n</math> proměnných (takže ta univerzální funkce pak dostane těch <math>n</math> proměnných + číslo funkce, kterou má emulovat, a udělá to), přičemž je docela pěkná (je ve tvaru minimalizace PRP)

Dk(podle Kleeneovy)

<math>\varphi_z^{(n+1)}(e, x_1, \dots, x_n) \simeq \cal{U}(\mu y[T_n(e, x_1, \dots, x_n, y)])</math>

💡 Nicméně vzhledem k ekvivalenci ČRF a TS bychom také mohli vzít již zkonstruovaný univerzální TS a jemu odpovídající ČRF.

''s''<sub>n</sub><sup>m</sup> věta

<math>\mathbf{ \varphi_e^{(n)}}</math> je ČRF <math>n</math> proměnných, kterou počítá stroj <math>M_e</math>

Churchovo <math>\lambda</math>-značení . Je-li <math>V</math> výraz, pak pomocí <math>\lambda_{ x_1x_2...x_n}V</math> označíme funkci na proměnných <math>x_1, x_2, \dots, x_n</math>, která je daná výrazem <math>V</math>.

{{theorem _ | <math>\forall</math> m,n > 0 <math>\exists</math> prostá PRF <math>s_n^m</math> a <math>\forall x, y_1, \dots, y_m</math> platí: <math>\varphi^{(n)}_{s_n^m(x,y_1,.., y_m)} = \lambda z_1..z_n[\varphi_x^{(m+n)}(y_1, .., y_m, z_1, .., z_n)]</math>

| snm }}

:💡  říká, že pokud v naší univerzální funkci, která má <math>m+n</math> sadu argumentů (jedním z nich je číslo programu, který má běžet),

<math>m</math> argumentů (+ číslo programu) zafixujeme,

dostaneme funkci zbytku (<math>n</math>) těch argumentů,

a tato fixovací funkce bude hezká (prostá PRF).

Dk (program <math>s=s_n^m(x, y_1, \dots, y_m)</math>, na vstupu dostane z-ka a pak pustí TS <math>M_x</math> na vstup y-nek a z-tek)

Neformálně popíšeme, co bude dělá program <math>s=s_n^m(x, y_1, \dots, y_m)</math>:

Na vstupu dostane čísla <math>z_1, . . . , z_n</math>, poté spustí stroj <math>M_x</math> na vstup <math>y_1, . . . , y_m, z_1, z_2, . . . , z_n</math>,

💡 Všechna tato čísla zná, jelikož je buď dostane na vstupu <math>M_s</math> (v případě <math>z_1, . . . , z_n</math>), nebo je má zakódované do své přechodové funkce jako parametry (v případě <math>x, y_1, \dots, y_m</math>).

💡 Pro tuto úpravu není vůbec rozhodující, jak vypadají instrukce <math>M_x</math>, ani to, jak bude probíhat jeho výpočet, jediné, co je v <math>M_x</math> třeba změnit jsou čísla stavů tak, aby nekolidovala s nově přidanými stavy.

  • Úprava přechodové funkce <math>M_x</math> je jednoduchá a vystačí si s PR prostředky ⇒ <math>s_n^m</math> je PRF.

  • Kód nového stroje obsahuje nějakým způsobem i hodnoty parametrů fce <math>s_n^m</math>, pro různé hodnoty těchto parametrů budou i různé výstupní hodnoty ⇒ <math>s_n^m</math> je prostá.

další zdroje

  • http://wiki.matfyz.cz/index.php?title=St%C3%A1tnice_-_Algoritmicky_vy%C4%8D%C3%ADsliteln%C3%A9_funkce

Základní vlast. RM a RSM. (🎓)

Základní vlastnosti rekurzivních a rekurzivně spočetných množin. (Ne)uzavřenost na sjednocení, průnik a doplněk. Postova věta v kontextu množin. Existenční kvantifikátor a výběrová funkce. {{Zkazky|

  • (inicialy JM... zeby Mlcek?) - Rekurzivne funkcie a rekurzivne spocetne mnoziny (nie je to priamo otazka z poziadavkov, nejak som mal proste rozpravat o danej teme), uz pri zadavani mi vravel, ze si mam pripravit vela prikladov, na co je to dobre. Zadefinoval som elementarne funkcie a operatory, vyznam operatorov(for, while), PRF,ORF,CRF, inkluzie a priklady funkcii, kvoli ktorym su inkluzie ostre, definoval som rekurzivne a r.spocetne mnoziny a uviedol som tam znenie tej dlhej vety o vlastnostiach r.s. mnozin. Na zaver som pridal nieco o halting probleme ako priklad vyuzitia celej tej teorie. Skusajuci si to pozrel, nemal nejake pripomienky a zacal sa pytat na tie priklady, tak som povedal ten halting problem, ekvivalenciu programov a este sa pytal, ci existuje funkcia, ktora nie je ani CRF - to som nejak previedol na TS a povedal, ze napriklad diagonalizacny jazyk. Toto mu stacilo, bolo to celkom v pohode.

  • RS a RSM mnoziny, prevoditelnosti - pri zadani spominal aj simple a kreativne, ale nastastie sme sa az tam nedostali, to som sa uz neucil. Definicia zakladnych fcii, operatorov, definicia RS RSM mnozin, potom ze to je ekvivalentne s generovanim pomocou oborov hodnot, tie vety o vztahu rng a RSM, vzdy sa opytal aj na myslienku dokazu. Postova veta (tam sa mu viac pacila odpoved 'pustime dva programy a cakame, ktory skor zastane' nez ten predikat, ktoreho potom selektor je char fciou), potom som zadefinoval 1- a m-prevoditelnost, 1-uplnost, dokazal, ze K je 1-uplna, napisal halting problem a Kryl odchadzal spokojny.

  • Majerech - CRF + RM + RSM - tady jsem kliku, ze jsem si vylosoval zrovna toto, ptz jinak bych tam mohl u Majerecha sedet doted.:) Vypsal jsem vsechny ty definice, nejdulezitejsi vety (Postovu jsem si dovolil i dokazat, coz je u me velmi nezvykle) a ruzna tvrzeni okolo, na ktere jsem si vzpomnel. Ptal se na usekovou fci a generovani bodu - to jsem tapal a radsi hned rekl, ze nevim (jak toto muze byt nekdy osvobozujici:) a zlehka nejake uzaverove vlastnosti. 1-

*Napsal jsem: **definice RM, RSM vč. definice ORF a ČRF (s drobnou chybou – dal jsem dohromady prvky a operátory nad funkcemi),

**generování (tři věty o oborech hodnot) (Tady se mě ptal, jak fungují ty programy pomocí kterých množiny generuji. Neměl jsem to rozmyšlené, takže to ze mě musel tahat a část říct), **1-převoditelnost, 1-úplnost, K je 1-úplná. Ptal se mě, k čemu ta 1-převoditelnost je. Dával mi návodné otázky a potom jsem si končeně vzpomněl, že asi myslí to, že můžu převést jednu množinu na druhou. Jen tak mimochodem se ptal, kolik je RM a kolik RSM.

**Všechno jsem psal bez důkazu a nechyběly mu. Nakonec mi řekl, že to mám tak za 1− a jestli chci čistou 1, tak ať mu formálně dokážu, že K je 1-úplná. Řekl jsem mu, že o 1 mi až tak nejde. }}

charakteristická funkce <math>χ_A(x)</math> -- charakteristická fce predikátu náležení do množiny (<math>χ_A(x) = \downarrow 1</math> pro <math>x\in A</math> a <math>χ_A(x) \downarrow = 0</math> pro <math>x\notin A</math>) <math>χ_A(x_1,\dots,x_n)\simeq \begin{cases}1 \quad & \mbox{ pokud } R(x_1,\dots,x_n) \\ 0 \quad & \mbox{ jinak }\end{cases}\,\!</math>

::💡 částečná charakteristická funkce množiny -- <math>χ_A(x) = \downarrow 1</math> pro <math> x \in A</math> a <math>χ_A(x)\uparrow</math> pro <math>x \notin A</math> <math> dom\,\!</math> značí definiční obor, <math> rng\,\!</math> obor hodnot

RM A ⊆ ℕ ⇐ je-li def. oborem ORF

💡 také nazýváme jako unární RP (příklad: binarni predikat je mnozina dvojic, ale unarni predikat je mnozina prvku)

💡 tj.: char.fce <math>χ_A(x)</math> je ORF

RSM A ⊆ ℕ ⇐ je-li def. oborem ČRF

💡 také nazýváme jako unární RSP

💡 tj: A = dom ČRF f = {x | f(x)↓}

e-tá RSM <math>\mathbf{W_e} = dom~ φ_e = \{ x | φ_e(x)↓ \}</math>

Pomocí <math>\varphi^{(n)}_{e, s}</math>, kde <math>e, n,s\in{\mathbb N}</math> označíme konečnou aproximaci <math>\varphi_{e, s}^{(n)}</math> funkce <math>\varphi_e^{(n)}</math>, kterou definujeme následujícím způsobem:

::<math>\varphi^{(n)}_{e, s}(x_1, \dots, x_n)\simeq \begin{cases} \varphi^{(n)}_e(x_1, \dots, x_n) \quad & \mbox{pokud }(\exists y<s)[T_n(e, x_1, \dots, x_n, y)]\\ \uparrow\quad & jinak \end{cases}</math>

rekurzivní konečná aproximace <math>\mathbf{W_{e,s}} = dom φ_{e,s} = \{ x | φ_{e,s}(x)↓ \}</math>

{{lemma

| Predikát <math>H</math> definovaný jako <math>H (e, s, x_1, . . , x_n) ⇔ φ_{e,s}(n)(x_1, . . , x_n)↓</math> je PRP a platí, že: <math>φ_e(n) (x_1, . . . , x_n)↓⇔ (∃s)[ φ_{e,s}(n) (x_1, . . , x_n)↓]</math> . (v dk předpokladáme, že <math>T_n</math> z Kleenovy věty je PRP a omezená kvantifikace je PR.) }}

{{theorem

| RM jsou uzavřeny na sjednocení, průnik a operaci doplňku | RM - uzavřenost na ∪, ∩ a doplňek

}}

Dk

předpokládáme, že signum, součet, součin a opatrné odčítání 1 (predecessor) jsou PRF/ORF :

<math>A∪B=\{x|[χ_a(x)∨χ_b(x)]\}</math>

<math>A∩B=\{x|[sign(χ_a(x)+χ_b(x))]\}</math>

<math>\overline A=\{x|[1\dot{-}χ_a(x)]\}</math>

💡 tj: Ten samý jako pri logických operacích pro PRP, jenomže pro unární ORP (rekurzivní množiny). Platí: χA ∩ B(x) = χA(x).χB(x), χP ∩ R(x) = sign(χA(x) + χB(x)), χA(x) = 1 −• χA(x).

{{theorem

| Rekurzivně spočetné množiny jsou efektivně uzavřené na sjednocení a průnik, nikoliv na průnik. | RSM - uzavřenost na ∪, ∩ ale NE na doplňek

}}

Dk

A∪B - pustíme oba TS současně a když 1 skončí vstup patří do sjednocení

A∩B - čekám na zastavení obou

💡 tj: Uvažme nejprve sjednocení a funkci f(x, y). Nechť e-tý program počítá následovně. Pro daný vstup x, y, u hledej nejmenší limit s, který již stačí, aby u patřilo do Wx,s nebo do Wy,s. Tedy φe(x, y, u) ≃ μs[u ∈ Wx,s ∨ u ∈ Wy,s]. Z vlastností konečných aproximací, vyplývá, že predikát použitý jako podmínka minimalizace je PRP. Platí tedy, že φe(x, y, u)↓ ⇔ u ∈ Wx ∪ Wy. Program s číslem e je konkrétní program, který sestrojíme s pomocí univerzální ČRF. Funkci f dostaneme pomocí s-m-n věty jako <math>f(x, y) = s_1^2(e, x, y)</math>. Podobně můžeme postupovat i v případě průniku a funkce g, stačilo by místo disjunkce použít konjunkci.

{{theorem

| <math>A</math> je RM <math>\Leftrightarrow A</math> i <math>\overline A={\mathbb N}\setminus A</math> jsou RSM | Postova věta v kontextu množin

}}

Dk

:⇒ A je RM: A = dom μy[(λxy[1 ∸ χA(x)])≃0]

A' je RSM: A = dom μy[(λxy[χA(x)])≃0]

:⇐ paralelni beh obou char. funkci, jedna dobehne ::μs[x∈Wi,s ∨ x∈Wj,s]

Kódování uspořádaných dvojic, n-tic:

  • <math>⟨x, y⟩_2</math> je kód uspořádané dvojice [x, y] daný: <math>⟨x, y⟩_2 = (x + y).(x + y + 1) / 2 + x</math>

  • <math>⟨x_1, . ., x_n⟩_n</math> je kód uspořádané n-tice daný: <math>⟨x_1, . . ., x_n⟩_n = ⟨x_1, ⟨x_2, . . ., x_n⟩_{n-1}⟩_2</math>

  • <math>π_{n,i}(⟨x_1, . ., x_n⟩_n) = x_i</math> je inverze pro výběr <math>i</math>-tého prvku ze zakódované <math>n</math>-tice

  • Lemma – Pro každé <math>n ≥ 2, i ≤ n</math> jsou funkce <math>⟨x_1, . . . , x_n⟩_n</math> a <math>π_n</math> PRF, a <math>⟨x_1, . . . , x_n⟩_n</math> je bijekcí mezi <math>N^{n+1}</math> a <math>N</math> ( důkaz pro πn předpokládá, že omezená minimalizace a kvantifikace jsou PRF ).

{{theorem

| Predikát <math>R ⊆ N^n</math> je RSP ⇔ ∃ PRP <math>P ⊆ N^{n+1}</math> , že: <math>R(x_1, . . , x_n) ⇔ (∃y)[P (x_1, . . , x_n, y)]</math>. | důsledek Kleeneho věty

}} {{theorem

| <math>P(x_1, \dots, x_n, y)</math> je RSP ⇒ <math>R(x_1, \dots, x_n)=(\exists y)\;[P(x_1, \dots, x_n, y)]</math> je RSP | RSP jsou uzavřeny na ∃ kvantifikátor

}}

Dk

Protože <math>P(x, y)</math> je RSP, můžeme jej zapsat podle důsledku Kleeneho jako <math>P(x, y) = (∃z) [Q(x, y, z)]</math>, kde <math>Q</math> je PRP. Z toho plyne, že <math>R(x) = (∃y)(∃z) [Q(x, y, z)]= (∃⟨y, z⟩_2) [Q(x, y, z)]</math>.

Označíme-li si <math>D(x, u) = Q(x, π_{2,1}(u), π_{2,2}(u))</math>, pak <math>D</math> je PRP, pro který platí, že <math>R(x) = (∃u) D(x, u)</math>.

⇒ podle důsledku Kleeneho: <math>R(x)</math> je RSP.

{{theorem

| <math>R(x, y)</math> je RSP ⇒ <math>\exists</math> ČRF <math>f</math> (také výběrová funkce nebo selektor pro <math>R</math>), že <math>f(x)\downarrow\Leftrightarrow(\exists y)R(x, y)</math> a pokud <math>f(x)\downarrow</math>, pak <math>R(x, f(x))</math>. | výběrová funkce

}} 💡 <math>\exists f</math> implementující <math>\exists y </math> na predikátu <math>R(x, y)</math>

Dk

Podle důsledku Kleeneho můžeme <math>R</math> zapsat jako <math>R(x, y) = (∃z)[Q(x, y, z)]</math> pro nějaký PRP <math>Q</math>. A tedy <math>(∃y)R(x, y) ⇔ (∃y)(∃z)Q(x, y, z)</math>. Protože predikát <math>Q</math> je PRP(totální), dostaneme, že funkce <math>g(x) ≃ μ⟨y, z⟩_2 Q(x, y, z)</math>.

Nyní z nalezené hodnoty stačí vybrat <math>y</math>, tedy 1. prvek, celkově tedy definujeme funkci <math>f</math> jako <math>f(x) ≃ π_{2,1}(g(x))</math>.

další zdroje

7. RM = ''rng'' rost. úsekové ČRF (🎓)

Rekurzivní množina jako obor hodnot rostoucí úsekové funkce.

<math>f</math> je úseková fce, pokud její definiční obor tvoří počáteční úsek <math> \mathbb N\,\!</math>

{{theorem | A je RM <math>\Leftrightarrow</math> je oborem hodnot nějaké rostoucí úsekové ČRF

| <math>RM = rng</math> rostoucí úsekové ČRF }}

Dk (oběma směry - neformálně, )

<math> \Rightarrow\,\!</math>: Předpokládejme nejprve, že <math>A</math> je RM. Zkonstruujeme rostoucí, úsekovou ČRF <math> f(i)</math> = "vrať <math>i</math>-tý nejmenší prvek z <math>A</math>".

  • Začneme <math> f(0) \simeq \mu x(x\in A)\,\!</math>.

  • Dále <math> f(n+1) \simeq \mu x(x > f(n) \wedge x \in A)\,\!</math>

<math> \Leftarrow\,\!</math>: Nyní předpokládejme, že <math>A = rng f</math>, kde <math> f\,\!</math> je rostoucí úsekovou ČRF.

  1. Pokud <math>f</math> není ORF, znamená to že <math> f\,\!</math> má konečné <math> dom\,\!</math> (z def. úsekové fce), a tedy je konečná i samotná množina <math>A</math> a je tedy triviálně rekurzivní.

  2. Pokud je <math>f</math> ORF je všude definovaná (totální): <math> y \in A=rng f \Leftrightarrow \exists x:f(x)=y \Leftrightarrow \exists x\!\leq\!y: f(x)=y </math>. Poslední ekvivalence platí, protože <math> f\,\!</math> je rostoucí a úseková. Tedy <math> y \in A \Leftrightarrow y \in \{f(0),\ldots,f(y)\}. </math>

💡 Důsledek: Nechť <math>A</math> je ∞ množina: <math>A</math> je <math>RM ⇔ A=rng</math> nějaké rostoucí ORF. (protože úsekové funkce s nekonečnou doménou musí být všude definované = totální)

RSM = ''rng'' ORF, či ČRF (🎓)

Rekurzivně spočetná množina jako obor hodnot obecně rekurzivní funkce, či částečně rekurzivní funkce. {{Zkazky|

  • Funckia f je CRF ⇔ jej graf je RSM

    • Na ustnej sa ma pytal (kedze som to tam nemal uplne jasne vysvetlene, hlavne ze preco je riesenie korektne v jednom ⇔ ak je v prevedenom) veci ohladne toho, ale dost ma navadzal a spolu s nim som to tam aj vymyslel.

    • mi prošla bez dotazů, jsou to dvě věty, tak nějak jsem nastínil i důkazy, jen na pár řádek, zřejmě mu stačilo vidět myšlenku

}}

{{theorem | Následující tvrzení jsou ekvivalentní:

  1. A je RSM.

  2. A je ∅, nebo je <math>rng</math> nějaké ORF

  3. A je <math>rng</math> nějaké ČRF.

  4. A je <math>rng</math> nějaké rostoucí ČRF.

| Generování RSM }}

Dk (neformální, )

<math>1. ⇒ 2.</math> (konstrukce ORF co pro jakékoli vstupy vrací prvky z A):

<math>g(z) ≃ φ_{s-1-1 (e1,e)}(z) ≃ φ_{e1}(e, z = ⟨x, s⟩_2) ≃ \begin{cases}x \quad & x ∈ W_{e,s} \\ π_{2,1}(μ⟨x, s⟩_2[x ∈ W_{e,s}])\quad & \mbox{ jinak }\end{cases} </math>.

Každý prvek <math>W_e</math> je tedy funkcí <math>g</math> pro nějaký vstup <math>y</math> vrácen, jenom nedokážeme odhadnout, pro jak velké <math>y</math>. Dohromady dostáváme, že <math>A = W_e = rng~ g</math>.

<math>2. ⇒ 3.</math> : Plyne z toho, že každá ORF je i ČRF. ∅ je oborem hodnot ČRF, která není definovaná pro žádný vstup.

<math>3. ⇒ 1.</math> (pomocí částečné aproximace vyrobíme z ČRF RSP => RSM): Předpokládejme, že <math>A</math> je oborem hodnot ČRF <math>g ≃ φ_e</math>.

Uvědomme si, že rozhodnutí, zda <math>g(y)↓= x</math> je RSP (plyne například z toho, že <math>φ_{e,s}(y)↓ = x</math> je PRP a tedy <math>g(y)↓ = x ⇔ (∃s)[φe,s(y)↓= x]</math> je RSP, dále je tedy i <math>(∃y)[g(y)↓ = x]</math> RSP, a tedy množina <math>A = \{x | (∃y)[g(y)↓ = x]\}</math> je RSM. Ze znalosti GČ <math>e</math> funkce <math>g</math> bychom opět s pomocí s-m-n věty mohli spočítat GČ funkce, jejíž doménou množina <math>A</math> je. Pro úplnost totiž můžeme past <math>A = dom~ λx [ μ⟨y, s⟩_2[φ_{e,s}(y)↓= x] ]</math>.

<math>1. ⇒ 4.</math> (zkonstruujeme triviální rostoucí ČRF <math>h(x)=g(e,x)</math> u které se <math>dom</math>=<math>rng</math>) : Předpokládejme, že <math>A = W_e</math>, tedy <math>A = dom φ_e</math>. Buď <math>g(e, x)</math> fce definovaná jako:

<math>g(e, x) = \begin{cases}x \quad & x ∈ W_e \\ ↑ \quad & \mbox{ jinak }\end{cases}</math>.

Funkce <math>g(e, x)</math> je zřejmě ČRF, například proto, že ji lze zapsat jako <math>g(e, x) = o(φ_e(x)) + x</math> (tj. do nulové funkce vložíme <math>φ_e(x)</math> jako argument, hodnota tedy na hodnote <math>φ_e(x)</math> nezávisí, definovatelnost ano). Položme nyní <math>h(x) = g(e, x)</math>, potom je <math>A</math> jak oborem hodnot, tak definičním oborem funkce <math>h</math>, funkce <math>h</math> je rostoucí ČRF, jejíž GČ lze opět efektivně spočítat z <math>e</math>.

<math>4. ⇒ 3.</math> : Toto je zřejmé. Implikaci <math>(3. ⇒ 1.)</math> už máme hotovou.

{{TODO}}

1=>3 :Pro každou množinu <math>W_x</math> vytvoříme množinu dvojic <math> R=\{\langle y,y\rangle:y \in W_x\}\,\!</math>. Množina <math> R\,\!</math> je rekurzivně spočetná, tedy má ČRF selektor <math> \varphi\,\!</math>, :platí <math> dom(\varphi)=rng(\varphi)=W_x\,\!</math>.

:Myšlenka toho důkazu je, že body, kde <math> \varphi_x\,\!</math> konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude zárověň jeho oborem hodnot.

1<=3 :Máme ČRF <math> g\,\!</math> a její obor hodnot. Zkonstruujeme pseudoinverzní funkci <math> h\,\!</math> k ČRF <math> g\,\!</math>, tj. funkci takovou, že <math> dom(h)=rng(g)\,\!</math> a to tak, že vyrobíme RS :predikát <math> Q(x,y)\Leftrightarrow g(x)\simeq y\,\!</math> a to má ČRF selektor, který hledáme -- <math> h\,\!</math>.

≤<sub>1</sub>, ≤<sub>m</sub> a jejich vlastnosti, ''K'' a ''K<sub>0</sub>'' 1-úplné, RSM a ¬RM.

1-převoditelnost, m-převoditelnost a jejich vlastnosti, 1-úplnost množin K a K0. Množiny K a K0 jsou rekurzivně spočetné, ale nejsou rekurzivní.

<math>A\leq_m B</math> (množina <math>A</math> je <math>m</math>-převoditelná na <math>B</math>) pokud ∃ ORF <math>f</math>, tž: <math>∀ x: x ∈ A ⇔ f(x) ∈ B</math>

<math>A\leq_1 B</math> (množina <math>A</math> je <math>1</math>-převoditelná na <math>B</math>) je-li <math>f</math> navíc prostá

množina <math>A</math> je <math>m</math>-úplná (resp. <math>1</math>-úplná) pro třídu RSM pokud: je <math>A</math> RSM a ∀ jiná RSM je na ni <math>m</math>-převoditelná (resp. <math>1</math>-převoditelná).

💡 budeme říkat pouze <math>A</math> je <math>m</math>-úplná nebo <math>1</math>-úplná, dodatek „pro třídu RSM“ budeme vynechávat, protože jinými než RM a RSM se nebudeme zabývat.

9.1 vlastnosti ≤<sub>1</sub>, ≤<sub>m</sub>

  • <math>A\leq_m B</math> a <math>B</math> RM <math>\Rightarrow A</math> RM

    💡 <math>A\leq_m B</math> a <math>A</math> není RM <math>\Rightarrow B</math> není RM (protože: <math>(A\Rightarrow B)=(\neg B\Rightarrow \neg A)</math>)

    Dk: Je-li <math>B</math> RM a <math>f</math> je ORF převádějící <math>A</math> na <math>B</math>, pak <math>x ∈ A ⇔ f(x) ∈ B</math> a tedy <math>χ_A(x) = χ_B(f(x))</math>. <math>χ_A</math> je jistě ORF a tedy <math>A</math> je RM.

  • <math>A\leq_m B</math> a <math>B</math> RSM <math>\Rightarrow A</math> RSM

    💡 <math>A\leq_m B</math> a <math>A</math> není RSM <math>\Rightarrow B</math> není RSM

    Dk: Je-li <math>B</math> RSM a platí-li <math>B = dom φ_e</math> a je-li <math>f</math> ORF, která převádí <math>A</math> na <math>B</math>, pak <math>A = dom λx[φe(f(x))]</math> a jde tedy o RSM.

  • <math>\leq_m</math> a <math>\leq_1</math> (relace) jsou reflexivní a tranzitivní

    Dk: To, že jsou <math>≤_m</math> a <math>≤_1</math> reflexivní relace plyne z toho, že identita je prostá ORF. Předpokládejme, že <math>A ≤_1 B</math> a <math>B ≤_1 C</math>, nechť <math>f</math> je prostá ORF převádějící <math>A</math> na <math>B</math> a <math>g</math> buď prostá ORF převádějící <math>B</math> na <math>C</math>. Pak <math>h(x) = g(f(x))</math> je prostá ORF která převádí <math>A</math> na <math>C</math>, což ukazuje, že <math>≤_1</math> je tranzitivní. Pro <math>≤_m</math> platí týž argument s vynecháním prostoty.

  • <math>A</math> <math>m</math>-úplná & <math>B</math> RSM & <math>A\leq_m B \Rightarrow B</math> je <math>m</math>-úplná

    💡 platí pro 1-převoditelnost a 1-úplnost

    Dk: Toto plyne okamžitě z tranzitivity <math>≤_m</math>, <math>≤_1</math> a definice úplnosti.

  • <math>A\leq_mB \Rightarrow \overline A\leq_m\overline B</math>

    💡 platí pro 1-převoditelnost a 1-úplnost

    Dk: Plyne přímo z definice převoditelnosti, převod <math>A</math> na <math>B</math> zajistí stejná funkce jako převod <math>A</math> na <math>B</math>.

Problém zastavení K<sub>0</sub> a jeho diagonála K

<math>K_0 =\{\langle x, y\rangle_2\;|\;\varphi_x(y)\downarrow\}=\{\langle x, y\rangle_2\;|\;y\in W_x\} </math> - problém zastavení

<math>K =\{x\;|\;\varphi_x(x)\downarrow\}=\{x\;|\;x\in W_x\}</math> - diagonála <math>K_0</math>

💡 <math>K_1 =\{x\;|\;W_x\neq\emptyset\} </math>

{{theorem | <math>K</math> a <math>K_0</math> jsou RSM, ale nejsou RM

| <math>K</math>, <math>K_0</math> RSM <math>\neg</math>RM }}

Dk (sporem jako u TS)

Z definice jsou obě RSM. Nechť <math>φ_z</math> označuje univerzální ČRF.

<math>K = dom λx[φ_z(x, x)]</math>. Pro spor <math>K</math> je RM ⇒ <math>\overline K</math> je RSM.

Nechť <math>φ_e</math> je ČRF, pro níž <math>\overline K = dom φ_e</math> a ptejme se, zda <math>e ∈ \overline K</math> nebo ne:

Z def. <math>K</math> ⇒ <math>e ∈ \overline K ⇔ φ_e(e)↑</math>

<math>\overline K = dom φ_e</math> ⇒ <math>e ∈ \overline K ⇔ φ_e(e)↓</math>

⇒ <math>φ_e(e)↓ ⇔ φ_e(e)↑</math> ⇒ SPOR ⇒ <math>K</math> tedy není RM.

<math>K_0 = dom λ⟨x, y⟩_2[φ_z(x, y)]</math>. Pro spor <math>K_0</math> je RM a <math>χ_{K0}</math> je její char. ORF:

Definujeme <math>χ_{K}(x) = χ_{K_0}(⟨x, x⟩_2)</math> ⇒ <math>χ_K</math> char. ORF <math>K</math> ⇒ SPOR s tím že <math>K</math> není RM. ⇒ <math>K_0</math> tedy není RM.

{{theorem

| Množiny <math>K</math> a <math>K_0</math> jsou 1-úplné. | 1-úplnost <math>K</math>, <math>K_0</math>

}}

Dk

<math>K</math> je <math>1</math>-úplná: <math>K</math> je RSM, stačí tedy ukázat, že libovolnou RSM lze na <math>K</math> převést prostou ORF.

Definujme funkci <math>φ_{e1}(e, x, y) ≃ φ_e(x)</math>. Podle s-m-n věty <math>φ_{s^2_1(e1,e,x)} (y) ≃ φ_e (e, x, y) ≃ φ_e(x)</math>. Definujme tedy funkci <math>f(e, x) = s_1^2(e_1, e, x)</math>. Protože <math>s_1^2</math> je prostá PRF, je i <math>f</math> prostá PRF. Navíc platí, že <math>φ_{f(e,x)}</math> je buď všude definovaná konstantní funkce, pokud <math>x ∈ W_e</math>, nebo jde o funkci, která není definovaná pro žádný vstup v případě, že <math>x \notin W_e</math>, platí tedy, že:

<math>x ∈ W_e ⇒ φ_e(x)↓ ⇒ (∀y)[φ_{e1} (e, x, y)↓] ⇒ φ_{f(e,x)}(f(e, x))↓ ⇒ f(e, x) ∈ K</math>

<math>x\notin W_e ⇒ φ_e(x)↑ ⇒ (∀y)[φ_{e1} (e, x, y)↑] ⇒ φ_{f(e,x)}(f(e, x))↑ ⇒ f(e, x) \notin K</math>

Dohromady dostaneme požadovanou ekvivalenci <math>x ∈ W_e ⇔ f(e, x) ∈ K</math>, a z toho plyne, že funkce <math>g(x)</math> definovaná jako <math>g(x) ≃ f(e, x)</math>, je prostá ORF, která převádí množinu <math>W_e</math> na <math>K</math>. Protože <math>W_e</math> byla libovolná množina, dostáváme, že <math>(∀e)[W_e ≤_1 K]</math>, a <math>K</math> je tedy <math>1</math>-úplná množina.

<math>K_0</math> je RSM (podle vlastností převoditelnosti). Ve větě nahoru jsme ukázali i to, že <math>K ≤_1 K_0</math> pomocí prosté ORF <math>h(x) = ⟨x, x⟩_2</math>. Těžkost množiny <math>K_0</math> tedy plyne z tranzitivity <math>1</math>-převoditelnosti.

Riceova v. - dk převoditelnost

Riceova věta - důkaz pomocí převoditelnosti. {{theorem

| <math>\cal C</math> třída ČRF, <math>A_\cal C = \{e | \varphi_e ∈ C\}</math> je RM ⇔ <math>\cal C = \emptyset</math> nebo <math>\cal C</math> obsahuje všechny ČRF | Rice

}}

💡  <math>A_\cal C</math> je mnozina indexu (Gödel.č.) funkci z třídy <math>\cal C</math>

Dk (pomocí převoditelnosti)

předpokládejme že <math>\cal C</math> NEní ∅ a <math>\cal C</math> NEobsahuje všechny ČRF

ukážeme sporem že <math>K ≤_1 A_\cal C</math>

<math>e_0</math> je GČ fce nedefinové pro žádný vstup a <math>φ_{e0} ∈ \overline{\cal C}</math>

<math>e_1</math> je GČ fce <math>φ_{e1}∈C</math> a <math>φ_{e0}≄ φ_{e1}</math>

<math>\varphi_{e_2}(x, y)\simeq\cases{ \varphi_{e_1}(y)&je-li $x\in K$\cr \uparrow }</math>

<math>φ_{e2}(x , y) ≃ φ_{s^1_1}(e, x) (y) ≃ φ_{f(x)}(y)</math>

<math>x∈K ⇒ φ_{f(x)}≃φ_{e1} ⇒ φ_{f(x)}(y) ∈ C ⇒ f(x) ∈ A_\cal C</math>

<math>x∉K ⇒ φ_{f(x)}≃φ_{e0} ⇒ φ_{f(x)}(y) ∉ C ⇒ f(x)∉ A_\cal C</math>

tedy <math>x ∈ K ⇔ f(x) ∈ Ac</math>

VoR a důsledky (🎓)

Věta o rekurzi a její jednoduché důsledky (ne Riceova věta) {{Zkazky|

  • Věty o rekurzi, došlo i na tu obligátní otázku, jestli počítá rychleji f(a) nebo a, od ní jsme se dostali až k Riceově větě a okrajově i k důkazu nerozhodnutelnosti halting problému

  • Věta o rekurzi a její aplikace. Zkoušejícího zajímalo znění, důkaz (preferoval ten přes s-m-n větu, ale spokojil se i s diagonalizačním), aplikace (Riceova věta a její znění, existence množin jako <math>Wx=\{x\}</math> s důkazem).

  • Věty o rekurzi, Riceova věta - Napsal jsem základní větu, generování pevných bod a větu o rekurzi v závislosti na parametrech (vše samozřejmě s těmi jednoduchými důkazy). Napsal jsem Riceovu větu a její důkaz plynoucí ze základní věty o rekurzi. Ptal se mě odkud plynou důkazy, odpovědel jsem, že z Kleeneho věty a s.m.n. Pak se ještě ptal na trochu jinou verzi "Věty o programu co vypíše sám sebe", tam jsem trochu tápal, ale intuitivně jsem věděl (tu větu jsem znal, bohužel jsem ji neuvedl).

}}

{{theorem | ∀ ORF <math>f</math> ∃ <math>n</math>: <math>φ_n ≃ φ_{f(n)}</math>

| VoR }}

💡 ∀ ORF transformacni funkci algoritmu f ∃ n tak že oba TS počítají stejnou fci (mají stejný algoritmus)

💡 n se říká pevný bod f

Dk (přes s-m-n větu)

Nechť <math>e_1</math> je číslem funkce, pro kterou platí <math>\varphi_{e_1}^{(2)}(e, x)\simeq\varphi_{f(\varphi_e(e))}(x),</math> tuto funkci bychom snadno odvodili pomocí univerzální ČRF.

Nechť <math>b</math> je Gödelovým číslem funkce <math>s_1^1(e_1, e)</math>, podle s-m-n věty tedy platí, že <math>\varphi_{\varphi_b(e)}(x)\simeq\varphi_{s_1^1(e_1, e)}(x)\simeq\varphi_{e_1}^{(2)}(e, x)\simeq\varphi_{f(\varphi_e(e))}(x).</math>

Protože <math>\varphi_b</math> je PRF (podle s-m-n), je <math>\varphi_b(b)\downarrow</math> a platí, že <math>\varphi_{\varphi_b(b)}\simeq\varphi_{f(\varphi_b(b))},</math> <math>\varphi_b(b)</math> je tedy hledaným pevným bodem <math>f</math>.

{{TODO|doplnit poznámky}}

Důsledky VoR

{{theorem | ∃ prostá PRF <math>g</math>, která ke GČ funkce <math>f</math> určí její pevný bod

| 💡 }}

{{theorem | ∀ ORF <math>f</math> má ∞ pevných bodů

| 💡 }}

{{theorem | ∃ <math>n ∈ N</math>, pro nějž:

  1. <math>W_n = \{n\}</math>

  2. <math>φ_n ≃ λx[n]</math>

| 💡 }}

Dk
  1. Nechť <math>e</math> je Gödelovo číslo funkce definované jako <math>φ_e^{(2)}(x, y) ≃ μz[x = y]</math> (💡 tedy <math>φ_e^{(2)}(x, y)↓</math> ⇔ <math>x = y</math>). Použijeme s-m-n větu a definujeme-li <math>f(x) ≃ s_1^1(e, x)</math>, dostaneme, že <math>φ_{f(x)} ≃ φ_{s-1-1(e,x)} ≃ φ_e(x, y)</math> a tedy <math>W_{f(x)} = \{x\}</math>. Funkce <math>f</math> je ORF (podle s-m-n), a tak podle VoR: <math>∃ n: φ_n ≃ φ_{f(n)}</math>, a tak <math>W_n = W_{f(n)} = \{n\}</math>.

  2. Podobně, nechť <math>e</math> je GČ funkce definované jako <math>φ_e^{(2)}(x, y) ≃ x</math>. Pomocí s-m-n věty definujeme-li <math>f(x) = s_1^1(e, x)</math>, dostaneme <math>φ_{f(x)}(y) ≃ x</math> a s použitím VoR nalezneme <math>n</math>, pro něž je <math>φ_n(y) ≃ φ_{f(n)}(y) ≃ n</math>.

{{theorem

| <math>f(x,y)</math> je ORF <math>⇒ ∃</math> prostá ORF <math>n(y)</math> taková, že <math>φ_{n(y)} ≃ φ_{f(n(y),y)} ∀y ∈ N</math> | VoR s parametry

}}

Riceova v. - dk s VoR (🎓)

{{theorem | <math>\cal C</math> třída ČRF, <math>A_\cal C = \{e | \varphi_e ∈ C\}</math> je RM ⇔ <math>\cal C = \emptyset</math> nebo <math>\cal C</math> obsahuje všechny ČRF

| Rice }}

Dk (sporem)

předpokládejme že <math>\cal C</math> NEní ∅ a <math>\cal C</math> NEobsahuje všechny ČRF

předpokládejme sporem že <math>A_\cal C</math> je rekurzivní

definujme si fci <math>f</math>:

<math>f(x) = a ~~ x∉ A_\cal C</math>

<math>f(x) = b ~~ x∈ A_\cal C</math>

<math>f</math> je ORF

<math>a∈A_\cal C</math>

<math>b∉ A_\cal C</math>

<math>n</math> je pevný bod <math>f</math> a <math>φ_n≃ φ_{f(n)}</math>

<math>φ_n∈\cal C ⇒ n ∈ A_\cal C ⇒ f(n)=b ⇒ f(n)∉ A_\cal C ⇒ φ_{f(n)} ∉ \cal C</math>

<math>φ_n∉\cal C ⇒ n ∈ A_\cal C ⇒ f(n)=a ⇒ f(n)∈ A_\cal C ⇒ φ_{f(n)}∈ \cal C</math>

spor

Složitost

(Complexity)

Def. základních tříd složitosti. Definice třídy NP pomocí cert. a NTS a jejich ekvivalence. ≤<sup>p</sup><sub>m</sub>, NPC a jejich vlastnosti (🎓)

Definice základních tříd složitosti. Definice třídy NP pomocí certifikátů a nedeterministických strojů a jejich ekvivalence. Polynomiální převoditelnost a úplnost a jejich vlastnosti

Definice základních tříd složitosti

typy problémů:

  • odpověď typu ano/ne - rozhodovací problém (jestli vstup patří do binární relace <math>L\subseteq\{0, 1\}^*</math>)

    • vstup - instance problému

  • úloha - pro daný vstup x nalézt y co splňuje požadovanou vlastnost (jestli oba patří do binární relace <math>R\subseteq\{0, 1\}^*\times\{0, 1\}^*</math>)

třídy jazyků a relací (tj. problémů a úloh)

💡 <math>f:\mathbf N\mapsto\mathbf N</math> libovolná fce

  • <math>DTIME(f(n))</math>, jazyk <math>L(M) ∈ DTIME(f(n)) ⇐</math> ∃ TS <math>M</math> co pracuje v čase <math>O(f(n))</math>.

  • <math>DSPACE(f(n))</math>, jazyk <math>L(M) ∈ DSPACE(f(n)) ⇐</math> ∃ TS <math>M</math> co pracuje v prostoru <math>O(f(n))</math>.

  • <math>DTIMEF(f(n))</math>, relace <math>R ∈ DTIMEF(f(n)) ⇐</math> ∃ TS <math>M</math> co pracuje v čase <math>O(f(n))</math>, <math>M(x)</math> přijme ⇔ ∃ slovo <math>y</math>: <math>(x, y)\in R</math> a na konci páska obsahuje <math>y</math>

    💡 Lze to také říci tak, že selektor pro predikát R je funkce spočitatelná v polynomiálním čase.

{{lemma|<math>DTIME(f(n)) ⊆ DSPACE(f(n))</math>}}

Definice třídy NP

Třídy polynomiálních jazyků, relací:

  • <math> P= \bigcup_{i\in \mathbb N}DTIME(n^i)</math> - problémy rozhodnutelné v polynomiálním čase

  • <math> PSPACE=\bigcup_{i\in\mathbb N}DSPACE(n^i)</math> - problémy rozhodnutelné v polynomiálním prostoru

  • <math> PF=\bigcup_{i\in\mathbb N}DTIMEF(n^i) </math> - úlohy řešitelné v polynomiálním čase

Třída polynomiálně ověřitelných úloh <math>NPF</math> (<math>NP</math> - nedeterministicky polynomiální, <math>F</math> - funkce, úlohy řešitelné nedeterministickým Turingovým strojem v polynomiálním čase)

  • Relace <math>R ∈ NPF</math> ⇐ ∃ polynom <math>p(n)</math>: že <math>∀ (x, y)\in R</math> je <math>|y|\leq p(|x|)</math> a ověření zda <math>(x, y)\in R</math> lze v polynomiálním čase.

Třída polynomiálně ověřitelných problémů <math>NP</math> (nedeterministicky polynomiální)

  • def. pomocí certifikátů: Jazyk <math>L ∈ \mathrm NP</math> ⇐ ∃ polynom <math>p</math> a jazyk <math>B\in P</math> a pokud <math>∀ x\in\{0, 1\}^*</math> platí: <math>x\in L\Leftrightarrow (\exists y)\;\Big[|y|\leq p(|x|)\mbox{ a }(x, y)\in B\Big].</math>

    💡 <math>L ∈ \mathrm NP</math> ⇐ ∃ polynomiální algoritmus (daný jazykem <math>B</math>), že polynomiálně dlouhý certifikát <math>y</math> dosvědčuje fakt <math>x\in L</math>. Je opět nutné uvažovat pouze polynomiálně dlouhé certifikáty, neboť složitost ověřování se měří vzhledem k délce <math>x</math> i certifikátu <math>y</math>.

    💡 obecně platí P ⊆ NP, protože pokud umíme problém řešit polyn. nepotřebujeme certifikát

  • def. pomocí NTS:

::💡 NTS <math>M=(Q, \Sigma, \delta, q_0, F)</math>, kde <math>\delta:Q\times\Sigma\mapsto\cal P(Q\times\Sigma\times\{R, N, L\})</math>.

třídy jazyků a relací (tj. problémů a úloh)

💡 <math>f:\mathbf N\mapsto\mathbf N</math> libovolná fce

<math>NTIME(f(n))</math>, jazyk <math>L(M) ∈ NTIME(f(n)) ⇐</math> ∃ NTS <math>M</math> co pracuje v čase <math>O(f(n))</math>.

<math>NSPACE(f(n))</math>, jazyk <math>L(M) ∈ NSPACE(f(n)) ⇐</math> ∃ NTS <math>M</math> co pracuje v prostoru <math>O(f(n))</math>.

{{theorem

| <math>NP=\bigcup_{i\in\mathbb N} NTIME(n^i)</math> | ekvivalence definic NP

}}

Dk (přes oba směry implikace)

→ : Předpokládejme nejprve, že L ∈ NP, to znamená, že ∃ polynom p a jazyk B ∈ P, pro které platí, že x ∈ L právě když existuje y, |y| ≤ p(|x|), pro které (x, y) ∈ B. NTS M’ , který bude přijímat L, bude pracovat ve dvou fázích. V první fázi zapíše na vstupní pásku za slovo x slovo y, tato fáze je nedeterministická a pro každé slovo y, takové že|y| ≤ p(|x|) existuje výpočet M’, který jej napíše. Na zápis y stačí čas p(|x|). Ve druhé fázi bude M’ simulovat práci TS M, který rozpoznává jazyk B, na vstupu (x, y), přičemž přijme, pokud (x, y) ∈ B. Zřejmě L = L(M) a M pracuje v polynomiálním čase.

← : Nyní předpokládejme, že L ∈ ∪i∈N NTIME(ni). To znamená, že x ∈ L právě když existuje polynomiálně dlouhý výpočet nedeterministického Turingova stroje M, kde L = L(M), jenž x přijme. V každém kroku tohoto výpočtu vybírá M z několika možných instrukcí, nechť řetězec y kóduje právě to, které instrukce byly v každém kroku vybrány. Řetězec y má délku nejvýš p(|x|) pro nějaký polynom p, protože M pracuje v polynomiálním čase a možností jak pokračovat z dané konfigurace podle přechodové funkce je jen konstantně mnoho. Simulací M s použitím instrukcí daných dle y můžeme deterministicky ověřit, zda y kóduje přijímající výpočet. Řetězec y tedy může sloužit jako polynomiálně dlouhý certifikát kladné odpovědi.

Polynomiální převoditelnost, úplnost a jejich vlastnosti.

{{multiple image |align = tright

|direction = horizontal

| image1 = Redukce.jpg | width1 = 331

| caption1 = Ilustrace polynomiálního převodu/redukce z jazyka <math>L_1</math> na jazyk <math>L_2</math> pomocí redukční fce <math>f</math>. Pro vstup <math>x∈\{0,1\}^*</math> má otázka zda <math>x∈L_1</math> stejnou odpověď jako otázka zda <math>x∈L_2</math>. 💡 myslím že je vidět proč se mu říká někdy redukce(<math>f</math> NENÍ prostá)

| image2 = Nphard.png | width2 = 223

| caption2 = <math>{NP}</math>-těžkost }}

<math>A\leq_m^pB</math> (jazyk <math>A</math> polynomiálně převoditelný/redukovatelný na <math>B</math>) pokud f: {0,1}*→{0, 1}* spočitatelná v polynomiálním čase a platí: <math>x ∈A ⇔f(x) ∈B</math>

vlastnosti:

  • <math>\leq_m^p</math> je reflexivní a tranzitivní.

    Dk: Reflexivita plyne z toho, že identita je funkce spočitatelná v polynomiálním čase. Tranzitivita plyne z toho, že složením dvou polynomů vznikne opět polynom, přesněji, je-li f funkce převádějící jazyk A na jazyk B, tedy A ≤mp B s použitím f, a g je funkce převádějící jazyk B na jazyk C, tedy B ≤mp C s použitím g, pak g ◦ f převádí A na C, jsou-li f i g spočitatelné v polynomiálním čase, lze totéž říci i o g ◦ f, tedy A ≤mp C s použitím g ◦ f.

  • <math>A\leq_m^pB</math> a <math>B\in P</math> ⇒ <math>A\in P</math>

    Dk: Je-li B ∈ P, pak existuje Turingův stroj M, který přijímá B v polynomiálním čase. Je-li f funkce, která převádí A na B, a je-li f spočitatelná v polynomiálním čase, pak TS M’, který pro vstup x spočítá f(x) a poté pustí M k rozhodnutí, zda f(x) ∈ B, přijímá A v polynomiálním čase.

  • <math>A\leq_m^pB</math> a <math>B\in NP</math> ⇒ <math>A\in NP</math>

    Dk: Platí z téhož důvodu jako { 2. }, protože tytéž argumenty lze použít i pro NTS.

Jazyk <math>A \in \mathbf{NP}</math>-hard (NP-těžký) ⇐ ∀ jazyk <math>B\in NP</math>: <math>B\leq_m^pA</math>.

Jazyk <math>A \in \mathbf{NPC}</math> (NP-Complete, NP-úplný) ⇐ <math>A \in NP</math> a <math>A \in NP</math>-hard.

💡 problem je T-uplny, pokud patri do T a je T-silny, tedy kazdy problem v T se da na problem prevest v poly case

{{theorem

| A, B ∈ NP, <math>A\leq_m^pB</math> je NP-úplný ⇒ B je NP-úplný |

}}

Dk

Tvrzení plyne přímo z tranzitivity relace <math>≤_m^p</math> zaručené vlastnostami polynomiální převoditelnosti a definice NP-úplného problému.

Definice (existence certifikátu – CERT, rozhodovací problém):

  • Instance : Řetězec w kódující DTS M, řetězec x a řetězec 1ᵗ pro nějaké t ∈ N.

  • Otázka : Existuje řetězec y s |y|t, pro který platí, že M(x, y) přijme v t krocích?

{{theorem

| Problém CERT je NP-úplný. | NP-úplnost CERT

}}

Savičova věta.

Cook-Levin - KACHL ∈ NPC (🎓)

NP-úplnost SAT (z KACHL)

NP-úplnost 3-SAT (z SAT)

NP-úplnost VP (z 3-SAT)

NP-úplnost 3DM (z SAT)

LOUP ∈ NPC (z 3DM)

Pseudopolyn. alg., číselné probl. a silná NPC. Př. pseudopolyn. alg. Batoh (🎓)

Příklad pseudopolynomiálního algoritmu pro Batoh

Aproximační algoritmy - definice a příklad (🎓)

Příklad aproximačního algoritmu pro Bin Packing

Aproximační schémata, př. pro Batoh (🎓)

Příklad aproximačního schématu pro Batoh - BAPX

coNP, #P - def. a vlastnosti

coNP

#P

Metody tvorby algoritmů: rozděl a panuj, dynamické programování, hladový algoritmus (<strike>zkoušková</strike>, 🎓)

Metody tvorby algoritmů: rozděl a panuj, dynamické programování

Hladový algoritmus

Amortizovaná složitost

Průnik se státnicovými otázkami

Ostatní