TIN065 Prednáška 02
| Prednášky z Vyčísliteľnosti II |
| Obsah |
|---|
Na začiatok trochu opakovania z minulej prednášky. Celý čas formalizujeme pojem, že jedna množina je jednoduchšia ako druhá a vyrábame si tu relatívnu vyčísliteľnosť z efektívnej vyčísliteľnosti. V efektívnej vyčísliteľnosti sme zisťovali, či zadané prvky sú prvkami nejakých množín (a podľa toho, či sme to vedeli zistiť sme mali rekurzívne, prípadne rekurzívne spočítateľné množiny). Teraz zisťujeme, či je niečo prvkom množiny A ak poznáme množinu B. Mali sme nejaké prevoditeľnosti ($ \leq_1 $, $ \leq_m $, $ \leq_{tt} $, $ \leq_{wtt} $, $ \leq_T $) a z nich je najvšeobecnejšia tá turingovská ($ \leq_T $). Mali sme model s Pascalom rozšíreným o funkciu is_in_B, mali sme model Turingovho stroja s orákulovou páskou a jeho výpočtový strom. Vieme, že orákulí je nespočítateľne mnoho, keďže množín B môže byť nespočítateľne mnoho. A tiež sme mali rovnosť $ P(B, x) = y $ práve vtedy, keď $ (\exists u, v, s)(<x, y, u, v> \in W) $ za s krokov a $ D_u \subseteq B $ a súčasne $ D_v \subseteq \overline{B} $. Čo je vlastne to $ W $? Je to množina konečných vetiev v strome, je rekurzívne spočítateľná, a celý ten zápis nám hovorí, že existuje konečná vetva, kde výpočet (prechod stromom) skončí.
Ďalej vieme, že množinu $ B $ stotožňujeme s jej charakteristickou funkciou $ C_B $ a tiež vieme, čo to znamená, že jeden binárny string je prefixom druhého. Naviac vieme, čo pre binárny string $ \sigma $ znamená $ \sigma \leq B $. Tento zápis jednoducho hovorí, že $ \sigma $ je začiatkom $ C_B $.
Triviálne pozorovanie hovorí, že to, že sa pýtame na množiny $ D_u $ a $ D_v $ počas výpočtu (vlastne ich vytvárame až počas výpočtu práve tým pýtaním sa) je prakticky rovnaké, ako keby sme mali k dispozícii konečnú časť $ C_B $, a to takú, ktorá obsahuje všetky prvky od začiatku (od nuly) až po $ D_u \cup D_v $. Pritom tie, ktoré nepotrebujeme, budeme jednoducho ignorovať.
Obsah
Čiastočne rekurzívny funkcionál
Definujeme si čiastočne rekurzívny funkcionál (skrátene ČRFál) $ \Phi $ ako rekurzívne spočítateľnú množinu trojíc $ <\sigma, x, y> $ takých, že ak $ <\sigma, x, y> \in \Phi $ & $ <\acute{\sigma}, x, \acute{y}> \in \Phi $ & $ \sigma \leq \acute{\sigma} $, tak potom $ y = \acute{y} $. $ \Phi $ si môžeme predstaviť ako program, ktorý pre vstup $ x $ vráti $ y $, ak pozná počiatočný string $ \sigma $ množiny $ B $ (teda platí $ \sigma \leq B $). Podmienka v definícii (podmienka kozistencie výpočtu) hovorí, že ak je možné zo vstupu $ x $ s pomocou $ \sigma $ vypočítať $ y $, tak so znalosťou väčšej časti $ B $ musí byť vypočítané $ y $ rovnaké.
$ \Phi $ je teda rekurzívne spočítateľná množina. A pomocou nej si vieme vytvoriť zobrazenie.
Ak $ \Phi $ je ČRFál, tak definujeme
- $ \Phi(\sigma)(x)\simeq y $ ak platí $ <\sigma, x, y> \in \Phi $
- $ \Phi(\tau)(x)\simeq y $ ak platí $ <\sigma, x, y> \in \Phi $ pre nejaké $ \sigma \leq \tau $
- $ \Phi(B)(x)\simeq y $ ak platí $ <\sigma, x, y> \in \Phi $ pre nejaké $ \sigma \leq B $.
Prečo je $ \Phi $ funkcionál a nie funkcia? Pretože ho aplikujeme najprv na množinový vstup $ (B) $ a tým z toho dostaneme funkciu, ktorú už potom môžeme aplikovať na klasický vstup $ (x) $. Preto sa aj píše $ \Phi(B)(x) $ namiesto $ \Phi(B, x) $.
Nejaké poznámky
- Ak $ \Phi $ je ČRFál, tak $ \Phi(B) $ je vždy funkcia, ktorá je definovaná konzistentne so všetkými $ \Phi(\sigma) $ pre všetky $ \sigma \leq B $. Neznamená to, že $ \Phi(B) $ musí byť nutne definovaná všade. Ide len o podmienku konzistencie.
- $ \Phi(B) $ je určite B-efektívne vyčísliteľná (budeme si generovať trojice $ <\sigma, x, y> $ a pýtať sa, či $ \sigma $ je prefixom $ B $).
$ \Phi $ je naša formalizácia pojmu B-efektívne vyčísliteľné. Na $ \Phi $ sa často pozerá práve ako na zobrazenie a neformálne ako na program v B-Pascale.
Turingovská prevoditeľnosť
Definícia: $ A \leq_T B $ (čítame to: množina A je turingovsky prevoditeľná na množinu B, A je rekurzívne relatívna k B alebo A je B-rekurzívna), ak existuje ČRFál $ \Phi $ taký, že $ A=\Phi(B) $. Formálne správne je to takto: $ (\forall x)(C_A(x) = \Phi(B)(x)) $.
B-ČRF potom znamená práve $ \Phi(B) $ pre rôzne ČRFál-y $ \Phi $. Induktívnym spôsobom by to šlo samozrejme tiež (a dostali by sme aj B-PRF), ale kto by to robil?
Celé to hranie sa robíme kvôli relativizácii. Skúsime vyrobiť vety a tvrdenia, ktoré sme mali pri obyčanej efektívnej vyčísliteľnosti, aj pre B-vyčísliteľnosť.
B-rekurzívna spočítateľnosť
Definícia: Množina A sa nazýva B-rekurzívne spočítateľná (alebo rekurzívne spočítateľná v B), ak platí, že množina $ A $ je doménou funkcie $ \Phi(B) $ pre nejaký ČRFál $ \Phi $ a množinu $ B $.
Relativizácia Postovej vety
Množina $ A $ je B-rekurzívna práve vtedy, ak $ A $ aj $ \overline{A} $ sú B-rekurzívne spočítateľné. Dôkaz by bol rovnaký ako pri obyčajnej, nerelativizovanej Postovej vete.
Zatiaľ naša relativizácia vyzerá byť bezproblémová a orákulum (vlastne množinu B) ani nepotrebujeme. To sa však čoskoro zmení. Našim lokálnym cieľom nech zatiaľ je s-m-n veta.
Relativizovaná nummerácia
Potrebujeme nejakú numeráciu zovšeobecnených programov. Inými slovami, chceme očíslovať všetky možné $ \Phi $. Môžeme to urobiť tak, že si vezmeme náš B-Pascal a keďže každý program je konečný objekt, tak každému môžeme priradiť číslo. Týmto si očíslujeme všetky programy v B-Pascale a $ \Phi_e $ môžeme chápať ako čiastočne rekurzívny funkcionál definovaný e-tým programom. To je jeden spôsob, ale je možné robiť to aj inak.
Už z predchádzajúceho semestra máme $ \varphi_e $ ako očíslované obyčajné ČRF a $ W_e $ ako očíslované rekurzívne spočítateľné množiny, kde $ W_e = dom(\varphi_e) $. Môžeme teda využiť to, že $ \Phi $ je tiež iba rekurzívne spočítateľná množina a pokúsiť sa očíslovať ju pomocou numerácie obyčajných ČRF. To však narazí na problém, a to taký, že aj keď každý ČRFál je rekurzívne spočítateľná množina, tak nie každá rekurzívne spočítateľná množina je ČRFál. To je trošku nepríjemné, ale túto závadu ľahko odstránime. Postupovať budeme zhruba tak, že každú $ W_e $ hodíme do "strojčeka", ktorý z nej oreže tie časti, ktoré "robia problémy".
Regularizácia
Lemma: Existuje regularizačná funkcia, teda primitívne rekurzívna funkcia $ \rho $ taká, že pre každé e je $ W_{\rho(e)} $ ČRFál, teda je splnená podmienka konzistencie. Naviac, ak je $ W_e $ ČRFál, tak $ W_{\rho(e)}=W_e $, teda rekurzívne spočítateľné množiny, ktoré už sú ČRFály sa regularizačnou funkciou nezmenia.
Dôkaz: Idea dôkazu je jednoduchá. Vezmeme si program, ktorý generuje $ W_e $. Začneme s prázdnou množinou a stále, keď sa vygeneruje nová usporiadaná trojica $ <\sigma, x, y> $, tak sa spýtame na konzistentnosť. Ak je nová usporiadaná trojica konzistentná s doteraz vygenerovanou množinou, tak tam túto trojicu jednoducho pridáme. Ak nie je, tak ju zahodíme. A týmto spôsobom efektívne vygenerujeme celé $ W_{\rho(e)} $.
Všimnime si, čo sa však môže stať. Ak vygenerujeme dve usporiadané trojice: $ <\sigma_1, x, y_1> $ a $ <\sigma_2, x, y_2> $, kde $ y_1 \neq y_2 $ a zároveň $ (\sigma_1 \leq \sigma_2 $ alebo $ \sigma_2 \leq \sigma_1) $, tak v takom prípade záleží na poradí, v akom budeme do $ W_{\rho(e)} $ tieto usporiadané trojice pridávať. Pridaním jednej z nich ako prvej totiž určíme, že na vstupe $ x $ s vhodnou časťou orákula je správnym výstupom buď $ y_1 $ alebo $ y_2 $. A tým teda obmedzíme, ktoré ďalej vygenerované usporiadané trojice budú konzistentné a ktoré nie. To znamená, že obsah výslednej množiny $ W_{\rho(e)} $ závisí aj na poradí generovania usporiadaných trojíc z $ W_e $. To nás však netrápi, pretože si môžeme poradie generovaných usporiadaných trojíc dopredu nejako pevne definovať a používať stále to isté.
Zhrnutie
Pomocou regularizačnej funkcie teda získame numeráciu všetkých ČRFálov, pre ktorú platí: $ \Phi_e = W_{\rho(e)} $. Podrobnejšie:
$ \Phi_e(B)(x) \simeq y \Leftrightarrow (\exists \sigma)(<\sigma, x, y>\in W_{\rho(e)} $ & $ \sigma \leq B) $
To vlastne hovorí, že e-tý program s množinou B ako orákulom dá na vstupe x výsledok y práve vtedy, ak existuje konečná vetva v našom výpočtovom strome.
Ešte sme si spomenuli, čo to je počítanie v krokoch. Intuitívne je jasné, čo to je s krokov výpočtu. Aby to bolo formálne, tak napíšeme
$ \Phi_{e,s}(B)(x) \simeq y \Leftrightarrow (\exists \sigma)(<\sigma, x, y>\in W_{\rho(e),s} $ & $ \sigma \leq B $ & $ |\sigma| \leq s) $, kde $ W_{x,s} = \{y, (\exists j \leq s)(T_1(x, y, j))\} $, čiže Turingov stroj s kódom x skončí na vstupe y za maximálne s krokov.
Triviálne poznámky na koniec druhej prednášky
- $ \Phi_{e,s}(\sigma)(x)\downarrow $ je rekurzívne (vieme to triviálne zistiť tým, že to spustíme).
- $ \Phi_{e,s}(\sigma)(x) \simeq y $ je rekurzíve v e, s, $ \sigma $, x, y.
- $ \Phi_{e}(B)(x)\downarrow $ je B-rekurzívne spočítateľné.
- $ \Phi_{e}(B)(x)\simeq y $ je B-rekurzívne spočítateľné.
- $ \Phi_{e,s}(B)(x)\simeq y $ je B-rekurzívne, nie iba rekurzívne
V poslednom bode nevieme vôbec zhora obmedziť, ako veľmi ďaleké prvky z B budeme potrebovať. Práve preto si nevystačíme s nerelativizovanou ORF, ale potrebujeme sa pýtať orákula B, takže potrebujeme B-ORF.
Na budúcej prednáške bude s-m-n veta a relativizovanie halting problému.
