TIN065 Prednáška 03

Z ωικι.matfyz.cz
Verze z 9. 3. 2009, 18:32, kterou vytvořil 195.113.20.80 (diskuse) (preklep)

Přejít na: navigace, hledání

Opakovanie

Už vieme, že programy a teda ČRFály sa dajú očíslovať. A tiež máme regularizačnú funkciu $ \rho $, ktorá z obecnej rekurzívne spočetnej množiny vyrobí ČRFál a to dokonca tak, že $ W_{\rho(z)}\subset W_z $ a tiež $ \Phi_z=W_{\rho(z)} $. 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 $ A=dom(\Phi_z(B)) $ pre nejaké z. Taktiež si zadefinujeme značenie $ W_{z}^B $ a $ W_{z, s}^B $. $ W_{z}^B = dom(\Phi_z(B)) = \{y:\Phi_z(B)(y)\downarrow\} $ a $ W_{z, s}^B $ je konečná množina tých y, ktoré patria do $ W_{z}^B $ za 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ám orákulum pre A, tak viem zistiť, či prvok patrí do A triviálne. Pre tranzitivitu nech $ A \leq_T B $ a $ B \leq_T C $. 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 $ \equiv_T $ a T-stupne

Keď mám $ \leq_T $, tak je jednoduché zadefinovať reláciu $ \equiv_T $.

$ A \equiv_T B $ ak $ A \leq_T B \land 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 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ň $ [\emptyset] $ (trieda ekvivalencie reprezentovaná prázdnou množinou) sú práve všetky rekurzívne množiny. Ak mám množinu A, tak $ deg_T(A)=\{B:B\equiv_T A\} $ je T-stupeň A (označoval by sa malým a s vlnkou pod).

Pomocou $ \leq_T $ na jednotlivých množinách môžem na triedach ekvivalencie zaviesť čiastočné usporiadanie: $ [A] \leq [B] $ ak $ A \leq_T B $ pre ľubovoľné $ A \in [A] $ a $ B \in [B] $. Jasné je, že $ [\emptyset] \leq [B] $ 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 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 $ [\emptyset] $. 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ť: $ \{\varphi_x\} $. My si ale môžeme zobrať tiež numeráciu $ \{\Phi_x(\emptyset)\} $,l č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 $ \varphi_x=\Phi_{p(x)}(\emptyset) $. $ W_z^\emptyset $ 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ť $ \Phi_x(\emptyset) $ ako $ \Phi_x(\emptyset) $. Poznámka: Ak budeme používať len $ \Phi_x(\emptyset) $ (teda len s rekurzívnou množinou), dostaneme zimný semester (Vyčísliteľnosť I).

Zadefinujeme si, čo je to funkcia prre viac premenných. je to funkcia, kde pošleme kód 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: Nech $ \Phi_z(B) $ je univerzálna B-ČRF. Platí s-m-n veta: Existuje PRF $ \bar{s_m} $ taká, že $ \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)( $.

V pôvodnej verzii zo zimného semestra sa $ s_{m(z, y_1, y_2, \dots, y_m)} $ dalo predstaviť ako triviálny program, ktorý hovoril: Keď dostaneš $ (x_1, x_2, \dots, x_n) $, tak pusti $ \varphi_z(y_1, y_2, \dots, y_m, x_1, x_2, \dots, x_n) $. A v tomto prípade tým, že tam pridáme B sa nič nemení.

Tato část je neúplná a potřebuje rozšířit. Toto vyzerá ako klasický príklad dôkazu úporným tvrdením. Chcelo by to lepšie.

Ukážeme si iba pre $ \bar{\sigma_2} $. Pre iné si predstavíme, že x a y sú vektory.

Vezmeme si $ W=\{<\sigma, x, t>: <\sigma, <y, x>, t> \in W_{\rho(z)}\} $.

(tu sa hovorilo, že by sa presnejšie vzala ČRF $ \alpha $ taká, že $ \alpha(z, y, x)\downarrow \iff w = <\sigma, x, t> $také, že $ <\sigma, <y, x>, t>\in W_{\rho(z)} $, $ \alpha \simeq \varphi_{s_2(e, z, y)}(w) $ a $ \bar{s_2}(z, y) = s_2(e, z, y) $). Neviem, nerozumiem tomu príliš.

Máme teda množinu W. Tá nám dáva trojice také, že kúsok orákula $ \sigma $ vydá na x výsledok t ak to isté orákulum na <y, x> dá tiež t. (My chceme, aby $ \Phi_z(B)(y, x) \simeq \Phi_{\bar{s}(z, y)}(B)(x) $). A máme všetky výpočty, ktoré so $ \sigma $ z x dajú t ak na <y, x> tiež dajú t a to je to, čo chceme, ale s dôležitou poznámkou: $ W_{\bar{\sigma_2}(z, y)} $ je regulárna (naša regularizačná funkcia $ \rho $ ju nezmení: W_{\rho(\bar{\sigma_2}(z, y))} = W_{\bar{\sigma_2}(z, y)}). A to je zrejmé, lebo Vyberáme z $ W_{\rho(z)} $. Naša $ \bar s $ 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 $ \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_{s_n(z, y)}(B)(y) $. 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 ($ A \leq_T B $) 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 $ [\emptyset] $ existuje množina K, ktorá predstavuje halting problém. A my budeme nad hocijakou vedieť vytvoriť $ K_A $.

Definícia (operácia skoku/relativizovaný halting problém). Definujme si pre množinu A množinu $ A'=\{x:\Phi_x(A)(x)\downarrow\}=\{x:x\in W_x^A\} $. Pre pripomenutie, pôvodne sme mali $ K=\{x:\varphi_x(x)\downarrow\}=\{x\in W_x\} $ (a s ňou ekvivalentnú $ K_0=\{<x,y>:x\in W_y\}) $.

Množina A' sa volá skok (jump) množiny A.

Ak si spomenieme na K, tak to bolo $ \{x\in W_x\} $. Ak sa pozrieme na $ \emptyset' $, tak zbadáme, že to je $ \emptyset'=\{x\in W_x^{\emptyset}\} $ 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: $ A^0 = A $ (nultý skok neskáče) a $ A^(n+1) = (A^n)' $. Ono by sa to vraj dalo dostať aj na omegu a ďalej - ale to by chcelo vedieť Temno.

A na koniec prednášky už len veta.

  1. A' ja A-rekurzívne spočetná. (obdoba toho, že K je rekurzívne spočetná)
  2. A' nie je A-rekurzívna, doplnok A nie je A-rekurzívne spočetný. (obdoba toho istého pre K a doplnok K).
  3. B je A-rekurzívne spočetná práve vtedy, keď $ B\leq_1 A' $. (obdoba toho, že K je 1-úplná).
  4. Ak A je B-rekurzívne spočetná a $ B\leq_T C $, tak A je C-rekurzívne spočetná. Pozor, nepomý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 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.