=Algoritmicky vycíslitelné funkce, jejich vlastnosti, ekvivalence jejich ruzných matematických definic. Cástecne 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čí.
}}
== PRF, ČRF, RP, RSP a vlast. (🎓)==
[[Image:ZSV 1.jpg|right|thumb|460px|'''PRF⊂ORF⊂ČRF''']]
{| class="wikitable" border="1"
! !! funkce !! predikát !! množina !! problém
|-
|částečně rekurzivní /<br> rekurzivně spočetný || ČRF || RSP || RSM || částečně rozhodnutelný
|-
|obecně rekurzivní || ORF || ORP || rekurzivní množina || rozhodnutelný
|-
|primitivně rekurzivní || PRF || PRP || nezavádí se || nezavádí se
|}
'''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>.
{{Statnice I2}}
