Státnice - Algoritmicky vyčíslitelné funkce, rekurzivní a rekurzivně spočetné množiny

Ze zápisků k zkoušce z ZSV , maly uvod pokud jste toho uz hodne zapomneli: pohadky vycislitelnost

09/10, 14/15: Algoritmicky vycíslitelné funkce, jejich vlastnosti, ekvivalence jejich ruzných matematických definic. Cástecne rekurzivní funkce. Rekurzivní a rekurzivne spocetné množiny a jejich vlastnosti.

Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Částečně rekurzivní funkce. (4×🎓)

Zážitky ze zkoušek

Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Částečně rekurzivní funkce (2013, Loebl) - 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. ČRF (2010, 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í. CRF(2010, Fiala) - napsal sem v lidske reci vsechny zakladni funkce a operatory, co je odvozeni, popsal co je PRF, ORF, CRF a napsal inkluze a dokazal pres Ackermana inkluzi mezi PRF a ORF...dotaz znel na mnoziny, tak sem otocil co je rekurzivni a rekurzivne spocetna...celkem v Pohode zkouska, zkousel Fiala znamka 1-2 RM a RSM a súvislosť s ČRF (2010) - stihol som to tesne pred obedom, zadefinoval som operácie, ČRF, spomenul PRF<ORF<ČRF (+ackermanku, "nekončiacu fciu"), RM/RSM, RP/RSP, že sa črf dajú očíslovať (+kleeneho veta), čo je W_e, K, napísal dôkaz že "K je RS, not R; neg(K) nie je RS".. v tú chvíľu ma skúšajúci zastavil, takže sme sa vlastne k RSM množinám už ani nedostali :) mal som tam ešte niečo o selektore, 1-prevoditelnosti/úplnosti, postovu vetu, úsekové fcie... každopádne myslím že človek si tu s pochopením základov vystačí a kým nie je na teoretickej informatike, tak fakt netreba zo seba ťahať podrobné dôkazy napr. Kleeneho vety... :) ČRF (2010, Holan) - K splneniu stačila napísať detfinícia, operátory, funkcie. Ukázať neostré inklúzie medzi ČRF, ORF, PRF. Vysvetliť prečo sa zavádza abstrakcia ČRF, ďalej som spomenul ekvalenciu TS - ČRF, ostatné RAM, Post, ... len ústne. Prešli sme prípravu na papieri, asi jediná otázka bola na Godelovo číslo v dôkaze o uni. funkcii pre PRF a Holan povedal, že mu to stačí.

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

PRF, ČRF, RP, RSP a vlast.

💡 Behold - Ultimate Table of Life, the Universe, and Everything!

