{{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 ${\le }_T$

Pozorovania:

#Vzťah ${\le }_T$ je reflexívny a tranzitívny. #Ak A je rekurzívna množina, tak $A{\le }_{T}B$ pre každé B.

#Ak $A{\le }_{T}B$ a B je rekurzívna, tak aj A je rekurzívna. Pozorovania sú viac menej zrejmé. Keďže pri ${\le }_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 ${\le }_T$ reflexívne ($A{\le }_{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{\le }_{T}B$ a $B{\le }_{T}C$. Chceme zistiť, či $A{\le }_{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{\le }_{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 ${\le }_T$, tak je jednoduché zadefinovať reláciu ${\equiv }_T$.

$A{\equiv }_{T}B$ ak platí $A{\le }_{T}B$ & $B{\le }_{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 ${\le }_T$ na jednotlivých množinách môžeme na triedach ekvivalencie ${\equiv }_T$ zaviesť čiastočné usporiadanie $\le$. Formálne ho definujeme takto:

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

ak platí $A{\le }_{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 ${\le }_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>: $\{{\phi }_e{\}}_{e\in N}$. My si ale tiež môžeme zobrať numeráciu $\{{\Phi }_e(\varnothing ){\}}_{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 $\{{\phi }_e{\}}_{e\in N}$ na čísla numerácie $\{{\Phi }_e(\varnothing ){\}}_{e\in N}$. To znamená, že existuje rekurzívna permutácia $p$ taká, že ${\phi }_e={\Phi }_{p(e)}(\varnothing )$. Potom môžeme práve všetky rekurzívne spočítateľné množiny reprezentovať ako $\{W_z^{\varnothing }{\}}_{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(\varnothing )$ ako ${\varphi }_e$. Poznámka: Ak by sme používali iba ${\Phi }_e(B)$ pre $B{\le }_T\varnothing$ (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 $\overline{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 }_{\overline{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 ${\varphi }_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 ${\phi }_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 ⟺(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 $\{{\phi }_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 {\phi }_{s_2(e,z,x)}(w)\simeq {\phi }_{\beta (z,x)}(w)$. Definičný obor takto definovanej funkcie ${\phi }_{\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 $\overline{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 }_{\overline{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{\le }_{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:{\phi }_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^{\prime }=\{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:{\phi }_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={\varnothing }^{\prime }$, pretože platí: ${\varnothing }^{\prime }=\{x:x\in W_x^{\varnothing }\}=\{x:x\in W_x\}=K$, čo vyplýva z: $W_x\equiv W_x^{\varnothing }$. Teda rekurzívne orákulum nám nepomôže a množina $W_x^{\varnothing }$ je stále rekurzívne spočítateľná. Zápis $W_x\equiv W_x^{\varnothing }$ znamená, že množina $W_x$ je rekurzívne izomorfná s množinou $W_x^{\varnothing }$ a vraj sa to dá jednoducho dokázať.

Skok je množinová operácia z $A$ do $A^{\prime }$. $A^{\prime }$ 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)}{)}^{\prime }$

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^{\prime }}$ 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{\le }_1{A}^{\prime }$. (obdoba toho, že K je 1-úplná).

#Ak A je B-rekurzívne spočítateľná a $B{\le }_{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{\le }_{T}B⟺A^{\prime }{\le }_1{B}^{\prime }$

#$A{\equiv }_{T}B⟺A^{\prime }{\equiv }_1{B}^{\prime }$

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.