{{TOC float}}

{{Sources| Tohle je poněkud obšírnější výcuc ke z pro obory a , pocházející ze Strojilových skript, papírových zápisků A. Kazdy a zápisků z předmětu Vyčíslitelnost I ze -- 14:01, 17 Aug 2010 (CEST)

}}

Částečně rekurzivní funkce

v 30. letech vynalezl primitivní rekurzivní funkce, později společně s dalšími částečně rekurzivní funkce. Jde o funkcionální přístup k algoritmům. Lze se na ně dívat i jako na logiku 1. řádu: základní funkce jsou axiomy, máme operátory -- odvozovací pravidla -- a z toho vyrábíme formule -- rekurzivní funkce.

Definice (Podmíněná rovnost, konvergence, divergence)

  • <math> \simeq\,\!</math> značí "podmíněnou rovnost", tj. v případě, že alespoň jedna strana má smysl, tak má smysl i druhá a rovnají se.

  • <math> P_1(D)\!\!\downarrow\,\!</math> značí, že predikát je definován, tj "konverguje" (občas se značí <math> !\,\!</math> místo <math> \downarrow\,\!</math>)

  • <math> P_1(D)\!\!\uparrow\,\!</math> značí, že predikát není definován, tj. "diverguje"

Značky konvergence, divergence i podmíněné rovnosti se vztahují jak na predikáty, tak na funkce.

Definice (Základní funkce)

  • <math> o(x)\simeq 0\quad \forall x\in\mathbb{N}\,\!</math> ("nula")

  • <math> s(x)\simeq x + 1\quad \forall x\in\mathbb{N}\,\!</math> ("následník")

  • <math> I_n^j(x_1,\dots,x_n) = x_j\quad 1\leq j\leq n\,\!</math> ("projekce", vybrání jedne ze složek)

Definice (Základní operátory)

  • <math> R_n\quad (n\geq 1)\,\!</math> -- primitivní rekurze
    Funkcím <math> f\,\!</math> (<math> n-1\,\!</math> proměnných) a <math> g\,\!</math> (<math> n+1\,\!</math> proměnných) přiřadí <math> R_n(f,g)=h\,\!</math>, kde <math> h(0,x_2,\dots,x_n)\simeq f(x_2,\dots,x_n)\,\!</math> a <math> h(y+1,x_2,\dots,x_n)\simeq g(y,h(y,x_2,\dots,x_n),x_2,\dots,x_n)\,\!</math> (analogické k for-cyklu).

  • <math> S^m_n\,\!</math> -- substituce
    Funkci <math> f\,\!</math> (<math> m\,\!</math> proměnných) a <math> m\,\!</math> funkcím <math> g_i\,\!</math> (všechny <math> n\,\!</math> proměnných) přiřadí funkci <math> h\,\!</math> (<math> n\,\!</math> proměnných) předpisem <math> h=S_n^m(f,g_1,\dots,g_n) \equiv h(x_1,\dots,x_n)\simeq f(g_1(x_1,\dots,x_n),\dots,g_m(x_1,\dots,x_n))\,\!</math> (analogické k podprogramu).

  • <math> M_n\,\!</math> -- minimalizace
    Funkci <math> f\,\!</math> (<math> n+1\,\!</math> proměnných) přiřadí <math> h\,\!</math> (<math> n\,\!</math> proměnných) tak, že <center><math>h(x_1,\dots,x_n)\!\!\downarrow \wedge h(x_1,\dots,x_n)\simeq y \equiv f(x_1,\dots,x_n,y)\!\!\downarrow, \simeq 0 \wedge f(x_1,\dots,x_n, j)\!\!\downarrow, \not\simeq 0\ \forall j<y\,\!</math></center> (analogické k while-cyklu).

Další značení:

  • <math>\mu_y P(x, y)</math> je funkce proměnné <math>x</math>, která vrátí nejmenší <math>y</math> takové, aby platil predikát <math>P(x, y)</math>. Lze jí sestrojit pomocí operátoru minimalizace.

