{{theorem | Následující tvrzení jsou ekvivalentní:

1. A je RSM.

2. A je ∅, nebo je $rng$ nějaké ORF

3. A je $rng$ nějaké ČRF.

4. A je $rng$ nějaké rostoucí ČRF.

| Generování RSM }}

Dk ::

{{zarovka |

• Bod (2.) věty naznačuje, odkud RSM dostaly své jméno. Je-li $A$ RSM, nejsme sice obecně schopni algoritmicky rozhodnout, zda $x\in A$, ale jsme schopni efektivně vypsat (enumerate) všechny prvky $A$. O funkci $g$ z tvrzení (2.) budeme též říkat, že generuje množinu $A$. Na rozdíl od RM však nejsme schopni vypsat prvky RSM systematicky, tedy v rostoucím pořadí, a nepodaří se nám ani vyhnout tomu, abychom při výpisu nějaký prvek zopakovali. Funkci, která by byla rostoucí a jejímž oborem hodnot je množina $A$, sice můžeme zkonstruovat, ale musíme v tom případě rezignovat na ORF a na to, aby daná funkce byla všude definovaná, jak ukazuje bod (4). Taková funkce přitom není pro generování množiny $A$ použitelná.

| RSM }}

$1.\Rightarrow 2.$ (konstrukce ORF co pro jakékoli vstupy vrací prvky z A): Předpokládejme, že $A$ je neprázdná RSM, jejíž GČ si označíme pomocí e, tedy $A=W_e=dom{\phi }_e$.

:: Naším cílem je zkonstruovat ORF $g$ tak, aby platilo $A=rngg$. Náš postup navíc ukáže, jak z Gödelova čísla $e$ určit GČ funkce $g$. Rozeberme si nejprve, proč nemůžeme postupovat stejně jako v případě RM. Už postup, kterým jsme u RM hledali nejmenší prvek, v případě RSM selže. Pokud by totiž 0 nepatřila do $A$, tak se cyklus while, v němž bychom nejmenší prvek hledali, zarazí už při výpočtu ${\phi }_e(0)$, neboť tato hodnota není definovaná. Podobně nemůžeme hledat nejmenší prvek větší než zadaný parametr. Musíme proto postupovat opatrněji. Za pvé, nemůžeme sice přímo najít nejmenší prvek, ale můžeme najít nějaký prvek množiny $A=W_e$, a to například následující funkcí:

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 25: …{2,1}(μ⟨x, s⟩_2\̲[̲x ∈ W_{e,s}])

. Jedná se při tom o selektor RSP

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 5: (∃y)\̲[̲y ∈ W_e]

protože tento predikát je splněn díky neprázdnosti $W_e$, bude pro dané $e$ hodnota $a(e)$ definovaná. Takto nalezený prvek použijeme jako jakéhosi žolíka, kterého vrátí konstruovaná funkce $g$ ve chvíli, kdy si neví jinak rady. Sestrojíme nejprve funkci ${\phi }_{e1}(e,z)$, která si vyloží parametr z jako dvojici $z=⟨x,s{⟩}_2$, ověří, zda $x\in W_{e,s}$ a pokud ano, vrátí hodnotu $x$, v opačném případě vrátí žolíka $a(e)$, tedy: ::

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 78: …\ a(e) \quad & \̲m̲b̲o̲x̲{ jinak }\end{c…

. :: Protože $W_{e,s}$ je RM, a hodnota $a(e)$ je pro dané $e$ vždy definovaná vzhledem k neprázdnosti $W_e$, bude hodnota ${\phi }_{e1}(e,z)$ definovaná $\forall z$. Všimněme si, že definice funkce ${\phi }_{e1}^{(2)}$ nezávisí na hodnotě $e$, ta je jí předána jako parametr. Nyní už odvodíme $g(z)\simeq {\phi }_{e1}(e,z)$, a tedy podle s-m-n věty platí: :: $g(z)\simeq {\phi }_{s-1-1(e1,e)}(z)\simeq {\phi }_{e1}(e,z)$. Takto jsme tedy spočítali i GČ funkce $g$ z $e$. Zřejmě platí, že $g(z)\in W_e$ $\forall z$, uvažme naopak, že $\forall b\in W_e$ existuje $s$, pro něž $b\in W_{e,s}$, a tedy $g(⟨b,s{⟩}_2)=b$. Každý prvek $W_e$ je tedy funkcí $g$ pro nějaký vstup $y$ vrácen, jenom nedokážeme odhadnout, pro jak velké $y$. Dohromady dostáváme, že $A=W_e=rngg$.

$(2.\Rightarrow 3.)$ : Plyne z toho, že každá ORF je i ČRF. ∅ je oborem hodnot ČRF, která není definovaná pro žádný vstup.

$(3.\Rightarrow 1.)$ : (pomocí částečné aproximace vyrobíme z ČRF RSP => RSM) Předpokládejme, že $A$ je oborem hodnot ČRF $g\simeq {\phi }_e$.

:: Uvědomme si, že rozhodnutí, zda $g(y)\downarrow =x$ je RSP (plyne například z toho, že ${\phi }_{e,s}(y)\downarrow =x$ je PRP a tedy

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 17: …(y)↓ = x ⇔ (∃s)\̲[̲φe,s(y)↓= x]

je RSP, dále je tedy i

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 5: (∃y)\̲[̲g(y)↓ = x]

RSP, a tedy množina

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 15: A = \{x | (∃y)\̲[̲g(y)↓ = x]\}

je RSM. Ze znalosti GČ $e$ funkce $g$ bychom opět s pomocí s-m-n věty mohli spočítat GČ funkce, jejíž doménou množina $A$ je. Pro úplnost totiž můžeme past

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 13: A = dom~ λx \̲[̲ μ⟨y, s⟩_2\[φ_{…

.

$(1.\Rightarrow 4.)$ : (zkonstruujeme triviální rostoucí ČRF $h(x)=g(e,x)$ u které se $dom$=$rng$) Předpokládejme, že $A=W_e$, tedy $A=dom{\phi }_e$. Buď $g(e,x)$ fce definovaná jako:

::

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 55: …e \\ ↑ \quad & \̲m̲b̲o̲x̲{ jinak }\end{c…

.

:: Funkce $g(e,x)$ je zřejmě ČRF, například proto, že ji lze zapsat jako $g(e,x)=o({\phi }_e(x))+x$ (tj. do nulové funkce vložíme ${\phi }_e(x)$ jako argument, hodnota tedy na hodnote ${\phi }_e(x)$ nezávisí, definovatelnost ano). Položme nyní $h(x)=g(e,x)$, potom je $A$ jak oborem hodnot, tak definičním oborem funkce $h$, funkce $h$ je rostoucí ČRF, jejíž GČ lze opět efektivně spočítat z $e$.

$(4.\Rightarrow 3.)$ : Toto je zřejmé. Implikaci $(3.\Rightarrow 1.)$ už máme hotovou.