Státnice - Algoritmicky vyčíslitelné funkce

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Tohle je poněkud obšírnější výcuc ke státnicovým okruhům z vyčíslitelnosti pro obory Matematická lingvistika a Softwarové systémy, 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 Studnice -- Tuetschek 14:01, 17 Aug 2010 (CEST)

Částečně rekurzivní funkce[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

  • $ \simeq\,\! $ značí "podmíněnou rovnost", tj. v případě, že alespoň jedna strana má smysl, tak má smysl i druhá a rovnají se.
  • $ P_1(D)\!\!\downarrow\,\! $ značí, že predikát je definován, tj "konverguje" (občas se značí $ !\,\! $ místo $ \downarrow\,\! $)
  • $ P_1(D)\!\!\uparrow\,\! $ 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)[editovat | editovat zdroj]

  • $ o(x)\simeq 0\quad \forall x\in\mathbb{N}\,\! $ ("nula")
  • $ s(x)\simeq x + 1\quad \forall x\in\mathbb{N}\,\! $ ("následník")
  • $ I_n^j(x_1,\dots,x_n) \simeq x_j\quad 1\leq j\leq n\,\! $ ("projekce", vybrání jedne ze složek)

Definice (Základní operátory)[editovat | editovat zdroj]

  • $ R_n\quad (n\geq 1)\,\! $ -- primitivní rekurze
    Funkcím $ f\,\! $ ($ n-1\,\! $ proměnných) a $ g\,\! $ ($ n+1\,\! $ proměnných) přiřadí $ R_n(f,g)=h\,\! $, kde $ h(0,x_2,\dots,x_n)\simeq f(x_2,\dots,x_n)\,\! $ a $ h(y+1,x_2,\dots,x_n)\simeq g(y,h(y,x_2,\dots,x_n),x_2,\dots,x_n)\,\! $ (analogické k for-cyklu).
  • $ S^m_n\,\! $ -- substituce
    Funkci $ f\,\! $ ($ m\,\! $ proměnných) a $ m\,\! $ funkcím $ g_i\,\! $ (všechny $ n\,\! $ proměnných) přiřadí funkci $ h\,\! $ ($ n\,\! $ proměnných) předpisem $ h=S_n^m(f,g_1,\dots,g_m) \equiv h(x_1,\dots,x_n)\simeq f(g_1(x_1,\dots,x_n),\dots,g_m(x_1,\dots,x_n))\,\! $ (analogické k podprogramu).
  • $ M_n\,\! $ -- minimalizace
    Funkci $ f\,\! $ ($ n+1\,\! $ proměnných) přiřadí $ h\,\! $ ($ n\,\! $ proměnných) tak, že
    $ 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\,\! $
    (analogické k while-cyklu).

Další značení:

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

Definice (Třída primitivně a částečně rekurzivních funkcí)[editovat | editovat zdroj]

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

Poznámka (Vlastnosti zákl. funkcí a operátorů)[editovat | editovat zdroj]

  • 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.
  • $ R_n\,\! $, $ S_n^m\,\! $ zachovávají totálnost.
  • PRF jsou efektivně vyčíslitelné a totální.

Definice (Odvození funkce)[editovat | editovat zdroj]

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)[editovat | editovat zdroj]

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

Operace s PRF, predikáty[editovat | editovat zdroj]

Poznámka (Některé PRF)[editovat | editovat zdroj]

Pomocí PRF lze popsat např.:

  • součet
  • součin
  • mocninu, faktoriál
  • operaci $ x\dot{-} y\,\! $, kde $ x\dot{-} y = x-y\,\! $ pro $ x\geq y\,\! $, jinak $ 0\,\! $
  • operátory $ \mathrm{sg}\,\! $ a $ \overline{\mathrm{sg}}\,\! $ (testy na nenulovost, resp. nulovost argumentu)
  • minimum, maximum, absolutní hodnotu rozdílu

Definice (Charakteristická funkce)[editovat | editovat zdroj]

Mějme predikát $ P\,\! $ (libovolné tvrzení) o $ n\,\! $ proměnných. Potom $ c_P\,\! $ je jeho charakteristická funkce, když je to všude definovaná funkce daná následovně:

$ 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}\,\! $