Definice (Třída primitivně a částečně rekurzivních funkcí)

  • Třída primitivně rekurzivních funkcí je nejmenší třída funkcí <math> f:\mathbb{N}^k\to\mathbb{N}\,\!</math>, která obsahuje základní funkce a je uzavřená na <math> R_n\,\!</math> a <math> S_n^m\,\!</math>.

  • Třída částečně rekurzivních funkcí je nejmenší třída, která obsahuje zákl. funkce a je uzavřená na <math> R_n\,\!</math>, <math> S_n^m\,\!</math> a <math> M_n\,\!</math>.

Poznámka (Vlastnosti zákl. funkcí a operátorů)

  • Všechny zákl. funkce jsou všude definované ("totální") a efektivně vyčíslitelné.

  • Všechny zákl. operátory zachovávají efektivní vyčíslitelnost.

  • <math> R_n\,\!</math>, <math> S_n^m\,\!</math> zachovávají totálnost.

  • PRF jsou efektivně vyčíslitelné a totální.

Definice (Odvození funkce)

Odvození funkce je konečná posloupnost funkcí, z nichž každá je buď funkce základní, nebo vzniká z už odvozených funkcí pomocí nějakého operátoru. Ke každé funkci si pamatujeme, jak vznikla (toto v praxi hraje roli programu).

Definice (Obecně rekurzivní funkce)

Funkce je obecně rekurzivní (ORF), jestliže je ČRF a totální.

Operace s PRF, predikáty

Poznámka (Některé PRF)

Pomocí PRF lze popsat např.:

  • součet

  • součin

  • mocninu, faktoriál

  • operaci <math> x\dot{-} y\,\!</math>, kde <math> x\dot{-} y = x-y\,\!</math> pro <math> x\geq y\,\!</math>, jinak <math> 0\,\!</math>

  • operátory <math> \mathrm{sg}\,\!</math> a <math> \overline{\mathrm{sg}}\,\!</math> (testy na nenulovost, resp. nulovost argumentu)

  • minimum, maximum, absolutní hodnotu rozdílu

Definice (Charakteristická funkce)

Mějme predikát <math> P\,\!</math> o <math> n\,\!</math> proměnných. Potom <math> c_P\,\!</math> je jeho charakteristická funkce, když je to všude definovaná funkce daná následovně:

:<math>c_P(x_1,\dots,x_n)\simeq \begin{cases}1 \quad & \mbox{ pokud } P(x_1,\dots,x_n) \\ 0 \quad & \mbox{ jinak }\end{cases}\,\!</math>

Charakteristická funkce množiny označuje charakteristickou funkci predikátu náležení do množiny.

Částečná charakteristická funkce pro nějaký predikát <math> P\,\!</math> o <math> n\,\!</math> proměnných je funkce <math> f\,\!</math> o <math> n\,\!</math> proměnných taková, že <math> \downarrow f(x_1,\dots,x_n)\Leftrightarrow P(x_1,\dots,x_n)\,\!</math> a <math> \downarrow f(x_1,\dots,x_n)\Rightarrow f(x_1,\dots,x_n) = 1\,\!</math>. Podobně se definuje částečná charakteristická funkce množiny.

Definice (PR, OR, RS Predikáty)

Řekneme, že predikát je primitivně (obecně) rekurzivní, jestliže jeho charakteristická funkce je primitivně (obecně) rekurzivní. Predikát je rekurzivně spočetný, jestliže jeho částečná charakteristická funkce je částečně rekurzivní.

S funkcemi a predikáty se operuje docela nedůsledně, dají se v podstatě ztotožnit.

Definice (Rekurzivní a rekurzivně spočetná množina)

Množina <math> M\,\!</math> je rekurzivní, je-li její charakteristická funkce obecně rekurzivní (každá char. fce je totální, takže ČRF by bylo totéž). Množina <math> M\,\!</math> je rekurzivně spočetná, jestliže je definičním oborem nějaké ČRF (neboli jestliže je její částečná char. funkce částečně rekurzivní).

