TIN065 Prednáška 05
| Prednášky z Vyčísliteľnosti II |
| Obsah |
|---|
Na minulých prednáškach sme si vysvetlili, čo je to skok, ďalej sme si povedali, že operácia skoku je vlastne iba relativizovaný halting problém, a že A' je najzložitejšia rekurzívne spočítateľná množina vzhľadom k A (tak, ako K bola k $ \emptyset $).
Ďalej sme si povedali niečo o vlastnostiach skoku, z ktorých asi najdôležitejšia bola tá, že pre dve množiny, A a B, také, že A vieme T-previesť na B, ich skoky A' a B' sú na seba 1-prevoditeľné a späť ($ A \leq_T B \iff A' \leq_1 B' $). Z toho samozrejme vyplýva $ A \equiv_T B \iff A' \equiv_1 B' $ a to nám hovorí, že skoky sú dobre definované na T-stupňoch a dokonca veľmi silne - skok T-stupňa je 1-stupeň. Vieme teda definovať skok T-stupňa a ten aj iterovať.
A ešte o skokoch vieme, že sú uniformné: $ (\exists z_0)(\forall A)(A'=W_{z_0}^A) $.
Limitná vyčísliteľnosť
Už vieme, že najjednoduchšie sú rekurzívne množiny. Existuje ich charakteristická funkcia, ktorá stále konverguje a odpovie, či prvok padne do množiny alebo nie.
Potom máme 1-rekurzívne spočítateľné množiny (klasické RSM). Pre takéto množiny máme funkciu, ktorá nemusí stále konvergovať, ale platí o nej, že ak skonverguje, tak o prvku, ktorý sme jej dali na vstupe rozhodne, či padol do množiny alebo nie. V nultom kroku žiaden prvok v množine nie je. A v ďalších krokoch môže prvok padnúť do množiny. Podstatné je, že ak po niekoľkých krokoch funkcia skonverguje a odpovie, že v množine prvok je, tak už pre žiadny iný, väčší počet krokov toto svoje rozhodnutie nikdy nemôže zmeniť. To znamená, že pre každé $ x $ sa môže nepadnutie na padnutie zmeniť maximálne raz.
Podobne ako máme 1-rekurzívne spočítateľné množiny, máme aj 2-rekurzívne spočítateľné množiny. Opäť všetky prvky začínajú mimo množiny. V každom kroku môžu buď padnuť dnu alebo, ak už dnu sú, tak môžu z množiny vypadnúť. Ale keď pridávame počet krokov, pre každé $ x $ môžu byť tieto zmeny najviac dve.
A prejdeme k limitnej vyčísliteľnosti. Množina A sa nazýva limitne vyčísliteľná ak tých zmien je pre každý prvok iba konečne veľa (ale nedáme si žiaden odhad, ani globálny, ani pre jednotlivé prvky). A teraz formálne. A je limitne vyčísliteľná, ak existuje ORF $ f $ taká, že pre každé $ x $ platí: $ C_A(x) = \lim_{s \to \infty} f(x, s) $, kde $ s $ je počet krokov. Limita vlastne hovorí, že stav pre každé $ x $ sa môže zmeniť iba konečne veľa krát.
Menej všeobecná veta
Toto je špeciálny prípad tvrdenia, ktoré bude neskôr v tejto prednáške tiež dokázané.
Znenie: $ A\leq_T \emptyset' $ práve vtedy, ak $ A $ je limitne vyčísliteľná.
$ A $ je množina, takže $ C_A $ je totálna. To znamená, že $ C_A $ musí byť rekurzívna v $ \emptyset' $. Teda $ C_A $ je $ \emptyset' $-ORF.
Dôkaz: Najprv $ \Rightarrow $. Máme množinu $ A $, ktorá je turingovsky prevoditeľná na $ \emptyset' $. To znamená, že existuje z také, že $ C_A(x)=\Phi_z(\emptyset')(x) $. To je nemilé, pretože o $ \emptyset' $, čo je vlastne známa množina $ K $, nevieme povedať, či tam niečo padne alebo nie - je to známy halting problém. $ \emptyset' $ je ale rekurzívne spočítateľná množina, a teda ju môžeme efektívne generovať. "$ \Phi_z(\emptyset')(x) $ je "ošklivé", ale vieme to aproximovať."
$ \emptyset' $ je rekurzívne spočítateľná, takže platí: $ \emptyset' = W_{z_0}^\emptyset $ pre nejaké $ z_0 $. Zadefinujme si $ \emptyset'_s = W_{z_0,s}^\emptyset $ ako množinu, ktorá obsahuje tú časť množiny $ \emptyset' $, ktorú za $ s $ krokov vygenerujeme. A ďalej si zadefinujme funkciu $ f(x, s) $ takto:
$ f(x,s) = \begin{cases} \Phi_{z,s}(\emptyset'_s)(x),&\mbox{ak } \Phi_{z,s}(\emptyset'_s)(x)\downarrow\\ s+1&\mbox{inak}\\ \end{cases} $
Je vidieť, že $ f $ je ORF (zastaví stále). Už nám len treba ukázať, že je to tá pravá ORF pre našu množinu $ A $. Inak povedané, potrebujeme ukázať, že platí: $ C_A(x) = \lim_{s \to \infty} f(x, s) $.
Vieme, že $ A $ je rekurzívna vzhľadom k $ \emptyset' $. To znamená, že program pre $ C_A $ vždy zastaví: $ (\forall x)(\Phi_{z}(\emptyset')(x)\downarrow) $ a z toho vyplýva: $ (\forall x)(\exists \sigma \leq \emptyset')(C_A(x) = \Phi_{z}(\sigma)(x)) $. Ak sa totiž $ \Phi_{z}(\emptyset') $ zastaví, tak sme sa orákula $ \emptyset' $ spýtali iba konečný počet otázok, a preto nám stále stačí jeho konečná časť $ \sigma \leq \emptyset' $. $ \sigma $ je vlastne konečný reťazec núl a jednotiek, pre ktorý platí:
$ \sigma(j) = 0 \implies j \notin \emptyset' $
$ \sigma(j) = 1 \implies j \in \emptyset' $.
Tu príde niečo, čo nazveme heslom "počkaj na všetky". Tvrdíme, že ak máme $ \sigma $, tak existuje také $ s_0 $, že pre každé $ s > s_0 $ platí $ \sigma(j)=1\implies j\in \emptyset'_s $ pre $ j<|\sigma| $.
Je vidieť, že $ C_A(x)=\Phi_z(\emptyset'_s)(x) $ pre $ \forall s > s_0 $. Formálne by sa použilo nejaké obmedzenie $ \emptyset'_s \upharpoonright |\sigma| $ (jednoducho z množiny vezmeme len jej konečný úsek).
Ešte uvažujme dobu výpočtu: $ (\forall x)(\exists s_0)(\exists s_1)(C_A(x) = \Phi_{z,s_1}(\emptyset'_{s_0})(x)) $. Vezmeme $ s_2=\max(s_0, s_1) $ a máme $ (\forall x)(\exists s_2)(C_A(x) = \Phi_{z,s_2}(\emptyset'_{s_2})(x)) $.
Tým by mal byť dôkaz jedným smerom hotový. Poznámky, ktoré môžu pomôcť ho pochopiť: Dôležité je, že pre každé $ x $ nám stačí konečný kus orákula. Treba si uvedomiť, že $ \sigma $ ani $ s_0 $ sa nedá všeobecne určiť. Vieme iba, že raz sa $ f $ prestane meniť. Nevieme však kedy. Ak funkcia $ \Phi_{z, s} $ na vstupe $ x $ neskončí výpočet po s krokoch, tak aby sme tento prípad odlíšili od normálneho výsledku, tak položíme $ f(x) $ rovné $ s+1 $. Keďže vieme, že program $ \Phi_z $ raz určite zastaví, tak hodnota funkcie f v druhom prípade je nepodstatná. Nemusí tam nutne byť $ s+1 $. Limita funkcie nezávisí na konečnom počte prvkov.
Dôkaz v smere $ \Leftarrow $: Vieme, že $ (\forall x)(C_A(x) = \lim_{s \to \infty} f(x,s)) $, kde $ f $ je ORF. Z definície limity platí: $ (\forall x)(\exists s_0)(\forall s>s_0)(C_A(x) = f(x,s)) $ (obor hodnôt týchto funkcií je podmnožinou všetkých prirodzených čísel, a tam nemôžeme ísť ľubovoľne blízko - musí sa to začať rovnať). Otázka, ktorá nás zaujíma je, aké zložité je nájsť $ s_0 $. Ukážeme, že sa dá nájsť z $ \emptyset' $.
Naša otázka pre dané $ s $ je: $ (\exists j\geq 1)(f(x,s) \neq f(x, s+j)) $?. Alebo tiež: "Nastane ešte zmena?". Ak sa na to pozrieme, zistíme, že ide o rekurzívne spočítateľnú podmienku - máme existenčný kvantifikátor na všeobecne rekurzívnom predikáte. Všeobecne rekurzívny znamená napríklad všeobecne rekurzívny vzhľadom k $ \emptyset $, a to zase znamená, že tento predikát je možné 1-previesť (a teda aj T-previesť) na $ \emptyset' $. Lenže T-prevoditeľnosť na $ \emptyset' $ znamená, že tento predikát je $ \emptyset' $ rekurzívny, takže aj jeho negácia: $ (\forall j \geq 1)((f(x,s) = f(x,s+j)) $ je $ \emptyset' $ rekurzívna.
A pomocou $ \mu $, teda pomocou while cyklu, budeme minimalizovať $ s $. Takže máme akúsi $ \emptyset' $ rekurzívnu procedúru a okolo nej while cyklus. Tým sme dostali $ \emptyset'\mbox{-ČRF} $. Keďže však podľa predpokladu limita stále existuje, tak je to $ \emptyset'\mbox{-ORF} $. A touto funkciou zabezpečíme prevoditeľnosť $ A\leq_T \emptyset' $. Koniec dôkazu.
Všeobecnejšia veta
- Ak $ f $ je ORF, tak $ \lim_{s \to \infty}f(x,s)\mbox{ je } $$ \emptyset'\mbox{-ČRF} $
- Každá $ \emptyset'\mbox{-ČRF} $ je limitne vyčísliteľná, čiže ak $ \varphi $ je $ \emptyset'\mbox{-ČRF} $, tak existuje ORF $ f $, taká, že $ (\forall x)(\varphi(x) \simeq \lim_{s \to \infty} f(x,s)) $. Všimnime si, že tu už nie je rovnosť, ale podmienená rovnosť.
V druhom bode dokonca existuje funkcia $ h $ taká, že $ \Phi_z(\emptyset')(x) \simeq \lim_{s \to \infty} h(z,x,s) $.
Poznámka: Táto veta hovorí, že jeden limitný prechod odpovedá skoku. Ak máme niečo a urobíme na tom limitu, tak sme urobili skok a opačne.
Dôkaz je podobný ako v predchádzajúcej vete, akurát už nemusí $ \Phi_z(\emptyset')(x) $ vždy konvergovať.
Prvá časť sa dokazuje úplne rovnako: Použijeme minimalizáciu na $ \emptyset' $rekurzívnu pormienku $ (\forall j)(f(x,s) = f(x, s+j)) $, a teda máme $ \varphi(x) \simeq f(x, \mu_s(\dots)) $, čo je práve limita $ f $ (hodnota $ f $ v prvom takom $ s $, kde sa ďalej už $ f $ nemení), ale tá nemusí existovať, lebo podmienka na $ s $ je čiastočne rekurzívna, a teda aj limita $ f $ je čiastočne rekurzívna.
Druhá časť zasa vezme $ \varphi $, ktoré je $ \emptyset'\mbox{-ČRF} $, teda existuje pevné $ z $ také, že $ \varphi(x) \simeq \Phi_z(\emptyset')(x) $. Vyrobíme si funkciu $ g $ takto:
$ g(x,s) = \begin{cases} <\sigma, x, y>,&\mbox{ak } \Phi_{z,s}(\sigma)(x)\simeq y \land \sigma \leq \emptyset'_s\\ s+1&\mbox{inak} \end{cases} $
Už nám nestačí iba limitný výstup, ale potrebujeme stabilizovať celý výpočet, pretože by sa mohlo stať, že budeme dostávať jeden a ten istý zlý výsledok stále cez iné $ \sigma $. Správna odpoveď v takom prípade je, že funkcia $ \varphi $ diverguje, ale limita postupnosti výstupov by existovala, čo je zlé.
Potom si vytvoríme funkciu $ f $ takto:
$ f(x, s) = \begin{cases} g(x, s)_3&\mbox{ak } g(x, s) = g(x, s-1)\\ s+1&\mbox{inak} \end{cases} $
Poznámka: $ g(x, s)_3 $ je $ y $ z trojice $ <\sigma, x, y> $.
Vidíme, že $ f $ je ORF a tiež, že limita $ f $ cez $ s $ existuje práve vtedy, ak existuje limita $ g $. A $ g $ má limitu vtedy, ak sa stabilizuje trojica $ <\sigma, x, y> $, a teda $ \sigma $ je už počiatkom našej $ \emptyset' $, a ak $ \Phi_{z,s}(\sigma)(x)\simeq y $, tak limita $ f $ je rovná $ y $.
$ \lim_{s \to \infty} f(x, s) = \Phi_z(\emptyset')(x) $
Nové v tomto dôkaze je, že už nám nestačí iba stabilizácia hodnôt - mohlo by sa totiž stať, že by sme dostávali nejaký "stabilný" výsledok na rôznych $ \sigma $.
Nabudúce budeme tieto tvrdenia relativizovať a povieme si niečo o aritmetickej hierarchii.