Částečná charakteristická funkce pro nějaký predikát $ P\,\! $ o $ n\,\! $ proměnných je funkce $ f\,\! $ o $ n\,\! $ proměnných taková, že $ f(x_1,\dots,x_n)\downarrow\Leftrightarrow P(x_1,\dots,x_n)\,\! $ a $ f(x_1,\dots,x_n)\downarrow\Rightarrow f(x_1,\dots,x_n) = 1\,\! $.

Definice (PR, OR, RS Predikáty)[editovat | editovat zdroj]

Ř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.

Poznámka (Jiná možnost nahlížení)[editovat | editovat zdroj]

ČRF odpovídají funkcionální logice 1. řádu:

  • termy číselné: $ 0,x,x+1,\dots\,\! $
  • termy funkční: $ o,I_1^1,s,R_2(I_1^1,S_3^1(s,I_3^2)),\dots\,\! $
  • pravidlo aplikace: $ Ap(f,x)=\dots=f(x)\,\! $ (kde "$ \dots\,\! $" je proces vyhodnocení termu, potenciálně nekonečný, dává z funkce číselný term)
  • pravidlo zobecnění: $ \lambda{xy} (x+y)\,\! $ dává z číselného termu $ x+y\,\! $ funkci

Poznámka (Operace zachovávající PR)[editovat | editovat zdroj]

PR jsou:

  • Rozšíření počtu proměnných, konstantní funkce
  • Permutace a ztotožnění proměnných
  • Kódování $ \mathbb{N}^k\,\! $ do $ \mathbb{N}\,\! $ -- iterace Cantorova diagonálního kódování dvojic ($ \langle x,y\rangle_2 = \frac{(x+y)(x+y+1)}{2}+x\,\! $)
  • Opačná operace -- dekódování
  • Funkce $ p(i)\,\! $ -- $ i\,\! $-té prvočíslo
  • Predikát rovnosti a $ <\,\! $, $ >\,\! $
  • Logické spojky $ \vee, \wedge, \neg\,\! $, omezené kvantifikátory (kvantifikace spočetně mnoha prvků)
  • Gödelovo prvočíselné kódování: slovo $ a_{i_0}\dots a_{i_k}\,\! $ do $ p(0)^{i_0}\cdot\dots\cdot p(k)^{i_k}\,\! $

Ackermannova funkce[editovat | editovat zdroj]

Definice (Ackermannova funkce)[editovat | editovat zdroj]

Ackermannova funkce je funkce definovaná jako:

$ A(0,x) = \begin{cases} 1 \quad & x = 0 \\ 2 \quad & x = 1 \\ x + 2 \quad & x > 1 \end{cases} $
$ A(y,0) = 1\,\! $
$ A(y+1,x+1) = A(y, A(y+1,x) )\,\! $

Definice (Strukturální složitost)[editovat | editovat zdroj]

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

$ h(R_n(P,Q)) = \max(h(P), h(Q)+1)\,\! $, $ h(S_n^m(P,Q_0,\dots,Q_k)) = \max(h(P),h(Q_0),\dots,h(Q_k)) $

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

Věta (O Ackermannově funkci)[editovat | editovat zdroj]

Ackermannova funkce není PRF, ale je ORF.

Důkaz[editovat | editovat zdroj]

  • Určitě je ORF -- důkaz se provádí transfinitní indukcí typu $ \omega^2\,\! $; pro výpočet každé hodnoty potřebuji jen konečně mnoho předchozích hodnot -- stačí mi $ \mu_z\,\! $, kde $ z\,\! $ je nejmenší kus $ \mathbb{N}^2\,\! $, který stačí k výpočtu $ A(y,x)\,\! $ (dá práci dokázat, že je konečný, potřeba ordinálů, lexikografického uspořádání).
  • $ A\,\! $ roste rychleji než každá PRF: $ \forall\varphi\,\! $ PRF (jedné proměnné) $ \exists x_0: \forall x\geq x_0: \varphi(x)<A(x,x)\,\! $.
  • Uvažujme $ A(y,x)\,\! $ jako matici funkcí $ f_y(x)\,\! $. Potom určitě $ f_i \in \mathcal{R}_i\backslash \mathcal{R}_{i-1}\,\! $ a $ f_y(x)\,\! $ je (až na konečně mnoho $ x\,\! $) rostoucí. Navíc pro libovolnou $ \varphi\in\mathcal{R}_i\,\! $ existuje $ x_0\,\! $ takové, že $ \forall x\geq x_0: \varphi(x)<f_{i+1}(x)\,\! $, tedy $ f_{i+1}\,\! $ majorizuje všechny funkce z $ \mathcal{R}_i\,\! $
  • Nechť pro spor má $ A(x,x)\,\! $ hloubku $ i\,\! $. Potom $ A(x,x)=\varphi(x)<f_{i+1}(x)\,\! $ pro nějaké pevné $ i\,\! $. Potom ale $ A(x,x)<f_{i+1}(x)<f_x(x) = A(x,x)\,\! $, tj. pro $ x>i+1 $ máme spor.

