{{Sources| Ze zápisků k zkoušce z , 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×🎓)
{{Zkazky|
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<em> </em>of Life, the Universe, and Everything!
* 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⃗ ) | * 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)] | * (konečná) ∧,∨,¬ PRP je PRP * omezená kvantifikace PRP je PRP | |||||||
jinak ≃0 (jako PRP) | 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 | (decidable) | |||||||
* 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
jinak χR(x⃗ )↑ |
Uzavřenost:
* RSP uzavřeny na ∃ |
* 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) |
(recognizable) | |
{{image|image=Chpvenndiagram.jpg|width=346|caption=celá ZOO}}
{{image|image=ZSV 1.jpg|width=460|caption=PRF⊂ORF⊂ČRF}} {{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> }}
podmíněná rovnost f(x₁, .., xₙ) ≃ g(x₁, .., xₙ)<math></math> 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 fR: ℕⁿ → ℕ : fR(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) = ∑
Ekvivalence jejich definic (ČRF ⇔ TS)
Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti. (4×🎓)
RM = ''rng'' rost. úsekové ČRF
RSM = ''rng'' ORF, či ČRF
≤<sub>1</sub>, ≤<sub>m</sub>, ''K'' a ''K<sub>0</sub>'' 1-úplné, RSM a ¬RM.
Problém zastavení K<sub>0</sub> a jeho diagonála K