Množina je rekurzivní, jestliže existuje program, který se na libovolném vstupu zastaví a rozhodne, zda do ní vstup patří. Množina je rekurzivně spočetná, jestliže existuje program, který se zastaví právě na jejích prvcích. Je-li množina rekurzivní, je i rekurzivně spočetná, opačně to neplatí.

Poznámka (Jiná možnost nahlížení)

Pro ČRF by taky šlo použít něco jako logiku 1. řádu:

  • termy číselné: <math> 0,x,x+1,\dots\,\!</math>

  • termy funkční: <math> o,I_1^1,s,R_2(I_1^1,S_3^1(s,I_3^2)),\dots\,\!</math>

  • pravidlo aplikace: <math> Ap(f,x)=\dots=f(x)\,\!</math> (kde "<math> \dots\,\!</math>" je proces vyhodnocení termu, potenciálně nekonečný)

  • pravidlo zobecnění: <math> \lambda{xy} (x+y)\,\!</math> dává z číselného termu <math> x+y\,\!</math> funkci

Poznámka (Operace zachovávající PR)

PR jsou:

  • Rozšíření počtu proměnných, konstantní funkce

  • Permutace a ztotožnění proměnných

  • Kódování <math> \mathbb{N}^k\,\!</math> do <math> \mathbb{N}\,\!</math> -- iterace Cantorova diagonálního kódování dvojic (<math> \langle x,y\rangle_2 = \frac{(x+y)(x+y+1)}{2}+x\,\!</math>)

  • Opačná operace -- dekódování

  • Funkce <math> p(i)\,\!</math> -- <math> i\,\!</math>-té prvočíslo

  • Predikát rovnosti a <math> <\,\!</math>, <math> >\,\!</math>

  • Logické spojky <math> \vee, \wedge, \neg\,\!</math>, omezené kvantifikátory (kvantifikace spočetně mnoha prvků)

  • Gödelovo prvočíselné kódování: slovo <math> a_{i_0}\dots a_{i_k}\,\!</math> do <math> p(0)^{i_0}\cdot\dots\cdot p(k)^{i_k}\,\!</math>

Ackermannova funkce

Definice (Ackermannova funkce)

Ackermannova funkce je funkce definovaná jako:

:<math>A(0,x) = \begin{cases} 1 \quad & x = 0 \\ 2 \quad & x = 1 \\ x + 2 \quad & x > 1 \end{cases}</math>

:<math>A(y,0) = 1\,\!</math> :<math>A(y+1,x+1) = A(y, A(y+1,x) )\,\!</math>

Definice (Strukturální složitost)

Definujeme strukturální složitost -- hloubku rekurze (intuitivně: počet vnořených for-cyklů) jako <math> 0\,\!</math> pro základní funkce a

:<math>h(R_n(P,Q)) = \max(h(P), h(Q)+1)\,\!</math>

Pak <math> \mathcal{R}_i\,\!</math> je třída PRF, které lze získat pomocí PR-termů hloubky <math> \leq i\,\!</math> a PRF samo je <math> \cup_{i=1}^{\infty}\mathcal{R}_i\,\!</math>

Věta (O Ackermannově funkci)

Ackermannova funkce není PRF, ale je ORF.

