{{Sources| Ze zápisků k zkoušce z <Řešené_otázky_NTIN090> , 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 PRP_1..n: : **PRF(x)=**PRF_1..n(x)⇔PRP_1..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) ∃ČRF_z(e, x⃗ ) = ČRFₑ(x⃗ )

• (s_n^m) ∃prostá PRF tž.: ČRF_{PRF(x,''y''⃗ )} = λz⃗ [ČRFₓ(y⃗ ,z⃗ )]

• **(VoR)**∀ORF f ∃n: ČRF_n≃ČRF_f(n) : ☀ ∃n∈N: W_n={n} : ☀ ∃n∈N: φ_n≃λx[n]

• **(Rice) *C triviální třída ČRF ⇔ : mnž jejich GČ A_C je RM jinak χ_R(x⃗ )↑ Uzavřenost:

• RSP uzavřeny na ∃

• RSM jsou uzavřené na ∪, ∩ ale <u>NE na doplněk</u> 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 $\downarrow =$ (zkratka za konverguje a rovná se) bychom v definici klidně mohli psát jen $=$. Použití $\downarrow \ne$

:: (zkratka za konverguje a nerovná se) je ale důležité, například pokud $f(x_1,...,x_n,0)\uparrow$, tak $h(x_1,...,x_n)$ také není definováno, :: i kdyby třeba $f(x_1,...,x_n,1)=0$.

| minimalizace $M_n(f)=h$ }}

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) = ∑

•   * 
    :: 
    * 
    :: 
  

•   :: 
    :: 
    :: 
  

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

::

::

::

::

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

::

::

•   :: 
    :: 
  

•   :: 
    :: 
  

•   :: 
  

•   :: 
    :: 
  

•   :: 
    :: 
  

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

:: ::

:: :: :: :: :: :: :: ::

:: :: :: :: :: ::