{{TIN065 Prednášky}}

Opakovanie

Už vieme, že relativizované programy, teda ČRFály, sa dajú očíslovať. Máme tiež regularizačnú funkciu $\rho$, ktorá zo všeobecnej rekurzívne spočítateľnej množiny vyrobí ČRFál, a to dokonca tak, že $W_{\rho(z)} \subseteq W_z$ a tiež $\Phi_z = W_{\rho(z)}$. A ešte sme si zopakovali, čo to znamená, že množina A je B-rekurzívna.

Teraz si ešte povieme, čo to znamená, že A je B-rekurzívne spočítateľná množina (rekurzívne spočítateľná vzhľadom k B). Nejde o nič iné ako o to, že množina A je doménou nejakej B-ČRF. Formálnejšie: množina A je B-rekurzívne spočítateľná, ak $A = dom(\Phi_z(B))$ pre nejaké z.

Taktiež si zavedieme označenia: $W_{z}^B$ a $W_{z, s}^B$. $W_z^B = dom(\Phi_z(B)) = \{y: \Phi_z(B)(y)\downarrow\}$ teda označuje definičný obor funkcie $\Phi_z(B)$. Podobne $W_{z, s}^B$ označuje konečnú množinu tých $y$, o ktorých je možné rozhodnúť, či sú prvkami $W_{z}^B$, za nanajvýš $s$ krokov.

O vzťahu $\leq_T$

Pozorovania:

#Vzťah $\leq_T$ je reflexívny a tranzitívny. #Ak A je rekurzívna množina, tak $A\leq_T B$ pre každé B.

#Ak $A \leq_T B$ a B je rekurzívna, tak aj A je rekurzívna. Pozorovania sú viac menej zrejmé. Keďže pri $\leq_T$ sa jedná o programy, tak budeme jednotlivé vlastnosti ukazovať pomocou programov (čo je iste pochopiteľnejšie, ako formálne pomocou trojíc $<\sigma, x, y>$).

To, že je $\leq_T$ reflexívne ($A \leq_T A$) je jasné, lebo ak máme množinu A ako orákulum, tak vieme triviálne zistiť, či je niečo prvkom množiny A - stačí sa raz spýtať orákula. Pre dôkaz tranzitívnosti nech $A \leq_T B$ a $B \leq_T C$. Chceme zistiť, či $A \leq_T C$. Teda pre dané $x$ chceme program, ktorý zistí, či $x \in A$, pričom má k dispozícii iba funkciu is_in_C, teda iba orákulum C. Vieme, že ak by sme mohli použiť funkciu is_in_B, teda orákulum B, tak potom takýto program existuje (predpoklad $A \leq_T B$). Tento program využijeme a namiesto volania nepovolenej funkcie is_in_B dáme volanie podprogramu, ktorý počíta $C_B$ iba pomocou orákula C, teda iba pomocou funkcie is_in_C.

Druhé pozorovanie je podobne triviálne. Ak vieme A charakterizovať bez orákula, teda ak existuje ORF f taká, že $(\forall x)(C_A(x) = f(x))$, tak s akýmkoľvek orákulom B to vieme tiež (a tohoto orákula sa nemusíme vôbec na nič pýtať).

Tretie pozorovanie iba hovorí, že za predpokladu, že množinu B vieme rozhodovať, čiže existuje ORF g taká, že $(\forall x)(C_B(x) = g(x))$, tak ak by nejaká B-ČRF chcela použiť množinu B ako orákulum, potom vlastne žiadne orákulum nepotrebujeme. Je to preto, lebo keď sa budeme potrebovať spýtať, či $x \in B$, tak to môžeme zistiť priamym výpočtom (pomocou existujúcej ORF g) a nemusíme využiť orákulum. A tým pádom je možné celú množinu A rozhodovať bez orákula. Inak povedané, majme program na rozhodovanie A, ktorý používa orákulovu funkciu is_in_B. Túto funkciu len nahradíme podprogramom, ktorý počíta $C_B$ bez akéhokoľvek orákula a získame tak program, ktorý rozhoduje množinu A bez využitia orákula.