Důkaz

  • Určitě je ORF -- důkaz se provádí transfinitní indukcí typu <math> \omega^2\,\!</math>; pro výpočet každé hodnoty potřebuji jen konečně mnoho předchozích hodnot -- stačí mi <math> \mu_z\,\!</math>, kde <math> z\,\!</math> je nejmenší kus <math> \mathbb{N}^2\,\!</math>, který stačí k výpočtu <math> A(y,x)\,\!</math> (dá práci dokázat, že je konečný, potřeba ordinálů, lexikografického uspořádání).

  • Dokážeme, že <math> A\,\!</math> roste rychleji než každá PRF: <math> \forall\varphi\,\!</math> PRF (jedné proměnné) <math> \exists x_0: \forall x\geq x_0: \varphi(x)<A(x,x)\,\!</math>.

  • Uvažujme <math> A(y,x)\,\!</math> jako matici funkcí <math> f_y(x)\,\!</math>. Potom určitě <math> f_i \in \mathcal{R}_i\backslash \mathcal{R}_{i-1}\,\!</math> a <math> f_y(x)\,\!</math> je (až na konečně mnoho <math> x\,\!</math>) rostoucí. Navíc pro libovolnou <math> \varphi\in\mathcal{R}_i\,\!</math> existuje <math> x_0\,\!</math> takové, že <math> \forall x\geq x_0: \varphi(x)<f_{i+1}(x)\,\!</math>, tedy <math> f_{i+1}\,\!</math> majorizuje všechny funkce z <math> \mathcal{R}_i\,\!</math>

  • Nechť pro spor má <math> A(x,x)\,\!</math> hloubku <math> i\,\!</math>. Potom <math> A(x,x)=\varphi(x)<f_{i+1}(x)\,\!</math> pro nějaké pevné <math> i\,\!</math>. Potom ale <math> \exists x_0\,\!</math>, že <math> A(x,x)<f_{i+1}(x)<f_x(x)\,\!</math>.

Věta (O vztahu PRF, ORF a ČRF)

Platí PRF<math> \subset\,\!</math> ORF <math> \subset\,\!</math> ČRF a inkluze jsou ostré.

Důkaz

Pro ORF<math> \subset\,\!</math> ČRF mám funkci <math> g(x,y)\simeq y + 1\,\!</math> a <math> h(x)\simeq \mu_y(g(x,y)\simeq 0)\,\!</math>, ta není nikde definovaná. Pro PRF<math> \subset\,\!</math> ORF mám Ackermannovu funkci.

Vztah Turingových strojů a částečně rekurzivních funkcí

Definice (Univerzální funkce)

Mějme <math> \mathcal{T}\,\!</math> -- spočetnou množinu ČRF jedné proměnné. Potom <math> \mathcal{U}(i,x)\,\!</math> je univerzální funkce třídy <math> \mathcal{T}\,\!</math>, jestliže:

  • <math> \forall\,\!</math> přirozené <math> i: \lambda x \mathcal{U}(i,x)\in\mathcal{T}\,\!</math>

  • <math> \forall \varphi \in \mathcal{T}: \exists i_0 : \varphi = \lambda x \mathcal{U}(i_0,x)\,\!</math> A <math> \mathcal{U}\,\!</math> tedy indexuje všechny funkce třídy <math> \mathcal{T}\,\!</math>. Podobně se definují i univerzální funkce pro ČRF více proměnných. Platí, že <math> \{\lambda x \mathcal{U}(i,x)\}_{y\geq 0}\,\!</math> je posloupnost všech funkcí z <math> \mathcal{T}\,\!</math>, takže <math> \mathcal{U}\,\!</math> určuje numeraci prvků <math> \mathcal{T}\,\!</math>

Věta (O univerzální funkci PRF)

Existuje ORF, která je univerzální pro třídu PRF (jedné proměnné). Taková funkce pak nemůže být PRF.

Důkaz

  • Seřadím všechny PR-termy (PR-programy) do posloupnosti (máme 3 axiomy a 3 odvozovací pravidla, seřazení je možné).

  • Potom <math> U(x,y):= h_x(y)\,\!</math>, kde <math> h_x\,\!</math> vyčísluje <math> x\,\!</math>-tý program.

  • Sporem nechť <math> U(x,y)\,\!</math> je PRF. Pak i <math> U(x,x)\,\!</math> je PRF, <math> 1\dot{-} U(x,x)\,\!</math> je PRF, z toho <math> 1\dot{-} U(x,x)=U(x_0,x)\,\!</math>. Dosadím <math> x=x_0\,\!</math> a mám spor, neboť obě strany jsou definovány (toto je příklad použití Cantorovy diagonální metody).

Definice (Turingovsky vyčíslitelná funkce)

