TIN064 Produktivní a kreativní množiny

Wiki-skripta pro Vyčíslitelnost I
Obsah
Úvod (náhled do problematiky) Prerekvizity (co je dobré vědět předem) ČRF, ORF, PRF Rekurzivní spočetnost Převeditelnost RSM Generování RSM Imunní a simple množiny Věty o rekurzi Produktivní a kreativní množiny Neoddělitelné množiny Gödelova věta Seznam zkratek

Zavedení produktivních a kreativních množin

Definice

• Množina B je produktivní, pokud existuje ČRF $ \varphi $ taková, že $ \forall x: W_x \subseteq B \Rightarrow (\varphi(x)\downarrow \And \varphi(x) \in B \smallsetminus W_x) $. Funkce $ \varphi $ se pak nazývá produktivní funkce (pro množinu B).

• Množina A je kreativní, pokud je RS a její doplněk $ \overline{A} $ je produktivní.

Poznámky:

• $ \varphi $ zde neoznačuje univerzální funkci. (Tato dvojznačnost se ovšem používá i na přednášce a ve skriptech, takže je dobré na to být připraven a rozlišovat: toto $ \varphi $ nemá index.)
• Místo $ (\varphi(x)\downarrow \And \varphi(x) \in B \smallsetminus W_x) $ se někdy zkráceně píše $ \varphi(x)\downarrow \in B \smallsetminus W_x $. (Ono kdyby se ten znak konvergence vynechal, tak to vyjde asi nastejno — nedefinovaná hodnota nemůže být elementem. Píše se to ale takto také proto, aby se naznačilo, že konvergence není samozřejmá. I když uvidíme za chvíli...)
• Nechť B je non-RSM a $ W_x \subseteq B $. Pak víme, že zaručeně existuje nějaké $ y \in B \smallsetminus W_x $, protože jinak by se $ W_x $ rovnalo B. Problém je v tom, jak takové $ y $ efektivně najít — tedy sestrojit ČRF $ \varphi $ tak, aby $ \varphi(x)=y $.
• Produktivní množina nemůže být RSM (kdyby byla, byla by pro nějaké x sama svou podmnožinou a produktivní funkce by musela vrátit bod nový bod mimo - spor (množinový rozdíl z definice je tady prázdná množina a v té nemůže být žádný prvek).
• Proč zkoumáme takhle strašně divnou množinu? Godelova věta, ke které celou dobu směřujeme, vlastně dokazuje, že množina pravdivých výroků v matematické logice je produktivní (nějakým odvozovacím pravidlem $ \varphi $ nám z různých podmnožin pravdivých výroků vypadává vždy nějaký mimo ně) a tudíž není RSM.
• Jako mnemotechnickou pomůcku pro produktivní funkce množiny nabízím toto: produktivní funkce produkuje (jak se dozvíme v důkazu následující věty) nekonečně nových bodů.

Příklady

• Vzpomeňme si na množinu $ K=\{x|x \in W_x\} $. Tato množina je kreativní.
  Důkaz: Víme, že K je RSM, zbývá tedy ukázat, že $ \overline{K}=\{x|x \notin W_x\} $ je produktivní. Jako funkci $ \varphi $ zvolme identitu. Nechť je dáno nějaké x takové, že $ W_x \subseteq \overline{K} $ (premisa produktivní množiny). Nyní:
  • Kdyby $ x \in K $, pak $ x \in W_x \subseteq \overline{K} $, což je spor.
  • Kdyby $ x \in W_x $, pak $ x \in K $, což je taktéž spor.
    Dostáváme tedy, že $ x \in \overline{K} \smallsetminus W_x $, čímž jsme dokázali, že $ \varphi(x)=x $ je produktivní funkce pro $ \overline{K} $.

• Platí dokonce obecnější tvrzení: Pokud je f prostá ORF, pak množina $ A=\{f(x)|f(x) \in W_x\} $ je kreativní.
  Důkaz: (obdobně jako v předchozím případě, což byl speciální případ tohoto: f byla identita). Množina A je RSM. Nechť je dáno nějaké x takové, že $ W_x \subseteq \overline{A} $. Kdyby $ f(x) \in A $, pak $ f(x) \in W_x \subseteq \overline{A} $, což je spor. Kdyby $ f(x) \in W_x $, pak $ f(x) \in A $, což je taktéž spor. Dostáváme tedy, že $ f(x) \in \overline{A} \smallsetminus W_x $, čímž jsme dokázali, že $ f(x)\! $ je produktivní funkce pro $ \overline{A} $.

Produktivní obsahuje nekonečnou RSM

"Každá produktivní množina obsahuje nekonečnou RSM."

Důkaz provedeme mírně neformálně: Mějme nějakou produktivní množinu B a její produktivní funkci f. Nejprve nalezneme nějaký index prázdné množiny a nazveme ho $ z_0 $ (tedy $ W_{z_0}=\empty $). Jelikož $ W_{z_0} \subseteq B $, musí nám $ f(z_0) $ vrátit nějaký prvek z B. Nyní najdeme index množiny $ \{f(z_0)\} $ a nazveme jej $ z_1 $ (tedy $ W_{z_1}=\{f(z_0)\} $). $ f(z_1) $ vrátí nějaký nový prvek z B. Takto pokračujeme dále a umíme najít RS podmnožinu B libovolné velikosti.

Šel by takto sestrojit algoritmus, respektive ČRF, jejíž definiční obor by byl nekonečný a zároveň by byl podmnožinou B. Takový definiční obor je hledanou množinou.

Důsledek

Produktivní množiny nejsou imunní. Kreativní množiny nejsou simple.

Věta o produktivní ORF

"Každá produktivní množina má produktivní funkci, která je ORF."

Jak se nedokazuje

Mějme nějakou produktivní množinu B a její produktivní ČRF $ \varphi $. První nápad, jak sestrojit produktivní ORF f pro B by mohl být: dodefinujme $ \varphi $. Takto snadno to bohužel nejde. Neumíme totiž efektivně zjistit, zda $ \varphi(x)\downarrow $ ani zda $ \neg (W_x \subseteq B) $ — kdybychom uměli to druhé, tak pro všechna taková x nadefinujeme $ f(x)=0 $ (či libovolná jiná hodnota).

Jak se dokazuje

Opět máme produktivní množinu B a její produktivní ČRF $ \varphi $. Hledanou ORF f získáme jako složení: $ f(x):=\varphi(g(x)) $ pro nějakou vhodnou funkci g. K tomu se ovšem dostaneme až na konci důkazu. (Ve skriptech je důkaz uveden "retrospektivně", což mi přišlo trochu nepřehledné, proto budu postupovat "chronologicky".)

Zkonstruujme funkci $ \alpha $ tak, aby $ \alpha(x,y,z)\downarrow \Leftrightarrow \varphi(x)\downarrow \And z \in W_y $. Na tom jakou konkrétní hodnotu bude $ \alpha $ vracet nezáleží, důležité je pouze, zda konverguje, či ne. Vidíme, že $ \alpha $ je ČRF, tedy můžeme nalézt její index e a poté použít s-m-n větu:

$ \alpha(x,y,z) \simeq \psi_3(e,x,y,z) \simeq \psi_1(s_2(e,x,y),z) $

Položme nyní $ \beta(x,y) = s_2(e,x,y)\! $ (což je PRF). Dostáváme tak, že $ \psi_1(\beta(x,y),z)\downarrow \Leftrightarrow \varphi(x)\downarrow \And z \in W_y $.

Čemu se bude rovnat $ W_{\beta(x,y)} $? Pokud $ \varphi(x)\uparrow $, pak $ W_{\beta(x,y)}=\empty $. Pokud $ \varphi(x)\downarrow $, pak $ W_{\beta(x,y)}=W_y\! $.

Nyní na funkci $ \beta $ použijeme větu o rekurzi, konkrétně variantu s parametry. Ta říká, že existuje PRF g (pro náš účel jedné proměnné) taková, že $ \forall z: \psi(\beta(g(y),y),z) \simeq \psi(g(y),z) $.

Tedy $ W_{g(y)} = W_{\beta(g(y),y)} = \begin{cases} W_y & \mbox{pokud }\varphi(g(y))\downarrow \\ \empty & \mbox{pokud }\varphi(g(y))\uparrow \end{cases} $

Nebojte, už se blížíme do finiše, a nebyla by to ta pravá ořechová vyčíslitelnost, kdybychom nepoužili žádný self-referenční trik. Pomocí něho totiž dokážeme, že $ \varphi(g(y)) $ nemůže divergovat, a tedy je naše nová funkce $ f(y):=\varphi(g(y)) $ totální ORF. Pro spor nechť $ \varphi(g(y))\uparrow $. Pak $ W_{g(y)}=\empty \subseteq B $ pro libovolnou množinu B. Protože $ \varphi $ je produktivní funkce pro B, musí $ \varphi(g(y))\downarrow $, což je spor s předpokladem.

Nová funkce f je tedy ORF, ale je i produktivní? Pro každé y platí $ W_{g(y)} = W_y\! $. Pokud pro nějaké y je$ W_y \subseteq B $, pak i $ W_{g(y)} \subseteq B $ a $ \varphi(g(y)) \in B \smallsetminus W_{g(y)} $, protože původní $ \varphi $ byla produktivní. Tedy $ W_y \subseteq B \Rightarrow \varphi(g(y)) \in B \smallsetminus W_y $, čímž jsme dokázali, že nová f je taktéž produktivní pro B. $ \Box $

Dodatek

To, že $ W_{g(y)} = W_y\! $ ještě neznamená, že $ g(y) = y $. Znamená to jen, že programy s těmito indexy jsou ekvivalentní. Pokud by vám toto uniklo (jako původně mně), mohli byste si myslet, že už původní funkce $ \varphi $ byla totální a my jsme to jen dokázali pomocí triku s g — ne, tak to samozřejmě není.

My pomalejší, když důkaz dočteme, kulíme oči na to, co to tedy funkce $ g(y) $ vlastně dělá. Když se na to díváme jako na program, je to docela jednoduché: Pro každé $ y $ sestrojíme nějaký program s kódem $ k $, který dělá následující:

1. spustí $ f(k) $, zahodí výsledek
2. spustí $ \varphi_y(x) $, zahodí výsledek
3. vrátí třeba nulu (důležité je, že když už obě předchozí funkce konvergovaly, tak zakonverguje)

Věta o produktivní ORF bijekci

"Každá produktivní množina má produktivní funkci, která je rekurzivní permutací, tedy ORF bijekcí."

V předchozí větě jsme dokázali, že pro každou produktivní množině B lze upravit její produktivní ČRF na ORF. Nyní tvrzení ještě zesílíme a dokážeme, že lze nalézt takovou produktivní ORF, která bude navíc bijekcí (rek. permutací), tedy prostá a na.

Mějme produktivní množinu B a její produktivní funkci f. Díky předchozí větě můžeme předpokládat, že f je ORF. Konstrukci hledané produktivní bijektivní ORF h provedeme ve dvou krocích: nejprve upravíme f na g, aby g byla na (surjektivní). Pak upravíme g na h, která bude prostá, a to tak, aby surjektivnost (jak to říct česky? vlastnost na?) zůstala zachována.

Konstrukce surjektivní funkce g

Nejprve vytvoříme nekonečnou rekurzivní množinu M takovou, že $ x \in M \Rightarrow W_x=\mathbb{N} $. Jinak řečeno, vybereme indexy nějakých programů (ne nutně všech, chceme přece, aby množina byla rekurzivní), které se zastaví pro každý vstup.

Pro libovolné $ x \in M $ tedy z definice produktivní množiny platí, že $ W_x \not \subseteq B $, a proto $ g(x) $ můžeme zvolit libovolně a produktivitu funkce g to neovlivní. Definujme g následovně: $ g(x)= \begin{cases} f(x) & \mbox{pro } x \notin M \\ j & \mbox{pro } x \in M \And x \mbox{ je j-tým prvkem } M \end{cases} $

Jelikož M je nekonečná, tak g bude na. Zároveň g zůstane produktivní, protože f byla produktivní.

Konstrukce prosté funkce h

Základní myšlenka je prostá stejně jako výsledná funkce h :-). $ h(x) $ budeme postupně pro $ x=0,1,\dots $ definovat stejně jako $ g(x) $ a pouze v případě, že bychom měli porušit prostotu, tak $ h(x) $ definujeme nějak jinak.

