TIN065 Prednáška 03
Prednášky z Vyčísliteľnosti II |
Obsah |
---|
|
Obsah
Opakovanie
Už vieme, že relativizované programy, teda ČRFály, sa dajú očíslovať. Máme tiež regularizačnú funkciu $ \rho $, ktorá zo všeobecnej rekurzívne spočítateľnej množiny vyrobí ČRFál, a to dokonca tak, že $ W_{\rho(z)} \subseteq W_z $ a tiež $ \Phi_z = W_{\rho(z)} $. A ešte sme si zopakovali, čo to znamená, že množina A je B-rekurzívna.
Teraz si ešte povieme, čo to znamená, že A je B-rekurzívne spočítateľná množina (rekurzívne spočítateľná vzhľadom k B). Nejde o nič iné ako o to, že množina A je doménou nejakej B-ČRF. Formálnejšie: množina A je B-rekurzívne spočítateľná, ak $ A = dom(\Phi_z(B)) $ pre nejaké z.
Taktiež si zavedieme označenia: $ W_{z}^B $ a $ W_{z, s}^B $. $ W_z^B = dom(\Phi_z(B)) = \{y: \Phi_z(B)(y)\downarrow\} $ teda označuje definičný obor funkcie $ \Phi_z(B) $. Podobne $ W_{z, s}^B $ označuje konečnú množinu tých $ y $, o ktorých je možné rozhodnúť, či sú prvkami $ W_{z}^B $, za nanajvýš $ s $ krokov.
O vzťahu $ \leq_T $
Pozorovania:
- Vzťah $ \leq_T $ je reflexívny a tranzitívny.
- Ak A je rekurzívna množina, tak $ A\leq_T B $ pre každé B.
- Ak $ A \leq_T B $ a B je rekurzívna, tak aj A je rekurzívna.
Pozorovania sú viac menej zrejmé. Keďže pri $ \leq_T $ sa jedná o programy, tak budeme jednotlivé vlastnosti ukazovať pomocou programov (čo je iste pochopiteľnejšie, ako formálne pomocou trojíc $ <\sigma, x, y> $).
To, že je $ \leq_T $ reflexívne ($ A \leq_T A $) je jasné, lebo ak máme množinu A ako orákulum, tak vieme triviálne zistiť, či je niečo prvkom množiny A - stačí sa raz spýtať orákula. Pre dôkaz tranzitívnosti nech $ A \leq_T B $ a $ B \leq_T C $. Chceme zistiť, či $ A \leq_T C $. Teda pre dané $ x $ chceme program, ktorý zistí, či $ x \in A $, pričom má k dispozícii iba funkciu is_in_C
, teda iba orákulum C. Vieme, že ak by sme mohli použiť funkciu is_in_B
, teda orákulum B, tak potom takýto program existuje (predpoklad $ A \leq_T B $). Tento program využijeme a namiesto volania nepovolenej funkcie is_in_B
dáme volanie podprogramu, ktorý počíta $ C_B $ iba pomocou orákula C, teda iba pomocou funkcie is_in_C
.
Druhé pozorovanie je podobne triviálne. Ak vieme A charakterizovať bez orákula, teda ak existuje ORF f taká, že $ (\forall x)(C_A(x) = f(x)) $, tak s akýmkoľvek orákulom B to vieme tiež (a tohoto orákula sa nemusíme vôbec na nič pýtať).
Tretie pozorovanie iba hovorí, že za predpokladu, že množinu B vieme rozhodovať, čiže existuje ORF g taká, že $ (\forall x)(C_B(x) = g(x)) $, tak ak by nejaká B-ČRF chcela použiť množinu B ako orákulum, potom vlastne žiadne orákulum nepotrebujeme. Je to preto, lebo keď sa budeme potrebovať spýtať, či $ x \in B $, tak to môžeme zistiť priamym výpočtom (pomocou existujúcej ORF g) a nemusíme využiť orákulum. A tým pádom je možné celú množinu A rozhodovať bez orákula. Inak povedané, majme program na rozhodovanie A, ktorý používa orákulovu funkciu is_in_B
. Túto funkciu len nahradíme podprogramom, ktorý počíta $ C_B $ bez akéhokoľvek orákula a získame tak program, ktorý rozhoduje množinu A bez využitia orákula.
Ekvivalencia $ \equiv_T $ a T-stupne
Keď mám $ \leq_T $, tak je jednoduché zadefinovať reláciu $ \equiv_T $.
$ A \equiv_T B $ ak platí $ A \leq_T B $ & $ B \leq_T A $. $ A \equiv_T B $ je zrejme ekvivalencia a pre ekvivalenciu vieme vyrobiť triedy ekvivalencie. Jedna trieda ekvivalencie potom reprezentuje algoritmicky rovnako zložité množiny. Jednotlivé triedy ekvivalencie $ \equiv_T $ sa označujú malým písmenom, pod ktorým je vlnovka (v TeXu snáď \underset{\widetilde}{a}
, na tejto Wiki $ [a] $) a nazývajú sa "stupne nerozhodnuteľnosti" (degrees of unsolvability). Lepším pojmom sú T-stupne, pretože pre rôzne typy prevoditeľností môžeme rovnakým spôsobom vytvoriť ekvivalencie a ich príslušné triedy nazvať 1-stupne, m-stupne, tt-stupne, wtt-stupne a podobne.
Stupeň $ [\emptyset] $ (trieda ekvivalencie $ \equiv_T $ reprezentovaná prázdnou množinou) sú práve všetky rekurzívne množiny. Ak máme množinu A, tak $ [a] = [a]_T = deg_T(A) = \{B: B \equiv_T A\} $ je T-stupeň obsahujúci množinu A.
Pomocou usporiadania $ \leq_T $ na jednotlivých množinách môžeme na triedach ekvivalencie $ \equiv_T $ zaviesť čiastočné usporiadanie $ \leq $. Formálne ho definujeme takto: $ [A] \leq [B] $ ak platí $ A \leq_T B $ pre ľubovoľné $ A \in [A] $ a $ B \in [B] $. Je jasné, že $ [\emptyset] \leq [B] $ pre každé B. Vyplýva to z druhého bodu pozorovania vyššie.
Mierna odbočka: Ak by sme uvažovali triedu všetkých množín (pozor, nejedná sa o množinu), tak si ich môžeme rozdeliť podľa našej ekvivalencie $ \leq_T $ a zistíme, že jediný T-stupeň, ktorý môžeme algoritmicky rozhodnúť je práve $ [\emptyset] $. Všetky ostatné stupne sú nerekurzívne, takže algoritmicky nerozhodnuteľné. No a práve preto sa tomu hovorí stupne nerozhodnuteľnosti.
Očíslovanie
ČRF vieme očíslovať dvoma spôsobmi. Prvý z nich sa bral na Vyčísliteľnosti I: $ \{\varphi_e\}_{e \in N} $. My si ale tiež môžeme zobrať numeráciu $ \{\Phi_e(\emptyset)\}_{e \in N} $, ktorá predstavuje ČRFály, do ktorých vložíme iba rekurzívne orákulum. Vieme, že takto vzniknuté funkcie sú rekurzívne izomorfné s ČRF, teda máme preklad z čísel numerácie $ \{\varphi_e\}_{e \in N} $ na čísla numerácie $ \{\Phi_e(\emptyset)\}_{e \in N} $. To znamená, že existuje rekurzívna permutácia $ p $ taká, že $ \varphi_e = \Phi_{p(e)}(\emptyset) $. Potom môžeme práve všetky rekurzívne spočítateľné množiny reprezentovať ako $ \{W_z^\emptyset\}_{z \in N} $.
Tento prístup k funkciám a k množinám je univerzálnejší, a preto budeme radšej písať $ \Phi_e(\emptyset) $ ako $ \phi_e $. Poznámka: Ak by sme používali iba $ \Phi_e(B) $ pre $ B \leq_T \emptyset $ (teda ČRFály len s rekurzívnou množinou), dostaneme Vyčísliteľnosť I.
s-m-n veta
Zadefinujeme si, čo je to funkcia viacerých premenných. Je to funkcia jednej premennej, kde dosadíme kód usporiadanej n-tice premenných: $ \Phi_z(B)(x_1, x_2, \dots, x_n) \simeq \Phi_z(B)(<x_1, x_2, \dots, x_n>) $.
Veta:(relativizovaná s-m-n veta) Nech $ \Phi_z(B) $ je univerzálna B-ČRF. Platí s-m-n veta: Existuje PRF $ \bar{s_m} $ $ m + 1 $ premenných taká, že platí:$ \Phi_z(B)(y_1, y_2, \dots, y_m, x_1, x_2, \dots, x_n) \simeq \Phi_{\bar{s_m}(z, y_1, y_2, \dots, y_m)}(B)(x_1, x_2, \dots, x_n) $.
Dôkaz: V pôvodnej verzii pre $ \phi_z $ sa $ s_{m(z, y_1, y_2, \dots, y_m)} $ dalo predstaviť ako triviálny program, ktorý hovoril: Keď dostaneš na vstupe $ z $ a $ (y_1, y_2, \dots, y_n) $, tak spusti $ \varphi_z(y_1, y_2, \dots, y_m, x_1, x_2, \dots, x_n) $. A našťastie aj v relativizovanom prípade tento postup funguje. Tým, že do programu pridáme prípadné otázky na orákulum B sa nič nezmení.
Trochu formálnejšie: pomocou pôvodnej s-m-n vety. Zavedieme pomocnú ČRF $ \alpha $ definovanú takto: $ \alpha(z,x,w)\downarrow \iff (w = <\sigma,y,t> $ & $ <\sigma,<x,y>,t> \in W_{\rho(z)}) $
Táto ČRF $ \alpha $ je definovaná (konverguje), ak $ w $ je kód trojice, ktorá "počíta s fixovanou premennou x". Ináč povedané je to vtedy, ak po pridaní hodnoty x k vstupu y do trojice w, táto nová upravená trojica je prvkom ČRFálu s indexom z. Nech ČRF $ \alpha $ má index e v pôvodnej numerácii $ \{\varphi_e\}_{e \in N} $. Použijeme na ňu nerelativizovanú (inú zatiaľ nemáme :) ) verziu s-m-n vety pre dve premenné: $ \alpha(z,x,w) \simeq \varphi_{s_{2}(e,z,x)}(w) \simeq \varphi_{\beta(z,x)}(w) $. Definičný obor takto definovanej funkcie $ \varphi_{\beta(z,x)}(w) $ tvoria všetky trojice $ <\sigma,y,t> $ z pôvodného ČRFálu $ \Phi_z $, ktoré "počítajú s x". Inak povedané, ak pomocou $ W_{\beta(z,x)} $ definujeme ČRFál, potom ten zo vstupu y (a množiny B) spočíta t práve vtedy, ak pôvodný ČRFál (vytvorený z $ W_{z} $) zo vstupu $ <x,y> $ (a množiny B) spočíta t. A to je presne to, čo chceme od s-m-n vety.
ČRFál $ \Phi_z $, na ktorý sme aplikovali s-m-n vetu, bol reprezentovaný regulárnou množinou trojíc $ W_{\rho(z)} $. Spôsob, akým sme zostrojili množinu $ W_{\beta(z,x)} $ nám zaručuje, že aj ona je regulárna (platí $ W_{\rho(\beta(z,x))} = W_{\beta(z,x)} $), a teda aj ona korektne definuje nový hľadaný ČRFál bez potreby použitia funkcie $ \rho $.
$ \Phi_{z}(B)(x,y) \simeq \Phi_{\beta(z,x)}(B)(y) $
Pomocou ČRF $ \alpha $ sme teda odvodili PRF $ \beta $, ktorá v relativizovanej s-m-n vete hraje úlohu funkcie $ s_m $ z nerelativizovanej verzie.
Poznámka: s-m-n veta platí absolútne: Existuje $ \bar{s_m} $ také, že pre pre každé B a pre každý číselný vstup y, x platí $ \Phi_z(B)(y, x) \simeq \Phi_{\bar{s_m}(z, y)}(B)(x) $. Tiež sa hovorí, že platí uniformne alebo "stejnoměrně" (inšpirácia analýzou je asi zrejmá).
Vyčísliteľnosť I sa nám celkom jednoducho relativizuje. Z ČRF sme si vyrobili B-ČRF a ČRFály, s-m-n veta viac menej ostáva, a tiež vieme relativizovať aj Postovu vetu: A je B-rekurzívna ($ A \leq_T B $) práve vtedy, ak A aj $ \overline{A} $ sú B-rekurzívne spočítateľné (B-RSM). A vieme tiež relativizovať generovanie: A je B-rekurzívne spočítateľná práve vtedy ak existuje prostá (a asi aj úseková) B-ČRF $ f $, ktorá generuje množinu A. A teraz prichádzame k relativizácii halting problému (operácii skoku).
Operácia skoku
Už vieme, že nerelativizovaný halting problém je nerozhodnuteľný, teda nedokážeme o každom programe rozhodnúť, či sa nad daným vstupom zastaví alebo nie. Množina, ktorá halting problém reprezentuje je $ K = \{x : \varphi_x(x)\downarrow\} $ a vieme, že nie je rekurzívna ale rekurzívne spočítateľná. Táto množina reprezentuje halting problém vzhľadom k T-stupňu $ [\emptyset] $, teda vzhľadom k rekurzívnym množinám. My si teraz ukážeme postup, akým sa dá vytvoriť množina reprezentujúca halting problém vzhľadom k najmenšiemu T-stupňu $ [a] $, ktorý obsahuje množinu A.
Definícia: (operácia skoku/relativizovaný halting problém). Pre množinu A definujeme množinu $ A'= \{x: \Phi_x(A)(x)\downarrow\} = \{x: x \in W_x^A\} $. Ide teda o podobnú definíciu akou boli definované množiny $ K = \{x: \varphi_x(x)\downarrow\} = \{x: x \in W_x\} $ a s ňou ekvivalentná $ K_0 = \{<x,y>: x \in W_y\}) $.
Množina A' sa nazýva skok (jump) množiny A.
Pôvodnú množinu $ K = \{x: x \in W_x\} $ môžeme pomocou operácie skoku definovať takto: $ K = \emptyset' $, pretože platí: $ \emptyset' = \{x: x \in W_x^{\emptyset}\} = \{x: x \in W_x\} = K $, čo vyplýva z: $ W_x \equiv W_x^{\emptyset} $. Teda rekurzívne orákulum nám nepomôže a množina $ W_x^{\emptyset} $ je stále rekurzívne spočítateľná. Zápis $ W_x \equiv W_x^{\emptyset} $ znamená, že množina $ W_x $ je rekurzívne izomorfná s množinou $ W_x^{\emptyset} $ a vraj sa to dá jednoducho dokázať.
Skok je množinová operácia z $ A $ do $ A' $. $ A' $ je relativizovaný halting problém. Prirodzeným zovšeobecnením operácie skoku je jej opakované použitie - môžeme ju totiž iterovať:
Definícia:
- $ A^0 = A $ (nultý skok neskáče)
- $ A^{(n+1)} = (A^{(n)})' $
Vraj sa takto dá postupovať aj na $ \omega_0 $ a ďalej, ale to by chcelo trošku lepšie vedieť Temno.
A na koniec prednášky už len znenie jednej vety, ktorá operáciu skoku charakterizuje:
- A' je A-rekurzívne spočítateľná. (obdoba toho, že K je rekurzívne spočítateľná)
- A' nie je A-rekurzívna, $ \overline{A'} $ nie je A-rekurzívne spočítateľná. (obdoba toho istého pre K a $ \overline{K} $).
- B je A-rekurzívne spočítateľná práve vtedy, ak platí $ B \leq_1 A' $. (obdoba toho, že K je 1-úplná).
- Ak A je B-rekurzívne spočítateľná a $ B \leq_T C $, tak A je C-rekurzívne spočítateľná. Pozor, nemýliť si, medzi ktorými dvoma je aký vzťah v predpokladoch!
- $ A \leq_T B \iff A' \leq_1 B' $
- $ A \equiv_T B \iff A' \equiv_1 B' $
V posledných dvoch bodoch je naozaj na jednej strane T-prevoditeľnosť a na druhej 1-prevoditeľnosť. Ale tomu sa budeme venovať až na ďalšej prednáške.