fce			predikát			množina			problém
odvozeny pomocí		vlastnosti	∃ pro něj (odp.)char.fce		vlastnosti	je def.oborem (odp.)fce je (odp.)unárním predikátem		vlastnosti
PRF	Základní fce: nulová funkce o(x) = 0 následník s(x) = x + 1 projekce Iₙʲ (x₁,..,xⱼ,..,xₙ) = xⱼ Operátory: substituce Sₙᵐ(f,g₁,..,gₘ) = h kde: h(x⃗ ) ≃ f(g₁(x⃗ ),..., gₘ(x⃗ )) x⃗ = x₁,..,xₙ primitivní rekurze(~for) Rₙ(f,g) = h kde: h(i, x⃗ ) ≃ g(i - 1, h(i - 1, x⃗ ), x⃗ ) h(0, x⃗ ) ≃ f( x⃗ )	Uzavřenost: konečný +,× PRF je PRF (podmíněný příkaz) ∀x je splněn !1 PRP1..n: PRF(x)=PRF1..n(x)⇔PRP1..n(x) (~if/switch) (omezená minimalizace) PRF(x,z)=μy<z[PRP(x,y)]	PRP	χP(x⃗ ) ≃ 1 pro R(x⃗ ) jinak ≃0	Uzavřenost: (konečná) ∧,∨,¬ PRP je PRP omezená kvantifikace PRP je PRP	nezavádí se
ORF	ČRF def.∀vstupy (totální)		ORP	χP(x⃗ ) ≃ 1 pro R(x⃗ ) jinak ≃0 (jako PRP)		RM	χA(x)↓= 1 pro x∈A jinak χA(x)↓= 0	Uzavřenost: RM jsou uzavřené na ∪, ∩ a doplněk (Postova) A je RM ⇔ A i doplněk A jsou RSM Generování RM: RM = rng nějaké rost. úsekové ČRF	rozhodnutelný (decidable)
ČRF	Nový operátor: minimalizace(~while) Mₙ(f) = h kde: h( x⃗ )↓≃min{y|f(x⃗ , y)↓=0 a ∀z<y: f(x⃗ ,z)↓ ≠ 0 }	f je ČRF ⇔ je turingovsky vyčíslitelná (Kleene) ∀ČRFₑ(x⃗ ) jde zjednodušit na PRF(while(y) PRP(e, x⃗ , y)) (UČRF) ∃ČRFz(e, x⃗ ) = ČRFₑ(x⃗ ) (snm) ∃prostá PRF tž.: ČRFPRF(x,y⃗ ) = λz⃗ [ČRFₓ(y⃗ ,z⃗ )] (VoR)∀ORF f ∃n: ČRFn≃ČRFf(n) ☀ ∃n∈N: Wn={n} ☀ ∃n∈N: φn≃λx[n] (Rice) C triviální třída ČRF ⇔ mnž jejich GČ AC je RM	RSP	Částečná char.fce: χR(x⃗ )↓ pro R(x⃗ ) jinak χR(x⃗ )↑	Uzavřenost: RSP uzavřeny na ∃	RSM	χA(x)↓ pro x∈A jinak χA(x)↑	Uzavřenost: RSM jsou uzavřené na ∪, ∩ ale NE na doplněk Generování RSM: RSM = ∅ nebo rng nějaké ORF RSM = rng nějaké (rostoucí) ČRF Převoditelnost: A ≤ₘ B pokud ∃ ORF f, tž: ∀ x: x ∈ A ⇔ f(x) ∈ B A ≤₁ B je-li f navíc prostá m-úplná pokud je RSM a ∀jiná RSM je na ni m-převoditelná (to samé pro 1-převoditelnost)	částečně rozhodnutelný (recognizable)

celá ZOO

PRF⊂ORF⊂ČRF

minimalizace $ M_n(f) = h $

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 $ ↓= $ (zkratka za konverguje a rovná se) bychom v definici klidně mohli psát jen $ = $. Použití $ ↓≠ $ (zkratka za konverguje a nerovná se) je ale důležité, například pokud $ f(x_1,...,x_n,0)↑ $, tak $ h(x_1,...,x_n) $ také není definováno, i kdyby třeba $ f(x_1,...,x_n,1)=0 $.

podmíněná rovnost f(x₁, .., xₙ) ≃ g(x₁, .., xₙ) znamená: hodnota f(x₁, .., xₙ) je definována ⇔ definována i hodnota g(x₁, .., xₙ), a pak jsou si také rovny

Základní funkce:

• nulová (konstantní) funkce o(x) = 0
• následník s(x) = x + 1
• projekce Iₙʲ (x₁, .., xⱼ, .. , xₙ) = xⱼ (💡 vrací hodnotu j-tého parametru)

Operátory: ( x = (x₁, .., xₙ) )

• substituce Sₙᵐ(f, g₁,..., gₘ) = h kde: h(x₁, .., xₙ) ≃ f(g₁(x₁, .., xₙ),..., gₘ(x₁, .., xₙ))
  • 💡 f má m proměnných a g₁, .. , gₘ n 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 Rₙ(f, g) = h
  • kde: h(0, x₂, ..., xₙ) ≃ f(x₂, ..., xₙ)

    h(i + 1, x₂, ..., xₙ) ≃ g(i, h(i , x₂, ..., xₙ), x₂, ..., xₙ)

  • 💡 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á x₁ nebo i má zvláštní význam — slouží jako čítač
• minimalizace Mₙ(f) = h (má sílu while-cyklu)

h(x₁, .., xₙ)↓ ≃ min { y | f(x₁, .., xₙ, y)↓ = 0 a ∀z < y :  f(x₁, .., xₙ, z)↓ ≠ 0 }

• μ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 ⇐ ∃ pro něj PRF charakteristická funkce
  • predikát R(x₁, .., xₙ) je relace nebo libovolný fakt o n proměnných
    • charakteristická fce predikátu R je χ_P(x₁, .., xₙ) ≃ 1 pro R(x₁, .., xₙ) jinak ≃0
      • 💡 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í)
  • ORP ⇐ ∃ pro něj ORF charakteristická funkce