Věta (O vztahu PRF, ORF a ČRF)[editovat | editovat zdroj]

Platí PRF$ \subset\,\! $ ORF $ \subset\,\! $ ČRF a inkluze jsou ostré.

Důkaz[editovat | editovat zdroj]

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

Univerzální funkce[editovat | editovat zdroj]

Definice (Univerzální funkce)[editovat | editovat zdroj]

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

  • $ \forall\,\! $ přirozené $ i: \lambda x \mathcal{U}(i,x)\in\mathcal{T}\,\! $
  • $ \forall \varphi \in \mathcal{T}: \exists i_0 : \varphi = \lambda x \mathcal{U}(i_0,x)\,\! $

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

Věta (O univerzální funkci PRF)[editovat | editovat zdroj]

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

Důkaz[editovat | editovat zdroj]

  • 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 $ U(x,y):= h_x(y)\,\! $, kde $ h_x\,\! $ vyčísluje $ x\,\! $-tý program.
  • Sporem nechť $ U(x,y)\,\! $ je PRF. Pak i $ U(x,x)\,\! $ je PRF, $ 1\dot{-} U(x,x)\,\! $ je PRF, z toho $ 1\dot{-} U(x,x)=U(x_0,x)\,\! $. Dosadím $ x=x_0\,\! $ 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)[editovat | editovat zdroj]

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

  • Řekneme, že stroj $ M\,\! $ je $ n\,\! $-aritmetický, pokud pro každou $ n\,\! $-tici přir. čísel $ x_1,\dots,x_n\,\! $ reprezentovanou počáteční konfigurací $ S\,\! $ platí: je-li $ M\,\! $ použitelný k $ S $ (zastaví-li se výpočet nad ní) a je-li výsledná konfigurace $ T\,\! $, pak v $ T\,\! $ je na pásce nějaké jedno přirozené číslo a hlava stroje $ M\,\! $ stojí nad jeho posledním znakem $ |\,\! $.
  • Stroj je dále $ n\,\! $-aritmetický typu $ 0/1\,\! $, pokud má abecedu $ \{|,\lambda\}\,\! $ a jediný koncový stav.
  • Řekneme, že $ M\,\! $ vyčísluje funkci $ f\,\! $ o $ n\,\! $ proměnných, pokud $ M\,\! $ je $ n\,\! $-aritmetický a pro každou $ n\,\! $-tici přir. čísel $ x_1,\dots,x_n\,\! $ v poč. konfiguraci $ S\,\! $ platí: $ M\,\! $ je použitelný, právě když je $ f\,\! $ pro $ x_1,\dots,x_n\,\! $ definovaná a je-li $ f\,\! $ definovaná, pak ve výsledné konfiguraci $ T\,\! $ je na pásce stroje číslo $ f(x_1,\dots,x_n)\,\! $ a hlava stojí nad jeho posledním znakem.
  • Řekneme, že funkce je turingovsky vyčíslitelná, pokud existuje nějaký $ n\,\! $-aritmetický TS (typu $ 0/1\,\! $), který ji vyčísluje.

Věta (O ekvivalenci TS a ČRF)[editovat | editovat zdroj]

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

Důkaz[editovat | editovat zdroj]

"$ \Rightarrow\,\! $": Každá ČRF je T-vyčíslitelná.

Důkaz indukcí podle složitosti funkce -- pro základní funkce to jistě platí, $ R_n, M_n, S^m_n\,\! $ toto zachovávají ($ S^m_n\,\! $ znamená použití více pásek, vyčíslení a složení, $ R_n $ znamená vyčíslení $ f $ a $ y $-krát "otočení" $ g $, $ M_n $ je vyčíslování $ f $ na vstupu a zvětšujícím se počítadle cyklů, dokud nedostanu $ 0 $ -- pak vrátím hodnotu počítadla).

