{{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 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 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 : $\{\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 .
## 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)()$.
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,,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 $$ (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á).
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 \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ť .
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.