• RSP ⇐ ∃ pro něj ČRF charakteristická funkce
  • částečná char. fce (=ČRF) predikátu R je funkce f_R: ℕⁿ → ℕ : f_R(x₁, ... , xₙ)↓ ⇔ R(x₁, ... , xₙ), ∀(x₁, ... , xₙ) ∈ ℕ.
  • 💡 je def.oborem nějaké ČRF

Jejich základní vlastnosti

• (uzavřenost na aritm.operace: konečný + a ×) f je PRF 2 proměnných ⇒ je PRF i:
  • g(z, x) = ∑_y<z f (y, x) ( přičemž g(0, x) = 0 )
  • h(z, x) = ∏_y<z f (y, x) ( přičemž h(0, x) = 1 )
    • 💡 analogicky i pro PRF 1 proměnné (tj. vyhodíme všude x)
• (podmíněný příkaz) - analogie switch/case/if-then
  • g₁,..., gₙ , jsou PRF a R₁(x), ..., Rₙ(x) jsou PRP a ∀x ∈ ℕ je splněn !1 z nich.
  • ⇒ tato fce f je PRF: $ \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} $

• kvantifikátory (omezené i neomezené).
  • (omezená kvantifikace) $ P $ binární PRP ⇒ $ V_P(z, x)=(\forall y<z)[P(y, x)] $ a $ E_P(z, x)=(\exists y<z)[P(y, x)] $ 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)

  $ P $ a $ R $ unární PRP ⇒ $ R\wedge P $, $ R\vee P $ a $ \neg P $ jsou PRP

  • (konečná konjunkce a disjunkce)

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

• (omezená minimalizace)

  $ P $ binární PRP ⇒ tato $ f $ je PRF:

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

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

Ekvivalence jejich definic (ČRF ⇔ TS)

Věta ( ČRF ⇒ TS ):  $ h $ je ČRF $ n $ proměnných ⇒ $ h $ je Turingovsky vyčíslitelná

Dk (konstrukcí TS, zde komplet včetně nižší úrovně)

:💡 Věta přesněji: existuje Turingův stroj $ M_h $ takový, že pro každou $ n $-tici přirozených čísel $ x_1, x_2, \dots, x_n $ platí $ M_h((x_1)_B\#(x_2)_B\#\dots\# (x_n)_B)\downarrow\Leftrightarrow h(x_1, x_2, \dots, x_n)\downarrow $ a platí-li $ h(x_1, x_2, \dots, x_n)\downarrow=y $, potom výpočet Turingova stroje $ M_h $ vydá na výstupu řetězec $ (y)_B $. definujeme TS pro základní funkce a operátory pro odvození $ h $: 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ů) Věta ( 💡 ):  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 $ h $, spočítá Gödelovo číslo $ e $ stroje $ M_e $, který počítá funkci $ h $.

Věta ( TS ⇒ ČRF ):  funkce $ f $ turingovsky vyčíslitelná ⇒ je $ f $ Č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 $ M_e $ 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 Tato část je neúplná a potřebuje rozšířit. 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 ($ \mu y[T(e, x, y)] $) pomocí fce $ \cal U $ z ní vytáhnu g.číslo poslední konfigurace tedy $ f(x)=\cal U(\mu y[T(e, x, y)]) $ 💡 U je zřejmě PRF

Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti. (4×🎓)

Zážitky ze zkoušek

RM, RSM a jejich vlastnosti (2013, Kučera) – 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. CRF + RM + RSM (2011, Majerech) - 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- RS a RSM mnoziny, prevoditelnosti (2011, Kryl) - 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. Rekurzivne funkcie a rekurzivne spocetne mnoziny (2010, Mlcek?) - (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.

charakteristická funkce χ_A(x) -- charakteristická fce predikátu náležení do množiny ( χ_A(x)↓= 1 pro x ∈ A a jinak χ_A(x)↓= 0 )

$ χ_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}\,\! $

💡 částečná charakteristická funkce množiny -- χ_A(x)↓= 1 pro x ∈ A a jinak χ_A(x)↑

dom značí definiční obor, rng obor hodnot

RM A ⊆ ℕ ⇐ je-li charakteristická funkce χ_A(x) ORF

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

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 $ \mathbf{W_e} = dom~ φ_e = \{ x | φ_e(x)↓ \} $

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

$ \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} $

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

