Řešené otázky NTIN090/GenRSM

Věta ( Generování RSM ):  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.

Dk

RSM

Bod (2.) věty naznačuje, odkud RSM dostaly své jméno. Je-li $ A $ RSM, nejsme sice obecně schopni algoritmicky rozhodnout, zda $ x ∈ 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á.

$ 1. ⇒ 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~ φ_e $.

Naším cílem je zkonstruovat ORF $ g $ tak, aby platilo $ A = rng~ g $. 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 $ φ_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í: $ a(e) = π_{2,1}(μ⟨x, s⟩_2[x ∈ W_{e,s}]) $. Jedná se při tom o selektor RSP $ (∃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 $ φ_{e1}(e, z) $, která si vyloží parametr z jako dvojici $ z = ⟨x, s⟩_2 $, ověří, zda $ x ∈ W_{e,s} $ a pokud ano, vrátí hodnotu $ x $, v opačném případě vrátí žolíka $ a(e) $, tedy:

$ φ_{e1}(e, z = ⟨x, s⟩_2) ≃ \begin{cases}x \quad & x ∈ W_{e,s} \\ a(e) \quad & \mbox{ jinak }\end{cases} $.

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 $ φ_{e1}(e, z) $ definovaná $ ∀z $. Všimněme si, že definice funkce $ φ_{e1}^{(2)} $ nezávisí na hodnotě $ e $, ta je jí předána jako parametr. Nyní už odvodíme $ g(z) ≃ φ_{e1} (e, z) $, a tedy podle s-m-n věty platí:

$ g(z) ≃ φ_{s-1-1 (e1,e)}(z) ≃ φ_{e1}(e, z) $. Takto jsme tedy spočítali i GČ funkce $ g $ z $ e $. Zřejmě platí, že $ g(z) ∈ W_e $ $ ∀z $, uvažme naopak, že $ ∀b ∈ W_e $ existuje $ s $, pro něž $ b ∈ 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 = rng~ g $.

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

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

Uvědomme si, že rozhodnutí, zda $ g(y)↓= x $ je RSP (plyne například z toho, že $ φ_{e,s}(y)↓ = x $ je PRP a tedy $ g(y)↓ = x ⇔ (∃s)[φe,s(y)↓= x] $ je RSP, dále je tedy i $ (∃y)[g(y)↓ = x] $ RSP, a tedy množina $ 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 $ A = dom~ λx [ μ⟨y, s⟩_2[φ_{e,s}(y)↓= x] ] $.

$ (1. ⇒ 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 φ_e $. Buď $ g(e, x) $ fce definovaná jako:

$ g(e, x) = \begin{cases}x \quad & x ∈ W_e \\ ↑ \quad & \mbox{ jinak }\end{cases} $.

Funkce $ g(e, x) $ je zřejmě ČRF, například proto, že ji lze zapsat jako $ g(e, x) = o(φ_e(x)) + x $ (tj. do nulové funkce vložíme $ φ_e(x) $ jako argument, hodnota tedy na hodnote $ φ_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. ⇒ 3.) $ : Toto je zřejmé. Implikaci $ (3. ⇒ 1.) $ už máme hotovou.