{{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) = ∑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: <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>.

Ekvivalence jejich definic (ČRF ⇔ TS)

{{theorem | <math>h</math> je ČRF <math>n</math> proměnných ⇒ <math>h</math> je Turingovsky vyčíslitelná

| ČRF ⇒ TS }}

{{collapse|Dk (konstrukcí TS, )|2= :💡 Věta přesněji: existuje Turingův stroj <math>M_h</math> takový, že pro každou <math>n</math>-tici přirozených čísel <math>x_1, x_2, \dots, x_n</math> platí

<math>M_h((x_1)_B\#(x_2)_B\#\dots\# (x_n)_B)\downarrow\Leftrightarrow h(x_1, x_2, \dots, x_n)\downarrow</math>

a platí-li <math>h(x_1, x_2, \dots, x_n)\downarrow=y</math>, potom výpočet Turingova stroje <math>M_h</math> vydá na výstupu řetězec <math>(y)_B</math>.

definujeme TS pro základní funkce a operátory pro odvození <math>h</math>:

  • 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ů)

{{theorem

| 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 <math>h</math>, spočítá Gödelovo číslo <math>e</math> stroje <math>M_e</math>, který počítá funkci <math>h</math>. | 💡

}}

}} {{theorem

| funkce <math>f</math> turingovsky vyčíslitelná ⇒ je <math>f</math> ČRF | TS ⇒ ČRF

}} {{collapse|1=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)|2=

  • předpoklady: f je def. jako tur. vyčíslitelná ⇒ ∃ TS <math>M_e</math> 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

{{TODO|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 (<math>\mu y[T(e, x, y)]</math>)

  • pomocí fce <math>\cal U</math> z ní vytáhnu g.číslo poslední konfigurace

  • tedy <math>f(x)=\cal U(\mu y[T(e, x, y)])</math>

💡 U je zřejmě PRF

}}

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

{{Zkazky|

  • 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 xA a jinak χA(x)↓= 0 )

<math>χ_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}\,\!</math> ::💡 částečná charakteristická funkce množiny -- χA(x)↓= 1 pro xA 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 <math>\mathbf{W_e} = dom~ φ_e = \{ x | φ_e(x)↓ \}</math>

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

::<math>\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}</math>

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

{{theorem

| RM jsou uzavřeny na sjednocení, průnik a operaci doplňku | RM - uzavřenost na ∪, ∩ a doplňek

}} {{collapse|1=Dk:|2=

předpokládáme, že signum, součet, součin a opatrné odčítání 1 (predecessor) jsou PRF/ORF :

<math>A∪B=\{x|[χ_a(x)∨χ_b(x)]\}</math>

<math>A∩B=\{x|[sign(χ_a(x)+χ_b(x))]\}</math>

<math>\overline A=\{x|[1\dot{-}χ_a(x)]\}</math>

💡 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).

}} {{theorem

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

}} {{collapse|1=Dk:|2=

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

}} {{collapse|1=Postova věta v kontextu množin|2=

{{theorem | <math>A</math> je RM <math>\Leftrightarrow A</math> i <math>\overline A={\mathbb N}\setminus A</math> jsou RSM

| Postova věta v kontextu množin }}

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]

}} {{collapse|1= predikáty RSP,...|2=

{{lemma | Predikát <math>H</math> definovaný jako <math>H (e, s, x_1, . . , x_n) ⇔ φ_{e,s}(n)(x_1, . . , x_n)↓</math> je PRP a platí, že: <math>φ_e(n) (x_1, . . . , x_n)↓⇔ (∃s)[ φ_{e,s}(n) (x_1, . . , x_n)↓]</math> . (v dk předpokladáme, že <math>T_n</math> z Kleenovy věty je PRP a omezená kvantifikace je PR.)

}}

Kódování uspořádaných dvojic, n-tic:

  • <math>⟨x, y⟩_2</math> je kód uspořádané dvojice [x, y] daný: <math>⟨x, y⟩_2 = (x + y).(x + y + 1) / 2 + x</math>

  • <math>⟨x_1, . ., x_n⟩_n</math> je kód uspořádané n-tice daný: <math>⟨x_1, . . ., x_n⟩_n = ⟨x_1, ⟨x_2, . . ., x_n⟩_{n-1}⟩_2</math>

  • <math>π_{n,i}(⟨x_1, . ., x_n⟩_n) = x_i</math> je inverze pro výběr <math>i</math>-tého prvku ze zakódované <math>n</math>-tice

  • Lemma – Pro každé <math>n ≥ 2, i ≤ n</math> jsou funkce <math>⟨x_1, . . . , x_n⟩_n</math> a <math>π_n</math> PRF, a <math>⟨x_1, . . . , x_n⟩_n</math> je bijekcí mezi <math>N^{n+1}</math> a <math>N</math> ( důkaz pro πn předpokládá, že omezená minimalizace a kvantifikace jsou PRF ).

{{theorem

| Predikát <math>R ⊆ N^n</math> je RSP ⇔ ∃ PRP <math>P ⊆ N^{n+1}</math> , že: <math>R(x_1, . . , x_n) ⇔ (∃y)[P (x_1, . . , x_n, y)]</math>. | důsledek Kleeneho věty

}} {{theorem

| <math>P(x_1, \dots, x_n, y)</math> je RSP ⇒ <math>R(x_1, \dots, x_n)=(\exists y)\;[P(x_1, \dots, x_n, y)]</math> je RSP | RSP jsou uzavřeny na ∃ kvantifikátor

}}

Dk

Protože <math>P(x, y)</math> je RSP, můžeme jej zapsat podle důsledku Kleeneho jako <math>P(x, y) = (∃z) [Q(x, y, z)]</math>, kde <math>Q</math> je PRP. Z toho plyne, že <math>R(x) = (∃y)(∃z) [Q(x, y, z)]= (∃⟨y, z⟩_2) [Q(x, y, z)]</math>.

Označíme-li si <math>D(x, u) = Q(x, π_{2,1}(u), π_{2,2}(u))</math>, pak <math>D</math> je PRP, pro který platí, že <math>R(x) = (∃u) D(x, u)</math>.

⇒ podle důsledku Kleeneho: <math>R(x)</math> je RSP.

{{theorem

| <math>R(x, y)</math> je RSP ⇒ <math>\exists</math> ČRF <math>f</math> (také výběrová funkce nebo selektor pro <math>R</math>), že <math>f(x)\downarrow\Leftrightarrow(\exists y)R(x, y)</math> a pokud <math>f(x)\downarrow</math>, pak <math>R(x, f(x))</math>. | výběrová funkce

}} 💡 <math>\exists f</math> implementující <math>\exists y </math> na predikátu <math>R(x, y)</math>

Dk

Podle důsledku Kleeneho můžeme <math>R</math> zapsat jako <math>R(x, y) = (∃z)[Q(x, y, z)]</math> pro nějaký PRP <math>Q</math>. A tedy <math>(∃y)R(x, y) ⇔ (∃y)(∃z)Q(x, y, z)</math>. Protože predikát <math>Q</math> je PRP(totální), dostaneme, že funkce <math>g(x) ≃ μ⟨y, z⟩_2 Q(x, y, z)</math>.

Nyní z nalezené hodnoty stačí vybrat <math>y</math>, tedy 1. prvek, celkově tedy definujeme funkci <math>f</math> jako <math>f(x) ≃ π_{2,1}(g(x))</math>.

}} {{zdroje|

}}