"$ \Leftarrow\,\! $": Pro každý TS $ M\,\! $ 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í:

  • $ \mathrm{step}_M(X)\,\! $ -- jeden krok stroje je PR záležitost (pracuje se nad konfiguracemi TS $ UqsV $, z obou stran obalenými spec. znakem $ h\,\! $, pak slovo není nekonečné a lok. změna se dá spočítat). Existuje určitě PR funkce, která popisuje lokální změnu (jde vlastně o rozhodovací strom, který se staví pomocí $ R_n $).
  • $ \mathrm{comp}_M(X,i)\,\! $ -- výsledek stroje po $ i\,\! $ krocích práce je stále PR (for-cyklus -- $ R_n $)
  • $ \mu_i(\mathrm{comp}_M(X,i)\mbox{ obsahuje }q_0)\,\! $ -- $ q_0\,\! $ je koncový stav (pracuj, dokud neskončíš -- while)
  • Potom výsledná ČRF $ g\,\! $ je dána jako $ g(\mathrm{k\acute{o}d}(S))\simeq \mathrm{result}(\mu_i(\mathrm{comp}_M(X,i)\mbox{ obsahuje }q_0))\,\! $, kde result je jednoduchá funkce smazání okrajů atp. BÚNO je takový stroj úplný a $ q_0\,\! $ 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[editovat | editovat zdroj]

Věta (Kleenova o normální formě)[editovat | editovat zdroj]

Pro každé $ k \geq 1\,\! $ existují

  • ČRF $ \Psi_k\,\! $ $ k+1\,\! $ proměnných
  • PRP $ T_k\,\! $ $ k+2\,\! $ proměnných (Kleeneův predikát)
  • PRF $ U\,\! $ jedné proměnné
  • PRF $ s_k\,\! $ $ k+1\,\! $ proměnných

takové, že:

  1. $ \Psi_k\,\! $ je univerzální funkcí pro třídu všech ČRF $ k\,\! $ proměnných. $ \Psi_k(e,x_1,\ldots,x_k)\,\! $ vyčísluje $ e\,\! $-tou ČRF $ k\,\! $ proměnných.
    Navíc z odvození ČRF lze efektivně získat $ e\,\! $ a naopak z $ e\,\! $ lze efektivně získat odvození příslušné ČRF.
  2. $ \Psi_k(e,x_1,\ldots,x_k) \simeq U(\mu_y T_k(e,x_1,\ldots,x_k,y))\,\! $, kde $ T_k $ odpovídá výpočtu Turingova stroje, $ y=\langle y_0,y_1\rangle $, $ y_0 $ je doba výpočtu, $ y_1 $ výsledek a $ U $ vydělí z $ \langle y_0,y_1\rangle $ druhou složku.
  3. $ s_k\,\! $ 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):
    $ \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)\,\! $
    $ T_{m+n}(e,\vec{z},\vec{x}) \equiv T_n(s_m(e,\vec{z}),\vec{x})\,\! $
  4. $ T_k(e,x_1,\ldots,x_k,y) \wedge T_k(e,x_1,\ldots,x_k,z) \Rightarrow y=z\,\! $

Díky tomu lze ČRF efektivně očíslovat. $ \varphi_e(x_1,\dots,x_k) $ pak značí $ e $-tou funkci $ k $ proměnných. Indexu $ e $ se říká Gödelovo číslo funkce.

Důkaz[editovat | editovat zdroj]

  • Oklikou přes Univerzální Turingův stroj: ke každé ČRF máme TS a jeho kód $ e\,\! $. 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ě:
    $ Y\mbox{ blok1 }Y\mbox{ blok2 }\Delta\,\!\mbox{ blok3 }\times O_1 \times O_2 \ldots Y $
    První blok je aktuální konfigurace, druhý číslo stavu a třetí aktuální políčko, zbytek je program. Čísla kódujeme unárně ($ x\,\! $ jako $ x+1\,\! $ čar).
  • Základní idea -- bez proměnných $ x_1,\dots x_k $ páska UTS vypadá takto: $ Y\ M\ Y\mbox{ blok2 }\Delta\,\!\mbox{ blok3 }\times O_1 \times O_2 \ldots Y $ ($ M $ je kód programu).
  • Konstrukce $ \Psi_m(e,x_1,\ldots,x_m)\,\! $:
    • Zkontrolujeme, zda $ e\,\! $ po rozkódování obsahuje nějaký kód programu $ M $.
    • Jestliže ne, je výsledkem nulová funkce (syntax error).
    • Jestliže ano, nejlevější výskyt $ M $ nahradíme $ ||\ldots| \lambda ||\ldots|\lambda \ldots \lambda ||\ldots|M\,\! $ (kódování vstupních dat $ x_1,\dots,x_n $; substituce) a spustíme program $ e\,\! $ na UTS, podle toho získáme výsledek -- $ \Psi_k\,\! $
  • $ s_k(e,y_1,\dots,y_k)\,\! $ odpovídá: čekej na $ x_1,\dots,x_j\,\! $, přidej k nim $ y_1,\dots,y_k\,\! $ a spusť program $ e\,\! $.