Vezmeme Turingovy stroje s vnější abecedou, jejíž prvním znakem je "<math> |\,\!</math>". Čísla <math> 0,1,\dots\,\!</math> zapisujme na pásku jako <math> |, ||, |||,\dots\,\!</math>, n-tice oddělujme znakem <math> \lambda\,\!</math>. Potom:

  • Řekneme, že stroj <math> M\,\!</math> je <math> n\,\!</math>-aritmetický, pokud pro každou <math> n\,\!</math>-tici přir. čísel <math> x_1,\dots,x_n\,\!</math> reprezentovanou počáteční konfigurací <math> S\,\!</math> platí: je-li <math> M\,\!</math> použitelný k <math>S</math> (zastaví-li se výpočet nad ní) a je-li výsledná konfigurace <math> T\,\!</math>, pak v <math> T\,\!</math> je na pásce nějaké jedno přirozené číslo a hlava stroje <math> M\,\!</math> stojí nad jeho posledním znakem <math> |\,\!</math>.

  • Stroj je dále <math> n\,\!</math>-aritmetický typu <math> 0/1\,\!</math>, pokud má abecedu <math> \{|,\lambda\}\,\!</math> a jediný koncový stav.

  • Řekneme, že <math> M\,\!</math> vyčísluje funkci <math> f\,\!</math> o <math> n\,\!</math> proměnných, pokud <math> M\,\!</math> je <math> n\,\!</math>-aritmetický a pro každou <math> n\,\!</math>-tici přir. čísel <math> x_1,\dots,x_n\,\!</math> v poč. konfiguraci <math> S\,\!</math> platí: <math> M\,\!</math> je použitelný, právě když je <math> f\,\!</math> pro <math> x_1,\dots,x_n\,\!</math> definovaná a je-li <math> f\,\!</math> definovaná, pak ve výsledné konfiguraci <math> T\,\!</math> je na pásce stroje číslo <math> f(x_1,\dots,x_n)\,\!</math> a hlava stojí nad jeho posledním znakem.

  • Řekneme, že funkce je turingovsky vyčíslitelná, pokud existuje nějaký <math> n\,\!</math>-aritmetický TS (typu <math> 0/1\,\!</math>), který ji vyčísluje.

Věta (O ekvivalenci TS a ČRF)

Funkce <math> n\,\!</math> proměnných je částečně rekurzivní, právě když existuje <math> n\,\!</math>-aritmetický Turingův stroj typu <math> 0/1\,\!</math>, který ji vyčísluje.

Důkaz

"<math> \Leftarrow\,\!</math>": Každá ČRF je T-vyčíslitelná.

Důkaz indukcí -- pro základní funkce to jistě platí, <math> R_n, M_n, S^m_n\,\!</math> toto zachovávají (<math> S^m_n\,\!</math> znamená použití více pásek, vyčíslení a složení, ostatní podobně).

"<math> \Rightarrow\,\!</math>": Pro každý TS <math> M\,\!</math> existuje ČRF, která dává stejný výsledek

Je nutné zavést kódy konfigurací; TS navíc nemají žádné podtřídy, tedy nelze postupovat induktivně. Platí:

  • <math> \mathrm{step}_M(X)\,\!</math> -- jeden krok stroje je PR záležitost (pracuje se nad <math>UqsV</math>, z obou stran obalenými spec. znakem <math> h\,\!</math>, pak slovo není nekonečné a lok. změna se dá spočítat)

  • <math> \mathrm{comp}_M(X,i)\,\!</math> -- výsledek stroje po <math> i\,\!</math> krocích práce je stále PR (for-cyklus)

  • <math> \mu_i(\mathrm{comp}_M(X,i)\mbox{ obsahuje }q_0)\,\!</math> -- <math> q_0\,\!</math> je koncový stav (pracuj, dokud neskončíš)

  • Potom výsledná ČRF <math> g\,\!</math> je dána jako <math> g(\mbox{kód}(S))\simeq \mathrm{result}(\mu_i(\mathrm{comp}_M(X,i)\mbox{ obsahuje }q_0))\,\!</math>, kde result je jednoduchá funkce smazání okrajů atp. BÚNO je takový stroj úplný a <math> q_0\,\!</math> jeho jediný koncový stav. Operátor minimalizace se vyskytuje jen jednou, proto je vhodné ho vysunout co nejvíce "ven" v uzávorkování.