RM = ''rng'' rost. úsekové ČRF

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

{{theorem

| A je RM <math>\Leftrightarrow</math> je oborem hodnot nějaké rostoucí úsekové ČRF | <math>RM = rng</math> rostoucí úsekové ČRF

}} {{collapse|1=Dk (oběma směry - neformálně, )|2=

<math> \Rightarrow\,\!</math>: Předpokládejme nejprve, že <math>A</math> je RM. Zkonstruujeme rostoucí, úsekovou ČRF <math> f(i)</math> = "vrať <math>i</math>-tý nejmenší prvek z <math>A</math>".

  • Začneme <math> f(0) \simeq \mu x(x\in A)\,\!</math>.

  • Dále <math> f(n+1) \simeq \mu x(x > f(n) \wedge x \in A)\,\!</math>

<math> \Leftarrow\,\!</math>: Nyní předpokládejme, že <math>A = rng f</math>, kde <math> f\,\!</math> je rostoucí úsekovou ČRF.

  1. Pokud <math>f</math> není ORF, znamená to že <math> f\,\!</math> má konečné <math> dom\,\!</math> (z def. úsekové fce), a tedy je konečná i samotná množina <math>A</math> a je tedy triviálně rekurzivní.

  2. Pokud je <math>f</math> ORF je všude definovaná (totální): <math> y \in A=rng f \Leftrightarrow \exists x:f(x)=y \Leftrightarrow \exists x\!\leq\!y: f(x)=y </math>. Poslední ekvivalence platí, protože <math> f\,\!</math> je rostoucí a úseková. Tedy <math> y \in A \Leftrightarrow y \in \{f(0),\ldots,f(y)\}. </math>

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

{{Zkazky|

  • 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

}}

{{theorem | Následující tvrzení jsou ekvivalentní:

  1. A je RSM.

  2. A je ∅, nebo je <math>rng</math> nějaké ORF

  3. A je <math>rng</math> nějaké ČRF.

  4. A je <math>rng</math> nějaké rostoucí ČRF.

| Generování RSM }}

{{collapse|1=Dk (neformální, )|2=

<math>1. ⇒ 2.</math> (konstrukce ORF co pro jakékoli vstupy vrací prvky z A):

<math>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} </math>.

Každý prvek <math>W_e</math> je tedy funkcí <math>g</math> pro nějaký vstup <math>y</math> vrácen, jenom nedokážeme odhadnout, pro jak velké <math>y</math>. Dohromady dostáváme, že <math>A = W_e = rng~ g</math>.

<math>2. ⇒ 3.</math> : Plyne z toho, že každá ORF je i ČRF. ∅ je oborem hodnot ČRF, která není definovaná pro žádný vstup.

<math>3. ⇒ 1.</math> (pomocí částečné aproximace vyrobíme z ČRF RSP => RSM): Předpokládejme, že <math>A</math> je oborem hodnot ČRF <math>g ≃ φ_e</math>.

Uvědomme si, že rozhodnutí, zda <math>g(y)↓= x</math> je RSP (plyne například z toho, že <math>φ_{e,s}(y)↓ = x</math> je PRP a tedy <math>g(y)↓ = x ⇔ (∃s)[φe,s(y)↓= x]</math> je RSP, dále je tedy i <math>(∃y)[g(y)↓ = x]</math> RSP, a tedy množina <math>A = \{x | (∃y)[g(y)↓ = x]\}</math> je RSM. Ze znalosti GČ <math>e</math> funkce <math>g</math> bychom opět s pomocí s-m-n věty mohli spočítat GČ funkce, jejíž doménou množina <math>A</math> je. Pro úplnost totiž můžeme past <math>A = dom~ λx [ μ⟨y, s⟩_2[φ_{e,s}(y)↓= x] ]</math>.

<math>1. ⇒ 4.</math> (zkonstruujeme triviální rostoucí ČRF <math>h(x)=g(e,x)</math> u které se <math>dom</math>=<math>rng</math>) : Předpokládejme, že <math>A = W_e</math>, tedy <math>A = dom φ_e</math>. Buď <math>g(e, x)</math> fce definovaná jako:

<math>g(e, x) = \begin{cases}x \quad & x ∈ W_e \\ ↑ \quad & \mbox{ jinak }\end{cases}</math>.

Funkce <math>g(e, x)</math> je zřejmě ČRF, například proto, že ji lze zapsat jako <math>g(e, x) = o(φ_e(x)) + x</math> (tj. do nulové funkce vložíme <math>φ_e(x)</math> jako argument, hodnota tedy na hodnote <math>φ_e(x)</math> nezávisí, definovatelnost ano). Položme nyní <math>h(x) = g(e, x)</math>, potom je <math>A</math> jak oborem hodnot, tak definičním oborem funkce <math>h</math>, funkce <math>h</math> je rostoucí ČRF, jejíž GČ lze opět efektivně spočítat z <math>e</math>.

<math>4. ⇒ 3.</math> : Toto je zřejmé. Implikaci <math>(3. ⇒ 1.)</math> už máme hotovou.

{{TODO}} 1=>3

:Pro každou množinu <math>W_x</math> vytvoříme množinu dvojic <math> R=\{\langle y,y\rangle:y \in W_x\}\,\!</math>. Množina <math> R\,\!</math> je rekurzivně spočetná, tedy má ČRF selektor <math> \varphi\,\!</math>, :platí <math> dom(\varphi)=rng(\varphi)=W_x\,\!</math>. :Myšlenka toho důkazu je, že body, kde <math> \varphi_x\,\!</math> konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude zárověň jeho oborem hodnot.

1<=3

:Máme ČRF <math> g\,\!</math> a její obor hodnot. Zkonstruujeme pseudoinverzní funkci <math> h\,\!</math> k ČRF <math> g\,\!</math>, tj. funkci takovou, že <math> dom(h)=rng(g)\,\!</math> a to tak, že vyrobíme RS :predikát <math> Q(x,y)\Leftrightarrow g(x)\simeq y\,\!</math> a to má ČRF selektor, který hledáme -- <math> h\,\!</math>. }}

≤<sub>1</sub>, ≤<sub>m</sub>, ''K'' a ''K<sub>0</sub>'' 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 ≤1, ≤m
  • <math>A\leq_m B</math> a <math>B</math> RM <math>\Rightarrow A</math> RM

    💡 <math>A\leq_m B</math> a <math>A</math> není RM <math>\Rightarrow B</math> není RM (protože: <math>(A\Rightarrow B)=(\neg B\Rightarrow \neg A)</math>)

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

  • <math>A\leq_m B</math> a <math>B</math> RSM <math>\Rightarrow A</math> RSM

    💡 <math>A\leq_m B</math> a <math>A</math> není RSM <math>\Rightarrow B</math> není RSM

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

  • <math>\leq_m</math> a <math>\leq_1</math> (relace) jsou reflexivní a tranzitivní

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

  • <math>A</math> <math>m</math>-úplná & <math>B</math> RSM & <math>A\leq_m B \Rightarrow B</math> je <math>m</math>-úplná

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

    Dk: Toto plyne okamžitě z tranzitivity <math>≤_m</math>, <math>≤_1</math> a definice úplnosti.

  • <math>A\leq_mB \Rightarrow \overline A\leq_m\overline B</math>

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

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

Problém zastavení K<sub>0</sub> a jeho diagonála K

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

<math>K =\{x\;|\;\varphi_x(x)\downarrow\}=\{x\;|\;x\in W_x\}</math> - diagonála <math>K_0</math>

💡 <math>K_1 =\{x\;|\;W_x\neq\emptyset\} </math>

{{theorem | <math>K</math> a <math>K_0</math> jsou RSM, ale nejsou RM

| <math>K</math>, <math>K_0</math> RSM <math>\neg</math>RM }}

{{collapse|1=Dk (sporem jako u TS)|2=

Z definice jsou obě RSM. Nechť <math>φ_z</math> označuje univerzální ČRF.

<math>K = dom λx[φ_z(x, x)]</math>. Pro spor <math>K</math> je RM ⇒ <math>\overline K</math> je RSM.

Nechť <math>φ_e</math> je ČRF, pro níž <math>\overline K = dom φ_e</math> a ptejme se, zda <math>e ∈ \overline K</math> nebo ne:

Z def. <math>K</math> ⇒ <math>e ∈ \overline K ⇔ φ_e(e)↑</math>

<math>\overline K = dom φ_e</math> ⇒ <math>e ∈ \overline K ⇔ φ_e(e)↓</math>

⇒ <math>φ_e(e)↓ ⇔ φ_e(e)↑</math> ⇒ SPOR ⇒ <math>K</math> tedy není RM.

<math>K_0 = dom λ⟨x, y⟩_2[φ_z(x, y)]</math>. Pro spor <math>K_0</math> je RM a <math>χ_{K0}</math> je její char. ORF:

Definujeme <math>χ_{K}(x) = χ_{K_0}(⟨x, x⟩_2)</math> ⇒ <math>χ_K</math> char. ORF <math>K</math> ⇒ SPOR s tím že <math>K</math> není RM. ⇒ <math>K_0</math> tedy není RM.

}} {{theorem

| Množiny <math>K</math> a <math>K_0</math> jsou 1-úplné. | 1-úplnost <math>K</math>, <math>K_0</math>

}}

{{collapse|1=Dk:|2=

<math>K</math> je <math>1</math>-úplná: <math>K</math> je RSM, stačí tedy ukázat, že libovolnou RSM lze na <math>K</math> převést prostou ORF.

Definujme funkci <math>φ_{e1}(e, x, y) ≃ φ_e(x)</math>. Podle s-m-n věty <math>φ_{s^2_1(e1,e,x)} (y) ≃ φ_e (e, x, y) ≃ φ_e(x)</math>. Definujme tedy funkci <math>f(e, x) = s_1^2(e_1, e, x)</math>. Protože <math>s_1^2</math> je prostá PRF, je i <math>f</math> prostá PRF. Navíc platí, že <math>φ_{f(e,x)}</math> je buď všude definovaná konstantní funkce, pokud <math>x ∈ W_e</math>, nebo jde o funkci, která není definovaná pro žádný vstup v případě, že <math>x \notin W_e</math>, platí tedy, že:

<math>x ∈ W_e ⇒ φ_e(x)↓ ⇒ (∀y)[φ_{e1} (e, x, y)↓] ⇒ φ_{f(e,x)}(f(e, x))↓ ⇒ f(e, x) ∈ K</math>

<math>x\notin W_e ⇒ φ_e(x)↑ ⇒ (∀y)[φ_{e1} (e, x, y)↑] ⇒ φ_{f(e,x)}(f(e, x))↑ ⇒ f(e, x) \notin K</math>

Dohromady dostaneme požadovanou ekvivalenci <math>x ∈ W_e ⇔ f(e, x) ∈ K</math>, a z toho plyne, že funkce <math>g(x)</math> definovaná jako <math>g(x) ≃ f(e, x)</math>, je prostá ORF, která převádí množinu <math>W_e</math> na <math>K</math>. Protože <math>W_e</math> byla libovolná množina, dostáváme, že <math>(∀e)[W_e ≤_1 K]</math>, a <math>K</math> je tedy <math>1</math>-úplná množina.

<math>K_0</math> je RSM (podle vlastností převoditelnosti). Ve větě nahoru jsme ukázali i to, že <math>K ≤_1 K_0</math> pomocí prosté ORF <math>h(x) = ⟨x, x⟩_2</math>. Těžkost množiny <math>K_0</math> tedy plyne z tranzitivity <math>1</math>-převoditelnosti.

}}

{{Statnice_I2}}