{{TIN065 Prednášky}} 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 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.