Pak také platí, že mám-li nějakou částečnou funkci (tj. nemusí být totální), která je turingovsky vyčíslitelná, pak je ČR.

Kleenova věta

Věta (Kleenova o normální formě)

Pro každé <math> k \geq 1\,\!</math> existují

  • ČRF <math> \Psi_k\,\!</math> <math> k+1\,\!</math> proměnných

  • PRP <math> T_k\,\!</math> <math> k+2\,\!</math> proměnných

  • PRF <math> U\,\!</math> jedné proměnné

  • PRF <math> s_k\,\!</math> <math> k+1\,\!</math> proměnných

takové, že:

  1. <math> \Psi_k\,\!</math> je univerzální funkcí pro třídu všech ČRF <math> k\,\!</math> proměnných. <math> \Psi_k(e,x_1,\ldots,x_k)\,\!</math> vyčísluje <math> e\,\!</math>-tou ČRF <math> k\,\!</math> proměnných.
    Navíc z odvození ČRF lze efektivně získat <math> e\,\!</math> a naopak z <math> e\,\!</math> lze efektivně získat odvození příslušné ČRF.

  2. <math> \Psi_k(e,x_1,\ldots,x_k) \simeq U(\mu_y T_k(e,x_1,\ldots,x_k,y))\,\!</math>

  3. <math> s_k\,\!</math> jsou prosté funkce rostoucí ve všech proměnných.
    <math> \lambda x_1,\ldots,x_k s_k(e,x_1,\ldots,x_k)\,\!</math>

  4. (tato část Věty o normální formě se nazývá S-m-n věta)
    <math> \Psi_{m+n}(e,z_1,\ldots,z_m,x_1,\ldots,x_n) \simeq \Psi_n(s_m(e,z_1,\ldots,z_m),x_1,\ldots,x_n)\,\!</math>
    <math> T_{m+n}(e,\vec{z},\vec{x}) \equiv T_n(s_m(e,\vec{z}),\vec{x})\,\!</math>

  5. <math> T_k(e,x_1,\ldots,x_k,y) \wedge T_k(e,x_1,\ldots,x_k,z) \Rightarrow y=z\,\!</math>

Důkaz

  • Oklikou přes Turingovy stroje (): ke každé ČRF máme TS kódovaný <math> e\,\!</math>, tak si vezmeme UTS a hledáme jeho funkci.

  • Univerzální TS Y blok1 Y blok2 <math> \Delta\,\!</math> blok3 <math> \times O_1 \times O_2 \ldots \,\!</math> Y. Čísla kódujeme unárně (<math> x\,\!</math> jako <math> x+1\,\!</math> čar).

  • Základní idea -- bez dat UTS vypadá takto: Y M Y blok2 <math> \Delta\,\!</math> blok3 <math> \times O_1 \times O_2 \ldots \,\!</math> Y (očekáváme data).

  • Konstrukce <math> \Psi_m(e,x_1,\ldots,x_m)\,\!</math>: Chceme PRF. Zkontrolujeme, zda <math> e\,\!</math> po rozkódování obsahuje M, jestliže ne, je výsledkem nulová funkce. Jestliže ano, nejlevější výskyt M nahradíme <math> ||\ldots| \lambda ||\ldots|\lambda \ldots \lambda ||\ldots|M\,\!</math> (kódování vstupních dat; substituce) a spustíme program <math> e\,\!</math> na UTS, podle toho získáme výsledek -- <math> \Psi_k\,\!</math>

  • <math> s_k(e,y_1,\dots,y_k)\,\!</math> odpovídá: čekej na <math> x_1,\dots,x_j\,\!</math>, přidej k nim <math> y_1,\dots,y_k\,\!</math> a spusť program <math> e\,\!</math>.