První krok je jasný: $ h(0):=g(0)\! $. Další kroky: Pokud $ g(x) \notin \{h(0),h(1),...,h(x-1)\} $, tak $ h(x):=g(x)\! $. Pokud by se $ g(x) $ trefilo do nějaké už dříve vybrané ("zablokované") hodnoty, musíme najít něco jiného:

Najdeme index $ y_1 $ množiny $ W_x \cup \{g(x)\}=Y_1=W_{y_1} $ a zkusíme aplikovat g na tento index. O vztahu (z pohledu inkluze) mezi množinami $ W_x $ a $ B $ nic nevíme, proto má následující dělení na případy smysl a je zároveň nutné.

• Předpokládejme nyní, že $ Y_1 \subseteq B $. Pak z produktivity g plyne, že $ g(y_1) \in B \smallsetminus Y_1 $. Pokud $ g(y_1) \notin \{h(0),h(1),...,h(x-1)\} $, tak máme vyhráno ($ h(x):=g(y_1) $). V opačném případě iterujeme stejný postup, tedy najdeme index $ y_2 $ množiny $ Y_1 \cup \{g(y_1)\}=Y_2=W_{y_2} $ (všimněme si, že $ Y_2 \subseteq B $ protože $ Y_1 \subseteq B $ a $ g(y_1) \in B $) a zkusíme, zda $ g(y_2) \notin \{h(0),h(1),...,h(x-1)\} $. Vytváříme prostou posloupnost prvků $ g(y_i) $ potenciálně vhodných pro $ h(x) $. Nejpozději po $ x+1 $ krocích se nám tedy musí podařit najít nějaké "neblokované" $ g(y_i)=h(x) $. Ještě by mohlo někoho napadnout, že můžeme vyčerpat prvky $ y_i $, to však nemůžeme z definice produktivní množiny, takže skutečně najdeme "neblokované" $ g(y_i)=h(x) $.

