{{TIN065 Prednášky}}

Opakovanie

Už vieme, že relativizované programy, teda ČRFály, sa dajú očíslovať. Máme tiež regularizačnú funkciu <math>\rho</math>, ktorá zo všeobecnej rekurzívne spočítateľnej množiny vyrobí ČRFál, a to dokonca tak, že <math>W_{\rho(z)} \subseteq W_z</math> a tiež <math>\Phi_z = W_{\rho(z)}</math>. 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 <math>A = dom(\Phi_z(B))</math> pre nejaké z.

Taktiež si zavedieme označenia: <math>W_{z}^B</math> a <math>W_{z, s}^B</math>. <math>W_z^B = dom(\Phi_z(B)) = \{y: \Phi_z(B)(y)\downarrow\}</math> teda označuje definičný obor funkcie <math>\Phi_z(B)</math>. Podobne <math>W_{z, s}^B</math> označuje konečnú množinu tých <math>y</math>, o ktorých je možné rozhodnúť, či sú prvkami <math>W_{z}^B</math>, za nanajvýš <math>s</math> krokov.

O vzťahu <math>\leq_T</math>

Pozorovania:

#Vzťah <math>\leq_T</math> je reflexívny a tranzitívny. #Ak A je rekurzívna množina, tak <math>A\leq_T B</math> pre každé B.

#Ak <math>A \leq_T B</math> a B je rekurzívna, tak aj A je rekurzívna. Pozorovania sú viac menej zrejmé. Keďže pri <math>\leq_T</math> sa jedná o programy, tak budeme jednotlivé vlastnosti ukazovať pomocou programov (čo je iste pochopiteľnejšie, ako formálne pomocou trojíc <math><\sigma, x, y></math>).

To, že je <math>\leq_T</math> reflexívne (<math>A \leq_T A</math>) 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 <math>A \leq_T B</math> a <math>B \leq_T C</math>. Chceme zistiť, či <math>A \leq_T C</math>. Teda pre dané <math>x</math> chceme program, ktorý zistí, či <math>x \in A</math>, 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 <math>A \leq_T B</math>). Tento program využijeme a namiesto volania nepovolenej funkcie is_in_B dáme volanie podprogramu, ktorý počíta <math>C_B</math> 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 <math>(\forall x)(C_A(x) = f(x))</math>, 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 <math>(\forall x)(C_B(x) = g(x))</math>, 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 <math>x \in B</math>, 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 <math>C_B</math> bez akéhokoľvek orákula a získame tak program, ktorý rozhoduje množinu A bez využitia orákula.

Ekvivalencia <math>\equiv_T</math> a [[wen:Turing degree|T-stupne]]

Keď mám <math>\leq_T</math>, tak je jednoduché zadefinovať reláciu <math>\equiv_T</math>.

<math>A \equiv_T B</math> ak platí <math>A \leq_T B</math> & <math>B \leq_T A</math>. <math>A \equiv_T B</math> je zrejme ekvivalencia a pre ekvivalenciu vieme vyrobiť triedy ekvivalencie. Jedna trieda ekvivalencie potom reprezentuje algoritmicky rovnako zložité množiny. Jednotlivé triedy ekvivalencie <math>\equiv_T</math> sa označujú malým písmenom, pod ktorým je vlnovka (v TeXu snáď \underset{\widetilde}{a}, na tejto Wiki <math>[a]</math>) 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ň <math>[\emptyset]</math> (trieda ekvivalencie <math>\equiv_T</math> reprezentovaná prázdnou množinou) sú práve všetky rekurzívne množiny. Ak máme množinu A, tak <math>[a] = [a]_T = deg_T(A) = \{B: B \equiv_T A\}</math> je T-stupeň obsahujúci množinu A.

Pomocou usporiadania <math>\leq_T</math> na jednotlivých množinách môžeme na triedach ekvivalencie <math>\equiv_T</math> zaviesť čiastočné usporiadanie <math>\leq</math>. Formálne ho definujeme takto: <math>[A] \leq [B]</math> ak platí <math>A \leq_T B</math> pre ľubovoľné <math>A \in [A]</math> a <math>B \in [B]</math>. Je jasné, že <math>[\emptyset] \leq [B]</math> 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 <math>\leq_T</math> a zistíme, že jediný T-stupeň, ktorý môžeme algoritmicky rozhodnúť je práve <math>[\emptyset]</math>. 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 : <math>\{\varphi_e\}_{e \in N}</math>. My si ale tiež môžeme zobrať numeráciu <math>\{\Phi_e(\emptyset)\}_{e \in N}</math>, 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 <math>\{\varphi_e\}_{e \in N}</math> na čísla numerácie <math>\{\Phi_e(\emptyset)\}_{e \in N}</math>. To znamená, že existuje rekurzívna permutácia <math>p</math> taká, že <math>\varphi_e = \Phi_{p(e)}(\emptyset)</math>. Potom môžeme práve všetky rekurzívne spočítateľné množiny reprezentovať ako <math>\{W_z^\emptyset\}_{z \in N}</math>.

Tento prístup k funkciám a k množinám je univerzálnejší, a preto budeme radšej písať <math>\Phi_e(\emptyset)</math> ako <math>\phi_e</math>. Poznámka: Ak by sme používali iba <math>\Phi_e(B)</math> pre <math>B \leq_T \emptyset</math> (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: <math>\Phi_z(B)(x_1, x_2, \dots, x_n) \simeq \Phi_z(B)(<x_1, x_2, \dots, x_n>)</math>.

<b>Veta:</b><em>(relativizovaná s-m-n veta)</em> Nech <math>\Phi_z(B)</math> je univerzálna B-ČRF. Platí s-m-n veta: Existuje PRF <math>\bar{s_m}</math> <math>m + 1</math> premenných taká, že platí:<math>\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)</math>.