Ekvivalencia $\equiv_T$ a [[wen:Turing degree|T-stupne]]

Keď mám $\leq_T$, tak je jednoduché zadefinovať reláciu $\equiv_T$.

$A \equiv_T B$ ak platí $A \leq_T B$ & $B \leq_T A$. $A \equiv_T B$ je zrejme ekvivalencia a pre ekvivalenciu vieme vyrobiť triedy ekvivalencie. Jedna trieda ekvivalencie potom reprezentuje algoritmicky rovnako zložité množiny. Jednotlivé triedy ekvivalencie $\equiv_T$ sa označujú malým písmenom, pod ktorým je vlnovka (v TeXu snáď \underset{\widetilde}{a}, na tejto Wiki

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲a]

) a nazývajú sa "stupne nerozhodnuteľnosti" (degrees of <b>un</b>solvability). Lepším pojmom sú T-stupne, pretože pre rôzne typy prevoditeľností môžeme rovnakým spôsobom vytvoriť ekvivalencie a ich príslušné triedy nazvať 1-stupne, m-stupne, tt-stupne, wtt-stupne a podobne.

Stupeň

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲\emptyset]

(trieda ekvivalencie $\equiv_T$ reprezentovaná prázdnou množinou) sú práve všetky rekurzívne množiny. Ak máme množinu A, tak

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲a] = \[a]_T = d…

je T-stupeň obsahujúci množinu A.

Pomocou usporiadania $\leq_T$ na jednotlivých množinách môžeme na triedach ekvivalencie $\equiv_T$ zaviesť čiastočné usporiadanie $\leq$. Formálne ho definujeme takto:

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲A] \leq \[B]

ak platí $A \leq_T B$ pre ľubovoľné

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 7: A \in \̲[̲A]

a

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 7: B \in \̲[̲B]

. Je jasné, že

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲\emptyset] \leq…

pre každé B. Vyplýva to z druhého bodu pozorovania vyššie.

Mierna odbočka: Ak by sme uvažovali <Teorie%20množin> všetkých množín (pozor, nejedná sa o množinu), tak si ich môžeme rozdeliť podľa našej ekvivalencie $\leq_T$ a zistíme, že jediný T-stupeň, ktorý môžeme algoritmicky rozhodnúť je práve

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲\emptyset]

. Všetky ostatné stupne sú nerekurzívne, takže algoritmicky nerozhodnuteľné. No a práve preto sa tomu hovorí stupne <b>ne</b>rozhodnuteľnosti.

Očíslovanie

ČRF vieme očíslovať dvoma spôsobmi. Prvý z nich sa bral na <Vyčíslitelnost%20I>: $\{\varphi_e\}_{e \in N}$. My si ale tiež môžeme zobrať numeráciu $\{\Phi_e(\emptyset)\}_{e \in N}$, ktorá predstavuje ČRFály, do ktorých vložíme iba rekurzívne orákulum. Vieme, že takto vzniknuté funkcie sú rekurzívne izomorfné s ČRF, teda máme preklad z čísel numerácie $\{\varphi_e\}_{e \in N}$ na čísla numerácie $\{\Phi_e(\emptyset)\}_{e \in N}$. To znamená, že existuje rekurzívna permutácia $p$ taká, že $\varphi_e = \Phi_{p(e)}(\emptyset)$. Potom môžeme práve všetky rekurzívne spočítateľné množiny reprezentovať ako $\{W_z^\emptyset\}_{z \in N}$.

Tento prístup k funkciám a k množinám je univerzálnejší, a preto budeme radšej písať $\Phi_e(\emptyset)$ ako $\phi_e$. Poznámka: Ak by sme používali iba $\Phi_e(B)$ pre $B \leq_T \emptyset$ (teda ČRFály len s rekurzívnou množinou), dostaneme <Vyčíslitelnost%20I>.

s-m-n veta

Zadefinujeme si, čo je to funkcia viacerých premenných. Je to funkcia jednej premennej, kde dosadíme kód usporiadanej n-tice premenných: $\Phi_z(B)(x_1, x_2, \dots, x_n) \simeq \Phi_z(B)(<x_1, x_2, \dots, x_n>)$.

