TIN065 Prednáška 05

Prednášky z Vyčísliteľnosti II
Obsah
Prehľad Prvá prednáška Druhá prednáška Tretia prednáška Štvrtá prednáška Piata prednáška Šiesta prednáška Siedma prednáška Ôsma prednáška Deviata prednáška Desiata prednáška Jedenásta prednáška Dvanásta prednáška Zhrnutie na skúšku

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

1. Ak $ f $ je ORF, tak $ \lim_{s \to \infty}f(x,s)\mbox{ je } $$ \emptyset'\mbox{-ČRF} $
2. 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.