• Pokud byl náš předpoklad $ Y_1 \subseteq B $ nepravdivý, tak můžeme $ h(x) $ zvolit libovolně z množiny $ \mathbb{N} \smallsetminus \{h(0),h(1),...,h(x-1)\} $. To, že byl předpoklad nepravdivý ovšem můžeme zjistit, až když uděláme $ x+1 $ neúspěšných iterací, ale ta trocha práce navíc nás nezabije (a hlavně to jinak zjistit neumíme, alespoň já teda ne).

Zkonstruovali jsme h, která je produktivní funkcí pro B, je prostá a od f "zdědila" totálnost a od g surjektivnost. $ \Box $

Věta o ekvivalenci pojmů

Následující tvrzení jsou ekvivalentní:

1. $ \overline{K} \le_1 B $
2. $ \overline{K} \le_m B $
3. B je produktivní.

Pro připomenutí $ \overline{K}=\{x| x \notin W_x\} $. Tato věta tedy mimo jiné říká, že $ \overline{K} $ je nejjednodušší produktivní množina, přičemž výrokem "A je jednodušší než B" zde rozumíme "A je 1-převeditelné na B" ($ A \le_1 B $), případně "A je m-převeditelné na B" ($ A \le_m B $), protože to v tomto případě vyjde nastejno. Jak to, že je $ \overline{K} $ nejjednodušší produktivní? Mějme libovolnou produktivní B, pak implikace $ 3 \Rightarrow 1 $ říká, že $ \overline{K} $ je jednodušší než B (lidově řečeno "znám-li B, znám i $ \overline{K} $").

