{{TIN065 Prednášky}}

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 [[wen:Turing degree|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 <b>un</b>solvability). 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 <Teorie%20množin> 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 <b>ne</b>rozhodnuteľnosti.

Očíslovanie

ČRF vieme očíslovať dvoma spôsobmi. Prvý z nich sa bral na <Vyčíslitelnost%20I>: \{\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číslitelnost%20I>.

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>).

<b>Veta:</b><em>(relativizovaná s-m-n veta)</em> 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).

<b>Dôkaz:</b> 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číslitelnost%20I> 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.

<b>Definícia:</b> (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ť <Teorie%20množin>.

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.