{{theorem | Následující tvrzení jsou ekvivalentní:
A je RSM.
A je ∅, nebo je nějaké ORF
A je nějaké ČRF.
A je nějaké rostoucí ČRF.
| Generování RSM }}
Dk ::
{{zarovka |
Bod (2.) věty naznačuje, odkud RSM dostaly své jméno. Je-li RSM, nejsme sice obecně schopni algoritmicky rozhodnout, zda , ale jsme schopni efektivně vypsat (enumerate) všechny prvky . O funkci z tvrzení (2.) budeme též říkat, že generuje množinu . 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 , 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 použitelná.
| RSM }}
(konstrukce ORF co pro jakékoli vstupy vrací prvky z A): Předpokládejme, že je neprázdná RSM, jejíž GČ si označíme pomocí e, tedy .
:: Naším cílem je zkonstruovat ORF tak, aby platilo . Náš postup navíc ukáže, jak z Gödelova čísla určit GČ funkce . 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 , tak se cyklus while, v němž bychom nejmenší prvek hledali, zarazí už při výpočtu , 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 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 RSPParseError: 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 , bude pro dané hodnota definovaná. Takto nalezený prvek použijeme jako jakéhosi žolíka, kterého vrátí konstruovaná funkce ve chvíli, kdy si neví jinak rady. Sestrojíme nejprve funkci , která si vyloží parametr z jako dvojici , ověří, zda a pokud ano, vrátí hodnotu , v opačném případě vrátí žolíka , tedy: ::ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 78: …\ a(e) \quad & \̲m̲b̲o̲x̲{ jinak }\end{c…
. :: Protože je RM, a hodnota je pro dané vždy definovaná vzhledem k neprázdnosti , bude hodnota definovaná . Všimněme si, že definice funkce nezávisí na hodnotě , ta je jí předána jako parametr. Nyní už odvodíme , a tedy podle s-m-n věty platí: :: . Takto jsme tedy spočítali i GČ funkce z . Zřejmě platí, že , uvažme naopak, že existuje , pro něž , a tedy . Každý prvek je tedy funkcí pro nějaký vstup vrácen, jenom nedokážeme odhadnout, pro jak velké . Dohromady dostáváme, že .: Plyne z toho, že každá ORF je i ČRF. ∅ je oborem hodnot ČRF, která není definovaná pro žádný vstup.
: (pomocí částečné aproximace vyrobíme z ČRF RSP => RSM) Předpokládejme, že je oborem hodnot ČRF .
:: Uvědomme si, že rozhodnutí, zda je RSP (plyne například z toho, že 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 iParseError: KaTeX parse error: Undefined control sequence: \[ at position 5: (∃y)\̲[̲g(y)↓ = x]
RSP, a tedy množinaParseError: KaTeX parse error: Undefined control sequence: \[ at position 15: A = \{x | (∃y)\̲[̲g(y)↓ = x]\}
je RSM. Ze znalosti GČ funkce bychom opět s pomocí s-m-n věty mohli spočítat GČ funkce, jejíž doménou množina je. Pro úplnost totiž můžeme pastParseError: KaTeX parse error: Undefined control sequence: \[ at position 13: A = dom~ λx \̲[̲ μ⟨y, s⟩_2\[φ_{…
.: (zkonstruujeme triviální rostoucí ČRF u které se =) Předpokládejme, že , tedy . Buď fce definovaná jako:
::
ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 55: …e \\ ↑ \quad & \̲m̲b̲o̲x̲{ jinak }\end{c…
.:: Funkce je zřejmě ČRF, například proto, že ji lze zapsat jako (tj. do nulové funkce vložíme jako argument, hodnota tedy na hodnote nezávisí, definovatelnost ano). Položme nyní , potom je jak oborem hodnot, tak definičním oborem funkce , funkce je rostoucí ČRF, jejíž GČ lze opět efektivně spočítat z .
: Toto je zřejmé. Implikaci už máme hotovou.