<b>Dôkaz:</b> V pôvodnej verzii pre <math>\phi_z</math> sa <math>s_{m(z, y_1, y_2, \dots, y_m)}</math> dalo predstaviť ako triviálny program, ktorý hovoril: Keď dostaneš na vstupe <math>z</math> a <math>(y_1, y_2, \dots, y_n)</math>, tak spusti <math>\varphi_z(y_1, y_2, \dots, y_m, x_1, x_2, \dots, x_n)</math>. 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 <math>\alpha</math> definovanú takto:

<math>\alpha(z,x,w)\downarrow \iff (w = <\sigma,y,t></math> & <math><\sigma,<x,y>,t> \in W_{\rho(z)})</math>

Táto ČRF <math>\alpha</math> je definovaná (konverguje), ak <math>w</math> 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 <math>\alpha</math> má index e v pôvodnej numerácii <math>\{\varphi_e\}_{e \in N}</math>. Použijeme na ňu nerelativizovanú (inú zatiaľ nemáme :) ) verziu s-m-n vety pre dve premenné: <math>\alpha(z,x,w) \simeq \varphi_{s_{2}(e,z,x)}(w) \simeq \varphi_{\beta(z,x)}(w)</math>. Definičný obor takto definovanej funkcie <math>\varphi_{\beta(z,x)}(w)</math> tvoria všetky trojice <math><\sigma,y,t></math> z pôvodného ČRFálu <math>\Phi_z</math>, ktoré "počítajú s x". Inak povedané, ak pomocou <math>W_{\beta(z,x)}</math> 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 <math>W_{z}</math>) zo vstupu <math><x,y></math> (a množiny B) spočíta t. A to je presne to, čo chceme od s-m-n vety.

ČRFál <math>\Phi_z</math>, na ktorý sme aplikovali s-m-n vetu, bol reprezentovaný regulárnou množinou trojíc <math>W_{\rho(z)}</math>. Spôsob, akým sme zostrojili množinu <math>W_{\beta(z,x)}</math> nám zaručuje, že aj ona je regulárna (platí <math>W_{\rho(\beta(z,x))} = W_{\beta(z,x)}</math>), a teda aj ona korektne definuje nový hľadaný ČRFál bez potreby použitia funkcie <math>\rho</math>.

<math>\Phi_{z}(B)(x,y) \simeq \Phi_{\beta(z,x)}(B)(y)</math>

Pomocou ČRF <math>\alpha</math> sme teda odvodili PRF <math>\beta</math>, ktorá v relativizovanej s-m-n vete hraje úlohu funkcie <math>s_m</math> z nerelativizovanej verzie.

Poznámka: s-m-n veta platí absolútne: Existuje <math>\bar{s_m}</math> také, že pre pre každé B a pre každý číselný vstup y, x platí <math>\Phi_z(B)(y, x) \simeq \Phi_{\bar{s_m}(z, y)}(B)(x)</math>. 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 (<math>A \leq_T B</math>) práve vtedy, ak A aj <math>\overline{A}</math> 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 <math>f</math>, 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 <math>K = \{x : \varphi_x(x)\downarrow\}</math> 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 <math>[\emptyset]</math>, 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 <math>[a]</math>, ktorý obsahuje množinu A.

<b>Definícia:</b> (operácia skoku/relativizovaný halting problém). Pre množinu A definujeme množinu <math>A'= \{x: \Phi_x(A)(x)\downarrow\} = \{x: x \in W_x^A\}</math>. Ide teda o podobnú definíciu akou boli definované množiny <math>K = \{x: \varphi_x(x)\downarrow\} = \{x: x \in W_x\}</math> a s ňou ekvivalentná <math>K_0 = \{<x,y>: x \in W_y\})</math>.

Množina A' sa nazýva skok (jump) množiny A.

Pôvodnú množinu <math>K = \{x: x \in W_x\}</math> môžeme pomocou operácie skoku definovať takto: <math>K = \emptyset'</math>, pretože platí: <math>\emptyset' = \{x: x \in W_x^{\emptyset}\} = \{x: x \in W_x\} = K</math>, čo vyplýva z: <math>W_x \equiv W_x^{\emptyset}</math>. Teda rekurzívne orákulum nám nepomôže a množina <math>W_x^{\emptyset}</math> je stále rekurzívne spočítateľná. Zápis <math>W_x \equiv W_x^{\emptyset}</math> znamená, že množina <math>W_x</math> je rekurzívne izomorfná s množinou <math>W_x^{\emptyset}</math> a vraj sa to dá jednoducho dokázať.

Skok je množinová operácia z <math>A</math> do <math>A'</math>. <math>A'</math> 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:

*<math>A^0 = A</math> (nultý skok neskáče) *<math>A^{(n+1)} = (A^{(n)})'</math>

Vraj sa takto dá postupovať aj na <math>\omega_0</math> 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, <math>\overline{A'}</math> nie je A-rekurzívne spočítateľná. (obdoba toho istého pre K a <math>\overline{K}</math>). #B je A-rekurzívne spočítateľná práve vtedy, ak platí <math>B \leq_1 A'</math>. (obdoba toho, že K je 1-úplná).

#Ak A je B-rekurzívne spočítateľná a <math>B \leq_T C</math>, tak A je C-rekurzívne spočítateľná. Pozor, nemýliť si, medzi ktorými dvoma je aký vzťah v predpokladoch! #<math>A \leq_T B \iff A' \leq_1 B'</math>

#<math>A \equiv_T B \iff A' \equiv_1 B'</math>

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.