Věta ( RM - uzavřenost na ∪, ∩ a doplňek ):  RM jsou uzavřeny na sjednocení, průnik a operaci doplňku

Dk:
předpokládáme, že signum, součet, součin a opatrné odčítání 1 (predecessor) jsou PRF/ORF : $ A∪B=\{x|[χ_a(x)∨χ_b(x)]\} $ $ A∩B=\{x|[sign(χ_a(x)+χ_b(x))]\} $ $ \overline A=\{x|[1\dot{-}χ_a(x)]\} $ 💡 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).

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

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 $ f(x, y) = s_1^2(e, x, y) $. Podobně můžeme postupovat i v případě průniku a funkce g, stačilo by místo disjunkce použít konjunkci.

Postova věta v kontextu množin
Věta ( Postova věta v kontextu množin ):  $ A $ je RM $ \Leftrightarrow A $ i $ \overline A={\mathbb N}\setminus A $ jsou RSM 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]

predikáty RSP,...

Lemma :  Predikát $ H $ definovaný jako $ H (e, s, x_1, . . , x_n) ⇔ φ_{e,s}(n)(x_1, . . , x_n)↓ $ je PRP a platí, že: $ φ_e(n) (x_1, . . . , x_n)↓⇔ (∃s)[ φ_{e,s}(n) (x_1, . . , x_n)↓] $ . (v dk předpokladáme, že $ T_n $ z Kleenovy věty je PRP a omezená kvantifikace je PR.) Kódování uspořádaných dvojic, n-tic: $ ⟨x, y⟩_2 $ je kód uspořádané dvojice [x, y] daný: $ ⟨x, y⟩_2 = (x + y).(x + y + 1) / 2 + x $ $ ⟨x_1, . ., x_n⟩_n $ je kód uspořádané n-tice daný: $ ⟨x_1, . . ., x_n⟩_n = ⟨x_1, ⟨x_2, . . ., x_n⟩_{n-1}⟩_2 $ $ π_{n,i}(⟨x_1, . ., x_n⟩_n) = x_i $ je inverze pro výběr $ i $-tého prvku ze zakódované $ n $-tice Lemma – Pro každé $ n ≥ 2, i ≤ n $ jsou funkce $ ⟨x_1, . . . , x_n⟩_n $ a $ π_n $ PRF, a $ ⟨x_1, . . . , x_n⟩_n $ je bijekcí mezi $ N^{n+1} $ a $ N $ ( důkaz pro πn předpokládá, že omezená minimalizace a kvantifikace jsou PRF ). Věta ( důsledek Kleeneho věty ):  Predikát $ R ⊆ N^n $ je RSP ⇔ ∃ PRP $ P ⊆ N^{n+1} $ , že: $ R(x_1, . . , x_n) ⇔ (∃y)[P (x_1, . . , x_n, y)] $. Věta ( RSP jsou uzavřeny na ∃ kvantifikátor ):  $ P(x_1, \dots, x_n, y) $ je RSP ⇒ $ R(x_1, \dots, x_n)=(\exists y)\;[P(x_1, \dots, x_n, y)] $ je RSP Dk Protože $ P(x, y) $ je RSP, můžeme jej zapsat podle důsledku Kleeneho jako $ P(x, y) = (∃z) [Q(x, y, z)] $, kde $ Q $ je PRP. Z toho plyne, že $ R(x) = (∃y)(∃z) [Q(x, y, z)]= (∃⟨y, z⟩_2) [Q(x, y, z)] $. Označíme-li si $ D(x, u) = Q(x, π_{2,1}(u), π_{2,2}(u)) $, pak $ D $ je PRP, pro který platí, že $ R(x) = (∃u) D(x, u) $. ⇒ podle důsledku Kleeneho: $ R(x) $ je RSP. Věta ( výběrová funkce ):  $ R(x, y) $ je RSP ⇒ $ \exists $ ČRF $ f $ (také výběrová funkce nebo selektor pro $ R $), že $ f(x)\downarrow\Leftrightarrow(\exists y)R(x, y) $ a pokud $ f(x)\downarrow $, pak $ R(x, f(x)) $. 💡 $ \exists f $ implementující $ \exists y $ na predikátu $ R(x, y) $ Dk Podle důsledku Kleeneho můžeme $ R $ zapsat jako $ R(x, y) = (∃z)[Q(x, y, z)] $ pro nějaký PRP $ Q $. A tedy $ (∃y)R(x, y) ⇔ (∃y)(∃z)Q(x, y, z) $. Protože predikát $ Q $ je PRP(totální), dostaneme, že funkce $ g(x) ≃ μ⟨y, z⟩_2 Q(x, y, z) $. Nyní z nalezené hodnoty stačí vybrat $ y $, tedy 1. prvek, celkově tedy definujeme funkci $ f $ jako $ f(x) ≃ π_{2,1}(g(x)) $.

