{{TIN065 Prednášky}}
==Opakovanie==
Už vieme, že programy a teda ČRFály sa dajú očíslovať. A tiež máme regularizačnú funkciu <math>\rho</math>, ktorá z obecnej rekurzívne spočetnej 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 triviálne fakty z predchádzajúcej prednášky. Tiež vieme, čo to znamená, že A je B-rekurzívna.
Tak si ešte povieme, čo to znamená, že A je B-rekurzívne spočetná (rekurzívne spočetná vzhľadom k B). Nejde o nič iné ako o to, že A je doménou nejakej B-ČRF. Formálnejšie A je B-rekurzívne spočetná, ak <math>A=dom(\Phi_z(B))</math> pre nejaké z.
Taktiež si zadefinujeme značenie <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> a <math>W_{z, s}^B</math> je konečná množina tých y, ktoré patria do <math>W_{z}^B</math> za s 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ám orákulum pre A, tak viem zistiť, či prvok patrí do A triviálne. Pre tranzitivitu nech <math>A \leq_T B</math> a <math>B \leq_T C</math>. V tom prípade ak zisťujem, či niečo padne do A a potrebujem sa spýtať na niečo v B, tak miesto orákula pre B použijem program, ktorý počíta B z C a pýtam sa orákula pre C.
Druhé pozorovanie je podobne triviálne. Ak viem A zistiť bez orákula, tak s B-orákulom (akýmkoľvek orákulom) viem A zistiť zas (orákula sa proste nepýtam).
A tretie pozorovanie mi iba hovorí, že ak B viem zistiť (viem zistiť, či nejaký prvok tam patrí), tak nepotrebujem orákulum pre B, ale keď sa budem potrebovať spýtať na B, tak to zistím výpočtom (a preto celé A zistím výpočtom). Alebo inak: mal som program na zisťovanie A, ktorý používal funkciu orákulovu is_in_B a funkciu is_in_B nahradím programom pre B a získam program pre A bez 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 <math>A \leq_T B \land 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 sa označujú malým písmenom, pod ktorým je vlnovka (v TeXu snáď \underset{\widetilde{}}{a})) a nazývajú sa "stupne nerozhodnuteľnosti" (degrees of unsolvability). Lepším pojmom sú T-stupne, pretože pre rôzne prevoditeľnosti môžeme rovnakým spôsobom vytvoriť ekvivalenciu a príslušne triedy nazvať 1-stupne, m-stupne, tt-stupne a podobne.
Stupeň <math>[\emptyset]</math> (trieda ekvivalencie reprezentovaná prázdnou množinou) sú práve všetky rekurzívne množiny. Ak mám množinu A, tak <math>deg_T(A)=\{B:B\equiv_T A\}</math> je T-stupeň A (označoval by sa malým a s vlnkou pod).
Pomocou <math>\leq_T</math> na jednotlivých množinách môžem na triedach ekvivalencie zaviesť čiastočné usporiadanie: <math>[A] \leq [B]</math> ak <math>A \leq_T B</math> pre ľubovoľné <math>A \in [A]</math> a <math>B \in [B]</math>. Jasné je, že <math>[\emptyset] \leq [B]</math> pre každé B (z druhej vlastnosti v pozorovaní vyššie).
Mierna odbočka: Ak si vezmeme všetky množiny (no, to je trošku [[Teorie množin|problematické]], ale nevadí), tak si ich rozdelíme podľa našej ekvivalencie a zistíme, že jediná trieda, ktorú môžeme algoritmicky rozhodnúť je práve <math>[\emptyset]</math>. Všetky ostatné stupne sú nerekurzívne, takže algoritmicky nerozhodnuteľné.A preto sa tomu hovorí stupne nerozhodnuteľnosti.
==Očíslovanie a s-m-n veta==
ČRF vieme očíslovať: <math>\{\varphi_x\}</math>. My si ale môžeme zobrať tiež numeráciu <math>\{\Phi_x(\emptyset)\}</math>, čo sú ČRFály, do ktorých podhodíme rekurzívne orákulum a tie sú rekurzívne izomorfné s ČRF (teda máme preklad z čísel jedného na čísla druhého - existuje rekurzívna permutácia p taká, že <math>\varphi_x=\Phi_{p(x)}(\emptyset)</math>. <math>W_z^\emptyset</math> sú práve všetky rekurzívne množiny.
Tento prístup k funkciám a k množinám je univerzálnejší a preto budeme radšej písať <math>\Phi_x(\emptyset)</math> ako <math>\phi_x</math>. Poznámka: Ak budeme používať len <math>\Phi_x(\emptyset)</math> (teda len s rekurzívnou množinou), dostaneme zimný semester (Vyčísliteľnosť I).
Zadefinujeme si, čo je to funkcia pre viac premenných. Je to funkcia, kde pošleme kód 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>.
Veta: Nech <math>\Phi_z(B)</math> je univerzálna B-ČRF. Platí s-m-n veta: Existuje PRF <math>\bar{s_m}</math> taká, že <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>.
V pôvodnej verzii zo zimného semestra sa <math>s_{m(z, y_1, y_2, \dots, y_m)}</math> dalo predstaviť ako triviálny program, ktorý hovoril: Keď dostaneš <math>(x_1, x_2, \dots, x_n)</math>, tak pusti <math>\varphi_z(y_1, y_2, \dots, y_m, x_1, x_2, \dots, x_n)</math>. A v tomto prípade tým, že tam pridáme B sa nič nemení.
{{TODO|Toto vyzerá ako klasický príklad dôkazu úporným tvrdením. Chcelo by to lepšie.}}
Ukážeme si iba pre <math>\bar{\sigma_2}</math>. Pre iné si predstavíme, že x a y sú vektory.
Vezmeme si <math>W=\{<\sigma, x, t>: <\sigma, <y, x>, t> \in W_{\rho(z)}\}</math>.
(tu sa hovorilo, že by sa presnejšie vzala ČRF <math>\alpha</math> taká, že <math>\alpha(z, y, x)\downarrow \iff w = <\sigma, x, t></math>také, že <math><\sigma, <y, x>, t>\in W_{\rho(z)}</math>, <math>\alpha \simeq \varphi_{s_2(e, z, y)}(w)</math> a <math>\bar{s_2}(z, y) = s_2(e, z, y)</math>). Neviem, nerozumiem tomu príliš.
Máme teda množinu W. Tá nám dáva trojice také, že kúsok orákula <math>\sigma</math> vydá na x výsledok t ak to isté orákulum na <y, x> dá tiež t. (My chceme, aby <math>\Phi_z(B)(y, x) \simeq \Phi_{\bar{s}(z, y)}(B)(x)</math>). A máme všetky výpočty, ktoré so <math>\sigma</math> z x dajú t ak na <y, x> tiež dajú t a to je to, čo chceme, ale s dôležitou poznámkou: <math>W_{\bar{\sigma_2}(z, y)}</math> je regulárna (naša regularizačná funkcia <math>\rho</math> ju nezmení:<math>W_{\rho(\bar{\sigma_2}(z, y))} = W_{\bar{\sigma_2}(z, y)}</math>). A to je zrejmé, lebo Vyberáme z <math>W_{\rho(z)}</math>. Naša <math>\bar s</math> spĺňa to, že výsledok je ČRFál - netreba na to púšťať regularizáciu.
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_{s_n(z, y)}(B)(y)</math>. Tiež sa hovorí, že platí uniformne alebo "stejnoměrně" (inšpirácia analýzou je snáď zrejmá.
Zimný semester 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 Postovú vetu: A je B-rekurzívna (<math>A \leq_T B</math>) práve vtedy, keď A aj doplnok A sú B-rekurzívne spočetné. Alebo vieme tiež relativizovať generovanie: A je B-rekurzívne spočatná práve vtedy ak existuje prostá (asi aj úseková) B-ČRF, ktorá generuje A. A teraz prichádzame k relativizácii halting problému (operácii skoku).
==Operácia skoku==
Už vieme, že obyčajný halting problém len tak bez orákula nevieme vyriešiť. Nad <math>[\emptyset]</math> existuje množina K, ktorá predstavuje halting problém. A my budeme nad hocijakou vedieť vytvoriť <math>K_A</math>.
Definícia (operácia skoku/relativizovaný halting problém). Definujme si pre množinu A množinu <math>A'=\{x:\Phi_x(A)(x)\downarrow\}=\{x:x\in W_x^A\}</math>. Pre pripomenutie, pôvodne sme mali <math>K=\{x:\varphi_x(x)\downarrow\}=\{x\in W_x\}</math> (a s ňou ekvivalentnú <math>K_0=\{<x,y>:x\in W_y\})</math>.
Množina A' sa volá skok (jump) množiny A.
Ak si spomenieme na K, tak to bolo <math>\{x\in W_x\}</math>. Ak sa pozrieme na <math>\emptyset'</math>, tak zbadáme, že to je <math>\emptyset'=\{x\in W_x^{\emptyset}\}</math> a to je rekurzívne spočetná množina o ktorej sa vraj ľahko ukáže, že je rekurzívne izomorfná s K.
Skok je množinová operácia z A do A'. A' je relativizovaný halting problém. A môžeme si ho naiterovať.
Definícia: <math>A^0 = A</math> (nultý skok neskáče) a <math>A^(n+1) = (A^n)'</math>. Ono by sa to vraj dalo dostať aj na omegu a ďalej - ale to by chcelo vedieť [[Teorie množin|Temno]].
A na koniec prednášky už len veta.
#A' ja A-rekurzívne spočetná. (obdoba toho, že K je rekurzívne spočetná)
#A' nie je A-rekurzívna, doplnok A nie je A-rekurzívne spočetný. (obdoba toho istého pre K a doplnok K).
#B je A-rekurzívne spočetná práve vtedy, keď <math>B\leq_1 A'</math>. (obdoba toho, že K je 1-úplná).
#Ak A je B-rekurzívne spočetná a <math>B\leq_T C</math>, tak A je C-rekurzívne spočetná. Pozor, nepomý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 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.
