{{Sources|
''Ze zápisků k zkoušce z [[Řešené_otázky_NTIN090|ZSV]]
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čí.
}}
== 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 '''''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 ''- 2, ..., ''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''₁ 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 <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í)
** '''ORP '''⇐ ∃ pro něj ORF charakteristická funkce
* '''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>
{{collapse|vlastnosti predikátů|2=
* 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, [[Řešené_otázky_NTIN090/ČRF2TS| zde komplet včetně nižší úrovně]])|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), <u>tedy program = minimalizace čehosi, kde to cosi už je PR</u>)|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 <math>χ_A(x)</math>''' -- charakteristická fce predikátu náležení do množiny (<math>χ_A(x) = \downarrow 1</math> pro <math>x\in A</math> a <math>χ_A(x) \downarrow = 0</math> pro <math>x\notin A</math>)
<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''' -- <math>χ_A(x) = \downarrow 1</math> pro <math> x \in A</math> a <math>χ_A(x)\uparrow</math> pro <math>x \notin A</math>
<math> dom\,\!</math> značí '''definiční obor''', <math> rng\,\!</math> '''obor hodnot'''
'''RM''' A ⊆ ℕ ⇐ je-li def. oborem ORF
: 💡 také nazýváme jako unární RP (příklad: binarni predikat je mnozina dvojic, ale unarni predikat je mnozina prvku)
: 💡 tj.: char.fce <math>χ_A(x)</math> je ORF
'''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 průnik.
| RSM - uzavřenost na ∪, ∩ ale <u>NE na doplňek</u>
}}
{{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 <u>∃ kvantifikátor</u>
}}
;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|
* [[Státnice_-_Rekurzivní_a_rekurzivně_spočetné_množiny]]
}}
== 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ě, [[Řešené_otázky_NTIN090/RM_CRF | zde formálnější přepis ze skript]])|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.
# 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í.
# 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í:
# A je RSM.
# A je ∅, nebo je <math>rng</math> nějaké ORF
# A je <math>rng</math> nějaké ČRF.
# A je <math>rng</math> nějaké rostoucí ČRF.
| Generování RSM
}}
{{collapse|1=Dk (neformální, [[Řešené_otázky_NTIN090/GenRSM|zde komplet]])|2=
[[Image:genRSM.jpg|right|thumb|250px|postup v dukazu]]
<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.==
''1-převoditelnost, m-převoditelnost a jejich vlastnosti, 1-úplnost množin K a K0. Množiny K a K0 jsou rekurzivně spočetné, ale nejsou rekurzivní.''
<math>A\leq_m B</math> (množina <math>A</math> je '''<math>m</math>-převoditelná''' na <math>B</math>) pokud ∃ ORF <math>f</math>, tž: <math>∀ x: x ∈ A ⇔ f(x) ∈ B</math>
<math>A\leq_1 B</math> (množina <math>A</math> je '''<math>1</math>-převoditelná''' na <math>B</math>) je-li <math>f</math> navíc prostá
množina <math>A</math> je '''<math>m</math>-úplná''' (resp. '''<math>1</math>-úplná''') pro třídu RSM pokud: je <math>A</math> RSM a ∀ jiná RSM je na ni <math>m</math>-převoditelná (resp. <math>1</math>-převoditelná).
: 💡 budeme říkat pouze <math>A</math> je ''<math>m</math>-úplná'' nebo ''<math>1</math>-úplná'', dodatek „pro třídu RSM“ budeme vynechávat, protože jinými než RM a RSM se nebudeme zabývat.
{{collapse|1=vlastnosti ≤<sub>1</sub>, ≤<sub>m</sub>|2=
* <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}}