další zdroje
Státnice_-_Rekurzivní_a_rekurzivně_spočetné_množiny

RM = rng rost. úsekové ČRF

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

Věta ( $ RM = rng $ rostoucí úsekové ČRF ):  A je RM $ \Leftrightarrow $ je oborem hodnot nějaké rostoucí úsekové ČRF

Dk (oběma směry - neformálně, zde formálnější přepis ze skript)

$ \Rightarrow\,\! $: Předpokládejme nejprve, že $ A $ je RM. Zkonstruujeme rostoucí, úsekovou ČRF $ f(i) $ = "vrať $ i $-tý nejmenší prvek z $ A $". Začneme $ f(0) \simeq \mu x(x\in A)\,\! $. Dále $ f(n+1) \simeq \mu x(x > f(n) \wedge x \in A)\,\! $ $ \Leftarrow\,\! $: Nyní předpokládejme, že $ A = rng f $, kde $ f\,\! $ je rostoucí úsekovou ČRF. Pokud $ f $ není ORF, znamená to že $ f\,\! $ má konečné $ dom\,\! $ (z def. úsekové fce), a tedy je konečná i samotná množina $ A $ a je tedy triviálně rekurzivní. Pokud je $ f $ ORF je všude definovaná (totální): $ y \in A=rng f \Leftrightarrow \exists x:f(x)=y \Leftrightarrow \exists x\!\leq\!y: f(x)=y $. Poslední ekvivalence platí, protože $ f\,\! $ je rostoucí a úseková. Tedy $ y \in A \Leftrightarrow y \in \{f(0),\ldots,f(y)\}. $

💡 Důsledek: Nechť $ A $ je ∞ množina: $ A $ je $ RM ⇔ A=rng $ 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

Zážitky ze zkoušek
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

Věta ( Generování RSM ):  Následující tvrzení jsou ekvivalentní:

1. A je RSM.
2. A je ∅, nebo je $ rng $ nějaké ORF
3. A je $ rng $ nějaké ČRF.
4. A je $ rng $ nějaké rostoucí ČRF.

Dk (neformální, zde komplet)

