Syntax highlighting of Archiv/Státnice - Algoritmicky vyčíslitelné funkce

{{TOC float}}

{{Sources|
''Tohle je poněkud obšírnější výcuc ke [[Státnice|státnicovým okruhům]] z [[Státnice_-_Informatika_-_Vyčíslitelnost|vyčíslitelnosti]] pro obory [[Státnice_-_Informatika_-_I3:_Matematická_lingvistika|Matematická lingvistika]] a [[Státnice_-_Informatika_-_I2:_Softwarové_systémy|Softwarové systémy]], pocházející ze [http://ladislav.strojil.cz/ Strojilových skript], papírových zápisků [http://atrey.karlin.mff.cuni.cz/~alexak/ A. Kazdy] a zápisků z předmětu [[Vyčíslitelnost I]] ze [[Studnice vědomostí|Studnice]] -- [[User:Tuetschek|Tuetschek]] 14:01, 17 Aug 2010 (CEST)''
}}

==Částečně rekurzivní funkce==

[[wen:Kurt Gödel|K. Gödel]] 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'' <br />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'' <br /> 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'' <br /> 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> f(x_1,\dots,x_n)\downarrow\Leftrightarrow P(x_1,\dots,x_n)\,\!</math> a <math>f(x_1,\dots,x_n)\downarrow\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 [[Státnice_-_Algoritmicky_nerozhodnutelné_problémy#Definice_.28Konfigurace_TS.2FPostovo_slovo.29|konfiguracemi TS]] <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 (''Kleeneův predikát'')
* PRF <math> U\,\!</math> jedné proměnné 
* PRF <math> s_k\,\!</math> <math> k+1\,\!</math> proměnných  

takové, že:  
# <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. <br /> 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. 
# <math> \Psi_k(e,x_1,\ldots,x_k) \simeq U(\mu_y T_k(e,x_1,\ldots,x_k,y))\,\!</math>, kde <math>T_k</math> odpovídá výpočtu Turingova stroje, <math>y=\langle y_0,y_1\rangle</math>, <math>y_0</math> je doba výpočtu, <math>y_1</math> výsledek a <math>U</math> vydělí z <math>\langle y_0,y_1\rangle</math> druhou složku.
# <math> s_k\,\!</math> je prostá funkce rostoucí ve všech proměnných, o které platí (tato část Věty o normální formě se nazývá ''S-m-n věta''): <br /> <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> <br /> <math> T_{m+n}(e,\vec{z},\vec{x}) \equiv T_n(s_m(e,\vec{z}),\vec{x})\,\!</math>
# <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 ([[Státnice - Algoritmicky nerozhodnutelné problémy|Univerzální Turingův stroj]]): ke každé ČRF máme TS a jeho kód <math> e\,\!</math>. Vezmeme si proto UTS, který s kódy umí počítat, a hledáme jeho ČRF. 
* Páska univerzálního stroje vypadá v obecném případě následovně: <center><math>Y\mbox{ blok1 }Y\mbox{ blok2 }\Delta\,\!\mbox{ blok3  }\times O_1 \times O_2 \ldots Y</math></center> První blok je aktuální konfigurace, druhý číslo stavu a třetí aktuální políčko, zbytek je program. Čísla kódujeme unárně (<math> x\,\!</math> jako <math> x+1\,\!</math> čar). 
* Základní idea -- bez proměnných <math>x_1,\dots x_k</math> páska UTS vypadá takto:  <math>Y\ M\ Y\mbox{ blok2 }\Delta\,\!\mbox{ blok3  }\times O_1 \times O_2 \ldots Y</math> (<math>M</math> je kód programu). 
* Konstrukce <math> \Psi_m(e,x_1,\ldots,x_m)\,\!</math>: 
** Zkontrolujeme, zda <math> e\,\!</math> po rozkódování obsahuje nějaký kód programu <math>M</math>.
** Jestliže ne, je výsledkem nulová funkce (syntax error).
** Jestliže ano, nejlevější výskyt <math>M</math> nahradíme <math> ||\ldots| \lambda ||\ldots|\lambda \ldots \lambda ||\ldots|M\,\!</math> (kódování vstupních dat <math>x_1,\dots,x_n</math>; 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>)====

# Predikát <math> \Psi_k(e,x_1,\ldots,x_k)\!\!\downarrow\,\!</math> je rekurzivně spočetný, není rekurzivní. 
# jeho negace <math> \Psi_k(e,x_1,\dots,x_k)\!\!\uparrow\,\!</math> není rekurzivně spočetná. 
# 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>.
Univerzální funkce pro danou třídu funkcí tedy buď nemůže patřit do této třídy, nebo nemůže být totální.

====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>.
* 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.

{{Statnice I3}}