<b>Veta:</b><em>(relativizovaná s-m-n veta)</em> Nech $\Phi_z(B)$ je univerzálna B-ČRF. Platí s-m-n veta: Existuje PRF $\bar{s_m}$ $m + 1$ premenných taká, že platí:$\Phi_z(B)(y_1, y_2, \dots, y_m, x_1, x_2, \dots, x_n) \simeq \Phi_{\bar{s_m}(z, y_1, y_2, \dots, y_m)}(B)(x_1, x_2, \dots, x_n)$.

<b>Dôkaz:</b> V pôvodnej verzii pre $\phi_z$ sa $s_{m(z, y_1, y_2, \dots, y_m)}$ dalo predstaviť ako triviálny program, ktorý hovoril: Keď dostaneš na vstupe $z$ a $(y_1, y_2, \dots, y_n)$, tak spusti $\varphi_z(y_1, y_2, \dots, y_m, x_1, x_2, \dots, x_n)$. A našťastie aj v relativizovanom prípade tento postup funguje. Tým, že do programu pridáme prípadné otázky na orákulum B sa nič nezmení.

Trochu formálnejšie: pomocou pôvodnej s-m-n vety. Zavedieme pomocnú ČRF $\alpha$ definovanú takto:

$\alpha(z,x,w)\downarrow \iff (w = <\sigma,y,t>$ & $<\sigma,<x,y>,t> \in W_{\rho(z)})$

Táto ČRF $\alpha$ je definovaná (konverguje), ak $w$ je kód trojice, ktorá "počíta s fixovanou premennou x". Ináč povedané je to vtedy, ak po pridaní hodnoty x k vstupu y do trojice w, táto nová upravená trojica je prvkom ČRFálu s indexom z. Nech ČRF $\alpha$ má index e v pôvodnej numerácii $\{\varphi_e\}_{e \in N}$. Použijeme na ňu nerelativizovanú (inú zatiaľ nemáme :) ) verziu s-m-n vety pre dve premenné: $\alpha(z,x,w) \simeq \varphi_{s_{2}(e,z,x)}(w) \simeq \varphi_{\beta(z,x)}(w)$. Definičný obor takto definovanej funkcie $\varphi_{\beta(z,x)}(w)$ tvoria všetky trojice $<\sigma,y,t>$ z pôvodného ČRFálu $\Phi_z$, ktoré "počítajú s x". Inak povedané, ak pomocou $W_{\beta(z,x)}$ definujeme ČRFál, potom ten zo vstupu y (a množiny B) spočíta t práve vtedy, ak pôvodný ČRFál (vytvorený z $W_{z}$) zo vstupu $<x,y>$ (a množiny B) spočíta t. A to je presne to, čo chceme od s-m-n vety.

ČRFál $\Phi_z$, na ktorý sme aplikovali s-m-n vetu, bol reprezentovaný regulárnou množinou trojíc $W_{\rho(z)}$. Spôsob, akým sme zostrojili množinu $W_{\beta(z,x)}$ nám zaručuje, že aj ona je regulárna (platí $W_{\rho(\beta(z,x))} = W_{\beta(z,x)}$), a teda aj ona korektne definuje nový hľadaný ČRFál bez potreby použitia funkcie $\rho$.

$\Phi_{z}(B)(x,y) \simeq \Phi_{\beta(z,x)}(B)(y)$

Pomocou ČRF $\alpha$ sme teda odvodili PRF $\beta$, ktorá v relativizovanej s-m-n vete hraje úlohu funkcie $s_m$ z nerelativizovanej verzie.

Poznámka: s-m-n veta platí absolútne: Existuje $\bar{s_m}$ také, že pre pre každé B a pre každý číselný vstup y, x platí $\Phi_z(B)(y, x) \simeq \Phi_{\bar{s_m}(z, y)}(B)(x)$. Tiež sa hovorí, že platí uniformne alebo "stejnoměrně" (inšpirácia analýzou je asi zrejmá).

