{{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 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\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.

<b>Dôkaz:</b> Najprv $\Rightarrow$. Máme množinu $A$, ktorá je turingovsky prevoditeľná na $\emptyset'$. To znamená, že existuje <em>z</em> 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 <em>konečný</em> 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 <em>while</em> cyklu, budeme minimalizovať $s$. Takže máme akúsi $\emptyset'$ 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\leq_T \emptyset'$. 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 $\varphi$ 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)(\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

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 11: \emptyset'\̲m̲b̲o̲x̲{-Č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.