TIN065 Prednáška 03

Prednášky z Vyčísliteľnosti II
Obsah
Prehľad Prvá prednáška Druhá prednáška Tretia prednáška Štvrtá prednáška Piata prednáška Šiesta prednáška Siedma prednáška Ôsma prednáška Deviata prednáška Desiata prednáška Jedenásta prednáška Dvanásta prednáška Zhrnutie na skúšku

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:

1. Vzťah $ \leq_T $ je reflexívny a tranzitívny.
2. Ak A je rekurzívna množina, tak $ A\leq_T B $ pre každé B.
3. 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:

1. A' je A-rekurzívne spočítateľná. (obdoba toho, že K je rekurzívne spočítateľná)
2. 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} $).
3. B je A-rekurzívne spočítateľná práve vtedy, ak platí $ B \leq_1 A' $. (obdoba toho, že K je 1-úplná).
4. 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!
5. $ A \leq_T B \iff A' \leq_1 B' $
6. $ 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.