Důkaz provedeme osvědčeným postupem: $ 1 \Rightarrow 2, 2 \Rightarrow 3 \mbox{ a } 3 \Rightarrow 1 $.

Důkaz: 1. implikuje 2.

Tuto část důkazu sem píšu jen tak pro pořádek, neboť to triviálně vyplývá z definice 1- a m- převoditelnosti.

Důkaz: 2. implikuje 3.

Již víme, že množina $ \overline{K} $ je produktivní. Dokážeme nyní lemma, která říká, že produktivita se zachovává směrem vzhůru při uspořádání $ \le_m $. Tím dokážeme i implikaci $ 2 \Rightarrow 3 $.

Lemma: $ (C \mbox{ produktivní} \And C \le_m B) \Rightarrow B\mbox{ produktivní} $.

Důkaz: Z předpokladu $ C \le_m B $ máme ORF h, pro níž platí $ x \in C \iff h(x) \in B $. Z předpokladu máme dále funkci f, která je produktivní pro C. Chceme najít ČRF $ \alpha $ produktivní pro B, tedy takovou, že $ W_x \subseteq B \Rightarrow \alpha(x) \in B \smallsetminus W_x $.

Nepřítel (a těch je matematika, jak jistě víte, plná) nám zadá x takové, že $ W_x \subseteq B $. Víme, že $ h^{-1}(W_x)\subseteq C $ a pokud bychom našli index q množiny $ h^{-1}(W_x) $ pomocí nějaké ORF g (tedy $ h^{-1}(W_x) = W_{g(x)} = W_q = \{y|h(y) \in W_x\} $, tak máme téměř vyhráno.

Na index q aplikujeme funkci f, takže získáme $ f(q) \in C \smallsetminus W_q $. Pomocí funkce h se "vrátíme zpět do B", tedy $ h(f(q)) \in B \smallsetminus W_x $. Hledanou funkci $ \alpha $ dostaneme tedy složením: $ \alpha(x) = h(f(g(x))) $.

Zbývá doplnit, jak se získá funkce g. Ano, správně tušíte, že jsme již dlouho nepoužili s-m-n větu. Sestrojíme tedy pomocnou funkci $ \beta $ tak, aby $ \beta(x,y)\downarrow \iff h(y) \in W_x $ (což je přesně $ W_q $ o pár řádků výše; na hodnotě $ \beta(x,y) $ opět nezáleží). Tato funkce je ČRF, tedy lze nalézt její index e takový, že $ \beta(x,y) \simeq \psi_2(e,x,y) \simeq \psi_1(g(x),y) \simeq \varphi_{g(x)}(y) $ — zde jsme použili s-m-n větu a g definovali tak, že $ g(x)=s_1(e,x) $. Máme tedy $ W_{g(x)} = dom(\varphi_{g(x)}) = \{y| \varphi_{g(x)}(y)\downarrow\} = \{y|h(y)\in W_x\} = h^{-1}(W_x) $.

Důkaz: 3. implikuje 1.

Nejtěžší část důkazu jsme si tradičně nechali na konec. Máme dánu produktivní množinu B s její produktivní funkcí f, o které dle předchozích vět můžeme předpokládat, že je to prostá ORF. Chceme najít prostou ORF h takovou, že $ x \in \overline{K} \iff h(x) \in B $. Postup bude podobný jako v několika předchozích důkazech: postupně použijeme s-m-n větu a větu o rekurzi.

Nejprve zkonstruujeme pomocnou funkci $ \beta $ tak, aby $ \beta(y,x,w)\downarrow \iff w=f(y) \And x \in K $. Množina K je RSM a f je ORF, tedy $ \beta $ je ČRF a má nějaký index e: $ \beta(y,x,w) \simeq \psi_3(e,y,x,w) \simeq \psi_1(\alpha(y,x),w) \simeq \varphi_{\alpha(y,x)}(w) $ (podle s-m-n věty, $ \alpha(y,x)=s_2(e,y,x) $).

Máme tedy $ \varphi_{\alpha(y,x)}(w)\downarrow \iff w = f(y) \And x \in K $, čili $ W_{\alpha(y,x)} = \{w|w=f(y) \And x \in K\} $.

Podle věty o rekurzi (ve variantě s parametry použité na funkci $ \alpha $) víme, že existuje PRF g taková, že $ \varphi_{g(x)}(z) \simeq \varphi_{\alpha(g(x),x)}(z) $. To znamená, že $ W_{g(x)}=W_{\alpha(g(x),x)}=\{w| w=f(g(x)) \And x \in K\}\! $, což je ekvivalentní (Jak jsme vybrali prázdnou množinu? Definicí?):

$ W_{g(x)} = \begin{cases} \{f(g(x))\} & \mbox{pokud } x \in K \\ \empty & \mbox{pokud } x \in \overline{K} \end{cases} $

Máme tedy: $ x \in \overline{K} \Rightarrow W_{g(x)}=\empty \subseteq B \Rightarrow f(g(x)) \in B \smallsetminus W_{g(x)}= B $.
A naopak: $ x \in K \Rightarrow W_{g(x)}=\{f(g(x))\} \not \subseteq B \Rightarrow f(g(x)) \notin B $. Musíme ještě vysvětlit, proč $ W_{g(x)}=\{f(g(x))\} \not \subseteq B $. Předpokládejme pro spor opak, tedy $ W_{g(x)}=\{f(g(x))\} \subseteq B $, tedy $ W_{g(x)} \subseteq B $. Pak z produktivity f plyne, že $ f(g(x)) \in (B \smallsetminus W_{g(x)}) = B \smallsetminus \{f(g(x))\} $, což je spor.

Tímto jsme dokázali, že $ x \in \overline{K} \iff h(x)=f(g(x)) \in B $, tedy že $ \overline{K} \le_1 B $ (h je prostá ORF, neboť je složením dvou prostých ORF).

$ \Box $

Jiná věta o ekvivalenci pojmů

Následující tvrzení jsou ekvivalentní:

1. A je 1-úplná
2. A je m-úplná
3. A je kreativní.

Tato věta je přímým důsledkem předchozí věty. Zajímavá je tím, že spojuje pojmy (kreativita a úplnost), které byly definovány zcela odlišně.

Připomeňme, že množina M je 1-úplná, pokud M je RSM a každá RSM A je 1-převoditelná na M ($ \forall A \in RSM: A \le_1 M $).

Důkaz: 1. implikuje 2.

Je triviální.

Důkaz: 2. implikuje 3.

Nechť A je m-úplná. K je RSM, tedy z definice m-úplnosti plyne $ K \le_m A $. Protože m-převoditelnost (i 1-převoditelnost) se zachovává při "přechodu k doplňkům", platí i $ \overline{K} \le_m \overline{A} $. Dle předchozí věty je tedy $ \overline{A} $ produktivní. A je RSM (z definice m-úplnosti). Tudíž A je kreativní.

Důkaz: 3. implikuje 1.

Nechť je A kreativní, pak $ \overline{A} $ je produktivní a dle předchozí věty je $ \overline{K} \le_1 \overline{A} $ a $ K \le_1 A $. O množině K jsme již dříve dokázali, že je 1-úplná, a zde vidíme, že A je složitější než K a přitom je (z definice kreativity) RS. Tudíž i A je 1-úplná.

Úplně produktivní množiny

Definice

Množina B je úplně produktivní, pokud existuje ORF f taková, že $ \forall x: (f(x) \in B \smallsetminus W_x) \mbox{ nebo } (f(x) \in W_x \smallsetminus B) $.

Produktivní jsou úplně produktivní

"B je produktivní $ \iff $ B je úplně produktivní."

Důkaz:

"$ \Leftarrow $": Mějme B úplně produktivní s úplně produktivní funkcí f. Pokud $ W_x \subseteq B $, pak $ W_x \smallsetminus B = \empty $, tudíž musí nutně platit $ f(x) \in B \smallsetminus W_x $, čímž jsme dokázali, že B je produktivní.

"$ \Rightarrow $": Ve větě o ekvivalenci pojmů (v důkazu $ \overline{K} \le_m B \Rightarrow B \mbox{ je produktivní} $) jsme si chytře dokázali lemma, že produktivita se zachovává směrem vzhůru v uspořádání $ \le_m $. Pokud si v důkazu tohoto lemmatu nahradíte produktivitu úplnou produktivitou, vše bude fungovat stejně. Tedy jsme dokázali (kterou asi metodou?), že $ (C \mbox{ úplně produktivní} \And C \le_m B) \Rightarrow B\mbox{ úplně produktivní} $.

Dále si dokážeme, že $ \overline{K} $ je úplně produktivní: Jako funkci f můžeme zvolit identitu. Pokud $ x \in W_x $, tak $ x \in W_x \smallsetminus \overline{K} $. Pokud $ x \notin W_x $, tak $ x \in \overline{K} \smallsetminus W_x $.

Takto vyzbrojeni již snadno zvládneme zbývající implikaci. Mějme B produktivní. Z věty o ekvivalenci pojmů víme, že $ \overline{K} \le_m B $. A z předchozích dvou odstavců plyne, že B je úplně produktivní.

Tot je produktivní

"Množina $ Tot= \{x|\varphi_x \mbox{ je totální}\} = \{x|W_x = \mathbb{N}\} $ je produktivní."

Pokud dokážeme, že $ \overline{K} \le_m Tot $, je zbytek jednoduchý: viz předchozí odstavce. Chceme tedy najít nějakou ORF f takovou, aby $ x \in \overline{K} \iff f(x) \in Tot $.

Vzpomeňme si na PRP $ T_i $ z Kleeneho věty o normální formě, kde $ T_1(e,x,k) $ je pravda, pokud se e-tý program zastaví na vstupu x po k krocích. Vytvoříme si ČRF $ \beta $ tak, aby $ \beta(x,j)\uparrow \iff \exists k : k \le j \And T_1(x,x,k) $. Funkce $ \beta $ tedy diverguje právě tehdy, když "x padne do K během j kroků".

Nyní použijeme tradičně s-m-n větu: $ \beta(x,j) \simeq \varphi_e(x,j) \simeq \varphi_{f(x)}(j) $. Platí: $ f(x) \in Tot \iff W_{f(x)} = \mathbb{N} \iff x \notin K $. Hledaná funkce je tedy $ f(x)=s_1(e,x) $. $ \Box $