{{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''⃗&nbsp;) = λz⃗ [ČRFₓ(y⃗ ,z⃗ )] * (VoR)∀ORF f ∃n: ČRFn≃ČRFf(n) : ☀ ∃nN: Wn={n} : ☀ ∃nN: φ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ₙ))

    • 💡 fm proměnných a g₁, .. , gn 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