<Vyčíslitelnost%20I> sa nám celkom jednoducho relativizuje. Z ČRF sme si vyrobili B-ČRF a ČRFály, s-m-n veta viac menej ostáva, a tiež vieme relativizovať aj Postovu vetu: A je B-rekurzívna ($A \leq_T B$) práve vtedy, ak A aj $\overline{A}$ sú B-rekurzívne spočítateľné (B-RSM). A vieme tiež relativizovať generovanie: A je B-rekurzívne spočítateľná práve vtedy ak existuje prostá (a asi aj úseková) B-ČRF $f$, ktorá generuje množinu A. A teraz prichádzame k relativizácii halting problému (operácii skoku).

Operácia skoku

Už vieme, že nerelativizovaný halting problém je nerozhodnuteľný, teda nedokážeme o každom programe rozhodnúť, či sa nad daným vstupom zastaví alebo nie. Množina, ktorá halting problém reprezentuje je $K = \{x : \varphi_x(x)\downarrow\}$ a vieme, že nie je rekurzívna ale rekurzívne spočítateľná. Táto množina reprezentuje halting problém vzhľadom k T-stupňu

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲\emptyset]

, teda vzhľadom k rekurzívnym množinám. My si teraz ukážeme postup, akým sa dá vytvoriť množina reprezentujúca halting problém vzhľadom k najmenšiemu T-stupňu

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲a]

, ktorý obsahuje množinu A.

<b>Definícia:</b> (operácia skoku/relativizovaný halting problém). Pre množinu A definujeme množinu $A'= \{x: \Phi_x(A)(x)\downarrow\} = \{x: x \in W_x^A\}$. Ide teda o podobnú definíciu akou boli definované množiny $K = \{x: \varphi_x(x)\downarrow\} = \{x: x \in W_x\}$ a s ňou ekvivalentná $K_0 = \{<x,y>: x \in W_y\})$.

Množina A' sa nazýva skok (jump) množiny A.

Pôvodnú množinu $K = \{x: x \in W_x\}$ môžeme pomocou operácie skoku definovať takto: $K = \emptyset'$, pretože platí: $\emptyset' = \{x: x \in W_x^{\emptyset}\} = \{x: x \in W_x\} = K$, čo vyplýva z: $W_x \equiv W_x^{\emptyset}$. Teda rekurzívne orákulum nám nepomôže a množina $W_x^{\emptyset}$ je stále rekurzívne spočítateľná. Zápis $W_x \equiv W_x^{\emptyset}$ znamená, že množina $W_x$ je rekurzívne izomorfná s množinou $W_x^{\emptyset}$ a vraj sa to dá jednoducho dokázať.

Skok je množinová operácia z $A$ do $A'$. $A'$ je relativizovaný halting problém. Prirodzeným zovšeobecnením operácie skoku je jej opakované použitie - môžeme ju totiž iterovať:

Definícia:

*$A^0 = A$ (nultý skok neskáče) *$A^{(n+1)} = (A^{(n)})'$

Vraj sa takto dá postupovať aj na $\omega_0$ a ďalej, ale to by chcelo trošku lepšie vedieť <Teorie%20množin>.

A na koniec prednášky už len znenie jednej vety, ktorá operáciu skoku charakterizuje: #A' je A-rekurzívne spočítateľná. (obdoba toho, že K je rekurzívne spočítateľná)

#A' nie je A-rekurzívna, $\overline{A'}$ nie je A-rekurzívne spočítateľná. (obdoba toho istého pre K a $\overline{K}$). #B je A-rekurzívne spočítateľná práve vtedy, ak platí $B \leq_1 A'$. (obdoba toho, že K je 1-úplná).

#Ak A je B-rekurzívne spočítateľná a $B \leq_T C$, tak A je C-rekurzívne spočítateľná. Pozor, nemýliť si, medzi ktorými dvoma je aký vzťah v predpokladoch! #$A \leq_T B \iff A' \leq_1 B'$

#$A \equiv_T B \iff A' \equiv_1 B'$

V posledných dvoch bodoch je naozaj na jednej strane T-prevoditeľnosť a na druhej 1-prevoditeľnosť. Ale tomu sa budeme venovať až na ďalšej prednáške.