postup v dukazu $ 1. ⇒ 2. $ (konstrukce ORF co pro jakékoli vstupy vrací prvky z A): $ 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} $. Každý prvek $ W_e $ je tedy funkcí $ g $ pro nějaký vstup $ y $ vrácen, jenom nedokážeme odhadnout, pro jak velké $ y $. Dohromady dostáváme, že $ A = W_e = rng~ g $. $ 2. ⇒ 3. $ : Plyne z toho, že každá ORF je i ČRF. ∅ je oborem hodnot ČRF, která není definovaná pro žádný vstup. $ 3. ⇒ 1. $ (pomocí částečné aproximace vyrobíme z ČRF RSP => RSM): Předpokládejme, že $ A $ je oborem hodnot ČRF $ g ≃ φ_e $. Uvědomme si, že rozhodnutí, zda $ g(y)↓= x $ je RSP (plyne například z toho, že $ φ_{e,s}(y)↓ = x $ je PRP a tedy $ g(y)↓ = x ⇔ (∃s)[φe,s(y)↓= x] $ je RSP, dále je tedy i $ (∃y)[g(y)↓ = x] $ RSP, a tedy množina $ A = \{x | (∃y)[g(y)↓ = x]\} $ je RSM. Ze znalosti GČ $ e $ funkce $ g $ bychom opět s pomocí s-m-n věty mohli spočítat GČ funkce, jejíž doménou množina $ A $ je. Pro úplnost totiž můžeme past $ A = dom~ λx [ μ⟨y, s⟩_2[φ_{e,s}(y)↓= x] ] $. $ 1. ⇒ 4. $ (zkonstruujeme triviální rostoucí ČRF $ h(x)=g(e,x) $ u které se $ dom $=$ rng $) : Předpokládejme, že $ A = W_e $, tedy $ A = dom φ_e $. Buď $ g(e, x) $ fce definovaná jako: $ g(e, x) = \begin{cases}x \quad & x ∈ W_e \\ ↑ \quad & \mbox{ jinak }\end{cases} $. Funkce $ g(e, x) $ je zřejmě ČRF, například proto, že ji lze zapsat jako $ g(e, x) = o(φ_e(x)) + x $ (tj. do nulové funkce vložíme $ φ_e(x) $ jako argument, hodnota tedy na hodnote $ φ_e(x) $ nezávisí, definovatelnost ano). Položme nyní $ h(x) = g(e, x) $, potom je $ A $ jak oborem hodnot, tak definičním oborem funkce $ h $, funkce $ h $ je rostoucí ČRF, jejíž GČ lze opět efektivně spočítat z $ e $. $ 4. ⇒ 3. $ : Toto je zřejmé. Implikaci $ (3. ⇒ 1.) $ už máme hotovou. Tato část je neúplná a potřebuje rozšířit. {{{1}}} 1=>3 Pro každou množinu $ W_x $ vytvoříme množinu dvojic $ R=\{\langle y,y\rangle:y \in W_x\}\,\! $. Množina $ R\,\! $ je rekurzivně spočetná, tedy má ČRF selektor $ \varphi\,\! $, :platí $ dom(\varphi)=rng(\varphi)=W_x\,\! $. Myšlenka toho důkazu je, že body, kde $ \varphi_x\,\! $ konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude zárověň jeho oborem hodnot. 1<=3 Máme ČRF $ g\,\! $ a její obor hodnot. Zkonstruujeme pseudoinverzní funkci $ h\,\! $ k ČRF $ g\,\! $, tj. funkci takovou, že $ dom(h)=rng(g)\,\! $ a to tak, že vyrobíme RS :predikát $ Q(x,y)\Leftrightarrow g(x)\simeq y\,\! $ a to má ČRF selektor, který hledáme -- $ h\,\! $.

≤₁, ≤_m, K a K₀ 1-úplné, RSM a ¬RM.

A ≤ₘ B (množina A je m-převoditelná na B) pokud ∃ ORF f, tž: ∀ x: x ∈ A ⇔ f(x) ∈ B

A ≤₁ B (množina A je 1-převoditelná na B) je-li f navíc prostá

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

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

vlastnosti ≤₁, ≤_m

• $ A\leq_m B $ a $ B $ RM $ \Rightarrow A $ RM

💡 $ A\leq_m B $ a $ A $ není RM $ \Rightarrow B $ není RM (protože: $ (A\Rightarrow B)=(\neg B\Rightarrow \neg A) $)

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

• $ A\leq_m B $ a $ B $ RSM $ \Rightarrow A $ RSM

💡 $ A\leq_m B $ a $ A $ není RSM $ \Rightarrow B $ není RSM

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

• $ \leq_m $ a $ \leq_1 $ (relace) jsou reflexivní a tranzitivní

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

• $ A $ $ m $-úplná & $ B $ RSM & $ A\leq_m B \Rightarrow B $ je $ m $-úplná

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

Dk: Toto plyne okamžitě z tranzitivity $ ≤_m $, $ ≤_1 $ a definice úplnosti.

• $ A\leq_mB \Rightarrow \overline A\leq_m\overline B $

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

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

Problém zastavení K₀ a jeho diagonála K

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

$ K =\{x\;|\;\varphi_x(x)\downarrow\}=\{x\;|\;x\in W_x\} $ - diagonála $ K_0 $

💡 $ K_1 =\{x\;|\;W_x\neq\emptyset\} $

Věta ( $ K $, $ K_0 $ RSM $ \neg $RM ):  $ K $ a $ K_0 $ jsou RSM, ale nejsou RM

Dk (sporem jako u TS)

: Z definice jsou obě RSM. Nechť $ φ_z $ označuje univerzální ČRF. $ K = dom λx[φ_z(x, x)] $. Pro spor $ K $ je RM ⇒ $ \overline K $ je RSM. Nechť $ φ_e $ je ČRF, pro níž $ \overline K = dom φ_e $ a ptejme se, zda $ e ∈ \overline K $ nebo ne: Z def. $ K $ ⇒ $ e ∈ \overline K ⇔ φ_e(e)↑ $ $ \overline K = dom φ_e $ ⇒ $ e ∈ \overline K ⇔ φ_e(e)↓ $ ⇒ $ φ_e(e)↓ ⇔ φ_e(e)↑ $ ⇒ SPOR ⇒ $ K $ tedy není RM. $ K_0 = dom λ⟨x, y⟩_2[φ_z(x, y)] $. Pro spor $ K_0 $ je RM a $ χ_{K0} $ je její char. ORF: Definujeme $ χ_{K}(x) = χ_{K_0}(⟨x, x⟩_2) $ ⇒ $ χ_K $ char. ORF $ K $ ⇒ SPOR s tím že $ K $ není RM. ⇒ $ K_0 $ tedy není RM.

Věta ( 1-úplnost $ K $, $ K_0 $ ):  Množiny $ K $ a $ K_0 $ jsou 1-úplné.

Dk:

: $ K $ je $ 1 $-úplná: $ K $ je RSM, stačí tedy ukázat, že libovolnou RSM lze na $ K $ převést prostou ORF. Definujme funkci $ φ_{e1}(e, x, y) ≃ φ_e(x) $. Podle s-m-n věty $ φ_{s^2_1(e1,e,x)} (y) ≃ φ_e (e, x, y) ≃ φ_e(x) $. Definujme tedy funkci $ f(e, x) = s_1^2(e_1, e, x) $. Protože $ s_1^2 $ je prostá PRF, je i $ f $ prostá PRF. Navíc platí, že $ φ_{f(e,x)} $ je buď všude definovaná konstantní funkce, pokud $ x ∈ W_e $, nebo jde o funkci, která není definovaná pro žádný vstup v případě, že $ x \notin W_e $, platí tedy, že: $ x ∈ W_e ⇒ φ_e(x)↓ ⇒ (∀y)[φ_{e1} (e, x, y)↓] ⇒ φ_{f(e,x)}(f(e, x))↓ ⇒ f(e, x) ∈ K $ $ x\notin W_e ⇒ φ_e(x)↑ ⇒ (∀y)[φ_{e1} (e, x, y)↑] ⇒ φ_{f(e,x)}(f(e, x))↑ ⇒ f(e, x) \notin K $ Dohromady dostaneme požadovanou ekvivalenci $ x ∈ W_e ⇔ f(e, x) ∈ K $, a z toho plyne, že funkce $ g(x) $ definovaná jako $ g(x) ≃ f(e, x) $, je prostá ORF, která převádí množinu $ W_e $ na $ K $. Protože $ W_e $ byla libovolná množina, dostáváme, že $ (∀e)[W_e ≤_1 K] $, a $ K $ je tedy $ 1 $-úplná množina. $ K_0 $ je RSM (podle vlastností převoditelnosti). Ve větě nahoru jsme ukázali i to, že $ K ≤_1 K_0 $ pomocí prosté ORF $ h(x) = ⟨x, x⟩_2 $. Těžkost množiny $ K_0 $ tedy plyne z tranzitivity $ 1 $-převoditelnosti.

Státnice -- Softwarové systémy
Složitost a vyčíslitelnost -- Tvorba algoritmů (10🎓), NP-úplnost (15🎓), Aproximační algoritmy (6🎓), Vyčíslitelné funkce a rekurzivní množiny (8🎓), Nerozhodnutelné problémy (9🎓), Věty o rekurzi (6🎓)
Datové struktury -- Stromy (32🎓), Hašování (13🎓), Třídění (10🎓)
Databázové systémy -- Formální základy: Relace (12🎓), Datalog (9🎓), Ostatní (0🎓)   Modely a jazyky: SQL (7🎓), DIS (7🎓), Odborné (3)   Implementace: Transakce (5🎓), Indexace (10🎓), Komprese (3)
Softwarové inženýrství -- Programovací jazyky a překladače, Objektově orientované a komponentové systémy, Analýza a návrh softwarových systémů
Systémové architektury -- Operační systémy, Distribuované systémy, Architektura počítačů a sítí
Počítačová grafika -- Geometrické modelování a výpočetní geometrie, Analýza a zpracování obrazu, počítačové vidění a robotika, 2D počítačová grafika, komprese obrazu a videa, Realistická syntéza obrazu, virtuální realita

🎓 - znamená kolikrát byla otázka u státnic