Věta (Vlastnosti predikátu $ \Psi_k\,\! $)[editovat | editovat zdroj]

  1. Predikát $ \Psi_k(e,x_1,\ldots,x_k)\!\!\downarrow\,\! $ je rekurzivně spočetný, není rekurzivní.
  2. jeho negace $ \Psi_k(e,x_1,\dots,x_k)\!\!\uparrow\,\! $ není rekurzivně spočetná.
  3. Dále $ \Psi_k\,\! $ nelze rozšířit do ORF. Dokonce pokud $ \alpha\,\! $ je ČRF, která je rozšířením $ \Psi_k\,\! $, potom lze efektivně nalézt vstup $ \vec{z}\,\! $ takový, že $ \alpha(\vec{z})\!\!\uparrow\,\! $.

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[editovat | editovat zdroj]

  • Z definice je zřejmé, že $ \Psi_k(\ldots)\!\!\downarrow\,\! $ je rekurzivně spočetný predikát. Stačí ukázat, že $ \Psi_k(\ldots)\!\!\uparrow\,\! $ není rekurzivně spočetný. Z toho přímo plyne, že $ \Psi_k(\ldots)\!\!\downarrow\,\! $ není rekurzivní.
  • Bez újmy na obecnosti uvažujme $ k\!\!=\!\!1\,\! $. Použijeme Cantorovu diagonální metodu.
  • Kdyby $ \Psi_1(\ldots)\!\!\downarrow\,\! $ byl rekurzivní, potom by $ \Psi_1(x,x)\!\!\uparrow\,\! $ byl také rekurzivní, tím spíše rekurzivně spočetný. Tedy pro nějakou ČRF $ \varphi\,\! $ by platilo $ \Psi_1(x,x)\!\!\uparrow \Leftrightarrow \varphi(x)\!\!\downarrow\,\! $. Vezmeme-li index funkce $ \varphi\,\! $ (označme jej $ x_0\,\! $), dostáváme $ \Psi_1(x,x)\!\!\uparrow \Leftrightarrow \Psi_1(x_0,x)\!\!\downarrow\,\! $, po dosazení $ x=x_0\,\! $ dostáváme $ \Psi_1(x_0,x_0)\!\!\uparrow\Leftrightarrow\Psi_1(x_0,x_0)\!\!\downarrow\,\! $, což je spor.
  • Pro důkaz zbytku tvrzení předpokládejme, že $ h(e,x)\,\! $ je ORF rozšířením $ \Psi_1(e,x)\,\! $. Potom $ 1\dot{-} h(x,x)\,\! $ je ORF $ g\,\! $. Nechť $ g\,\! $ má index $ x_0\,\! $, tj. $ g(x)\simeq \Psi_1(x_0,x)\,\! $. Protože $ g\,\! $ je ORF, pro všechna $ x\,\! $ platí $ \Psi_1(x_0,x)\!\!\downarrow\,\! $, tedy $ \Psi_1(x_0,x_0)\!\!\downarrow\,\! $. Dostáváme $ h(x_0,x_0)=\Psi_1(x_0,x_0)\,\! $, což ovšem vede ke sporu: $ 1\dot{-} \Psi_1(x_0,x_0) \simeq h(x_0,x_0) \simeq \Psi_1(x_0,x_0)\,\! $.
  • Pokud nějaká ČRF $ \beta\,\! $ je rozšířením $ \Psi_1\,\! $, umím pro $ \beta\,\! $ (podle předch. důkazu) najít $ e\,\! $ takové, že $ \beta(e,e)\!\!\uparrow\,\! $.
  • 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.