Věta (Vlastnosti predikátu <math> \Psi_k\,\!</math>)

  1. Predikát <math> \Psi_k(e,x_1,\ldots,x_k)\!\!\downarrow\,\!</math> je rekurzivně spočetný, není rekurzivní.

  2. jeho negace <math> \Psi_k(e,x_1,\dots,x_k)\!\!\uparrow\,\!</math> není rekurzivně spočetná.

  3. Dále <math> \Psi_k\,\!</math> nelze rozšířit do ORF. Dokonce pokud <math> \alpha\,\!</math> je ČRF, která je rozšířením <math> \Psi_k\,\!</math>, potom lze efektivně nalézt vstup <math> \vec{z}\,\!</math> takový, že <math> \alpha(\vec{z})\!\!\uparrow\,\!</math>.

Důkaz

  • Z definice je zřejmé, že <math> \Psi_k(\ldots)\!\!\downarrow\,\!</math> je rekurzivně spočetný predikát. Stačí ukázat, že <math> \Psi_k(\ldots)\!\!\uparrow\,\!</math> není rekurzivně spočetný. Z toho přímo plyne, že <math> \Psi_k(\ldots)\!\!\downarrow\,\!</math> není rekurzivní.

  • Bez újmy na obecnosti uvažujme <math> k\!\!=\!\!1\,\!</math>. Použijeme Cantorovu diagonální metodu.

  • Kdyby <math> \Psi_1(\ldots)\!\!\downarrow\,\!</math> byl rekurzivní, potom by <math> \Psi_1(x,x)\!\!\uparrow\,\!</math> byl také rekurzivní, tím spíše rekurzivně spočetný. Tedy pro nějakou ČRF <math> \varphi\,\!</math> by platilo <math> \Psi_1(x,x)\!\!\uparrow \Leftrightarrow \varphi(x)\!\!\downarrow\,\!</math>. Vezmeme-li index funkce <math> \varphi\,\!</math> (označme jej <math> x_0\,\!</math>), dostáváme <math> \Psi_1(x,x)\!\!\uparrow \Leftrightarrow \Psi_1(x_0,x)\!\!\downarrow\,\!</math>, po dosazení <math> x=x_0\,\!</math> dostáváme <math> \Psi_1(x_0,x_0)\!\!\uparrow\Leftrightarrow\Psi_1(x_0,x_0)\!\!\downarrow\,\!</math>, což je spor.

  • Pro důkaz zbytku tvrzení předpokládejme, že <math> h(e,x)\,\!</math> je ORF rozšířením <math> \Psi_1(e,x)\,\!</math>. Potom <math> 1\dot{-} h(x,x)\,\!</math> je ORF <math> g\,\!</math>. Nechť <math> g\,\!</math> má index <math> x_0\,\!</math>, tj. <math> g(x)\simeq \Psi_1(x_0,x)\,\!</math>. Protože <math> g\,\!</math> je ORF, pro všechna <math> x\,\!</math> platí <math> \Psi_1(x_0,x)\!\!\downarrow\,\!</math>, tedy <math> \Psi_1(x_0,x_0)\!\!\downarrow\,\!</math>. Dostáváme <math> h(x_0,x_0)=\Psi_1(x_0,x_0)\,\!</math>, což ovšem vede ke sporu: <math> 1\dot{-} \Psi_1(x_0,x_0) \simeq h(x_0,x_0) \simeq \Psi_1(x_0,x_0)\,\!</math>.

  • Pokud nějaká ČRF <math> \beta\,\!</math> je rozšířením <math> \Psi_1\,\!</math>, umím pro <math> \beta\,\!</math> (podle předch. důkazu) najít <math> e\,\!</math> takové, že <math> \beta(e,e)\!\!\uparrow\,\!</math>.

Komentář

  • Myšlenka obsažená v předchozím důkazu je založená na Cantorově diagonální metodě. Spor na diagonále si vynutí divergenci, neboť rovnost funkcí je jenom podmíněná, tedy v případě divergence je vše v pořádku.

  • Univerzální funkce pro danou třídu funkcí buď nemůže patřit do této třídy, nebo nemůže být totální.

{{Statnice I3}}