{{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 $\varnothing$).

Ď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{\le }_{T}B⟺A^{\prime }{\le }_1{B}^{\prime }$). Z toho samozrejme vyplýva $A{\equiv }_{T}B⟺A^{\prime }{\equiv }_1{B}^{\prime }$ 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^{\prime }=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 wen:Limiting%20recursive 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é.

<b>Znenie:</b> $A{\le }_T{\varnothing }^{\prime }$ 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 ${\varnothing }^{\prime }$. Teda $C_A$ je ${\varnothing }^{\prime }$-ORF.

<b>Dôkaz:</b> Najprv $\Rightarrow$. Máme množinu $A$, ktorá je turingovsky prevoditeľná na ${\varnothing }^{\prime }$. To znamená, že existuje <em>z</em> také, že $C_A(x)={\Phi }_z({\varnothing }^{\prime })(x)$. To je nemilé, pretože o ${\varnothing }^{\prime }$, čo je vlastne známa množina $K$, nevieme povedať, či tam niečo padne alebo nie - je to známy halting problém. ${\varnothing }^{\prime }$ je ale rekurzívne spočítateľná množina, a teda ju môžeme efektívne generovať. "${\Phi }_z({\varnothing }^{\prime })(x)$ je "ošklivé", ale vieme to aproximovať."

${\varnothing }^{\prime }$ je rekurzívne spočítateľná, takže platí: ${\varnothing }^{\prime }=W_{z_0}^{\varnothing }$ pre nejaké $z_0$. Zadefinujme si ${\varnothing }_s^{\prime }=W_{z_0,s}^{\varnothing }$ ako množinu, ktorá obsahuje tú časť množiny ${\varnothing }^{\prime }$, 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 ${\varnothing }^{\prime }$. To znamená, že program pre $C_A$ vždy zastaví: $(\forall x)({\Phi }_z({\varnothing }^{\prime })(x)\downarrow )$ a z toho vyplýva: $(\forall x)(\exists \sigma \le {\varnothing }^{\prime })(C_A(x)={\Phi }_z(\sigma )(x))$. Ak sa totiž ${\Phi }_z({\varnothing }^{\prime })$ zastaví, tak sme sa orákula ${\varnothing }^{\prime }$ spýtali iba konečný počet otázok, a preto nám stále stačí jeho konečná časť $\sigma \le {\varnothing }^{\prime }$. $\sigma$ je vlastne <em>konečný</em> reťazec núl a jednotiek, pre ktorý platí:

$\sigma (j)=0⟹j\notin {\varnothing }^{\prime }$

$\sigma (j)=1⟹j\in {\varnothing }^{\prime }$.

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⟹j\in {\varnothing }_s^{\prime }$ pre $j<|\sigma |$.

Je vidieť, že $C_A(x)={\Phi }_z({\varnothing }_s^{\prime })(x)$ pre $\forall s>s_0$. Formálne by sa použilo nejaké obmedzenie ${\varnothing }_s^{\prime }\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}({\varnothing }_{s_0}^{\prime })(x))$. Vezmeme $s_2=\max (s_0,s_1)$ a máme $(\forall x)(\exists s_2)(C_A(x)={\Phi }_{z,s_2}({\varnothing }_{s_2}^{\prime })(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 ${\varnothing }^{\prime }$.

Naša otázka pre dané $s$ je: $(\exists j\ge 1)(f(x,s)\ne 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 $\varnothing$, a to zase znamená, že tento predikát je možné 1-previesť (a teda aj T-previesť) na ${\varnothing }^{\prime }$. Lenže T-prevoditeľnosť na ${\varnothing }^{\prime }$ znamená, že tento predikát je ${\varnothing }^{\prime }$ rekurzívny, takže aj jeho negácia: $(\forall j\ge 1)((f(x,s)=f(x,s+j))$ je ${\varnothing }^{\prime }$ rekurzívna.

A pomocou $\mu$, teda pomocou <em>while</em> cyklu, budeme minimalizovať $s$. Takže máme akúsi ${\varnothing }^{\prime }$ rekurzívnu procedúru a okolo nej <em>while</em> cyklus. Tým sme dostali

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 11: \emptyset'\̲m̲b̲o̲x̲{-ČRF}

. Keďže však podľa predpokladu limita stále existuje, tak je to

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 11: \emptyset'\̲m̲b̲o̲x̲{-ORF}

. A touto funkciou zabezpečíme prevoditeľnosť $A{\le }_T{\varnothing }^{\prime }$. Koniec dôkazu.

Všeobecnejšia veta

#Ak $f$ je ORF, tak

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 26: …o \infty}f(x,s)\̲m̲b̲o̲x̲{ je }

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 11: \emptyset'\̲m̲b̲o̲x̲{-ČRF}

#Každá

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 11: \emptyset'\̲m̲b̲o̲x̲{-ČRF}

je <em>limitne vyčísliteľná</em>, čiže ak $\phi$ je

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 11: \emptyset'\̲m̲b̲o̲x̲{-ČRF}

, tak existuje ORF $f$, taká, že $(\forall x)(\phi (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({\varnothing }^{\prime })(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({\varnothing }^{\prime })(x)$ vždy konvergovať.

Prvá časť sa dokazuje úplne rovnako: Použijeme minimalizáciu na ${\varnothing }^{\prime }$rekurzívnu pormienku $(\forall j)(f(x,s)=f(x,s+j))$, a teda máme $\phi (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 $\phi$, ktoré je

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 11: \emptyset'\̲m̲b̲o̲x̲{-ČRF}

, teda existuje pevné $z$ také, že $\phi (x)\simeq {\Phi }_z({\varnothing }^{\prime })(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 $\phi$ 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 ${\varnothing }^{\prime }$, 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.