{{TIN065 Prednášky}} Toto je zhrnutie poznatkov potrebných na skúšku.

Skúška z <Vyčíslitelnost%20II> obsahuje dve otázky. Prvá otázka sa týka jednej zo základných tém. V druhej otázke je možné si vybrať z jednej z ponúknutých tém a vypracovať len tú (nikto nebráni vybrať si všetky).

Základné témy (prvá otázka): #Operácia skoku a jej vlastnosti

#Limitná vyčísliteľnosť #Aritmetická hierarchia

Rozširujúce témy (druhá otázka)

#1-generickosť #rekurzívne stromy

#${\Sigma }_n$ alebo ${\Pi }_n$ úplnosť

Základy

ČRFál ${\Phi }_z(A)(x)$ je program s číslom $z$, ktorý má na vstupe $x$ a množinu $A$, ktorú používa ako orákulum. ${\Phi }_{z,s}$ je ČRFál za $s$ krokov. Je to tiež <em>rekurzívna</em> množina nekolidujúcich trojíc $<\sigma ,x,y>$ takých, že z $x$ pomocou časti orákula $\sigma$ vypočítame $y$. To, že sú trojice $<\sigma ,x,y>$ nekolidujúce znamená, že z dlhšieho $\sigma$ nemôžeme dostať iné $y$ ako z kratšieho. Nie každá rekurzívne spočetná množina $W_z$ je ČRFál, ale z každej môžeme ČRFál vyrobiť regularizačnou funkciou $\rho$, ktorá konfliktné dvojice oreže.

$(\forall W_z)(\exists {\Phi }_{\rho (z)})$

$A{\le }_{T}B$ znamená, že existuje ČRFál $\Phi$ taký, že $C_A(x)=\Phi (B)(x)$. Tým pádom funkcia $\Phi (B)(x)$ je totálna. Hovoríme, že $A$ je $B$-rekurzívna (rekurzívna v $B$).

$W_z^A=\{x:{\Phi }_z(A)(x)\downarrow \}$ sú $A$ rekurzívne spočetné množiny.

Operácia skoku a jej vlastnosti

Pre množinu $A$ definujeme množinu $A^{\prime }=\{x:{\Phi }_x(A)(x)\downarrow \}=\{x:x\in W_x^A\}$ ako skok množiny $A$.

Veta (vlastnosti skoku):

#A' je A-rekurzívne spočetná #A' nie je A rekurzívna

#B je A-rekurzívne spočetná práve vtedy, keď B je 1-prevoditeľná na A' #Ak A je rekurzívne spočetná v B a zároveň B je turingovsky prevoditeľná na C $(B{\le }_{T}C)$, tak A je rekurzívne spočetná v C

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

Dôkaz:

#Z definície.

#Podľa Postovej vety. Sporom ukážeme, že $\overline{A^{\prime }}$ nie je $A$ rekurzívne spočetná. Nech teda je a je to množina $W_{x_0}$. Ak $x_0\in \overline{A^{\prime }}=W_{x_0}$, tak z definície $A^{\prime }$ platí $x_0\in A^{\prime }$, čo je spor. Ak $x_0\notin \overline{A^{\prime }}=W_{x_0}$, tak $x_0\notin A^{\prime }$, teda $x_0\in \overline{A^{\prime }}$, čo je zasa spor. Teda $\overline{A^{\prime }}$ nie je $A$ rekurzívne spočetná. #Najťažšia a najdôležitejšia časť tejto vety.

• $B{\le }_1{A}^{\prime }$ $⟺$ $(\exists \mathrm{ORF}f)(x\in B⟺f(x)\in A^{\prime })$ $⟺$ $(\exists \mathrm{ORF}f)(x\in B⟺{\Phi }_{f(x)}(A)(f(x))\downarrow )$. Definícia množiny $B$ je teda rekurzívne spočetná v $A$.

#*$B$ je $A$ rekurzívne spočetná, teda $(\exists z_0)(B=\{x:{\Phi }_{z_0}(A)(x)\downarrow )$. Vyrobíme si funkciu $\alpha (z,x,w)\simeq {\Phi }_z(A)(x)$ s jedným parametrom naviac ($w$). Funkcia $\alpha$ je $A$ rekurzívne spočetná, a teda má index, ktorý si označme $a$. Teda platí: $\alpha (z,x,w)={\Phi }_a(A)(z,x,w)$. Použijeme <em>s-m-n</em> vetu: $(\exists PRFg)(\alpha (z,x,w)={\Phi }_a(A)(z,x,w)={\Phi }_{g(a,z,x)}(A)(w))$. Zadefinujeme si $f(x)=g(a,z_0,x)$. $f$ je definovaná pomocou $g$, takže je PRF, a teda aj ORF. Potom bude platiť: $f(x)\in A^{\prime }⟺{\Phi }_{f(x)}(A)(f(x))\downarrow ⟺{\Phi }_{g(a,z_0,x)}(A)(g(a,z_0,x))\downarrow ⟺\alpha (z_0,x,g(a,z_0,x))\downarrow ⟺{\Phi }_{z_0}(A)(x)\downarrow ⟺x\in B$. Teda dokázali sme ekvivalenciu: $x\in B⟺f(x)\in A^{\prime }$, čo je presná definícia $B{\le }_1{A}^{\prime }$. #Intuitívne: Vezmeme si ČRFál ${\Phi }_z$, ktorý pomocou $B$ zisťuje, či je niečo prvkom $A$. Zisťuje to rekurzívne spočetne: ak $x\in A$, tak to časom zistí, ak $x\notin A$ tak nezastaví. Tento ČRFál sa raz za čas pýta na $B$. A každú otázku na $B$ nahradíme spočítaním $B$ z $C$ (tentokrát už rekurzívnym), čiže nejakými otázkami na $C$. Takže $A$ je rekurzívne spočetná v $C$.

#Dôkaz poskladáme z predchádzajúcich tvrdení. #*Nech $A^{\prime }{\le }_1{B}^{\prime }$. $A$ aj $\overline{A}$ sú obe $A$ rekurzívne, a teda sú aj $A$ rekurzívne spočetné. Z (3) sú obe 1-prevoditeľné na $A^{\prime }$. Z tranzitívnosti sú 1-prevoditeľné aj na $B^{\prime }$ a zase z (3) sú obe $B$ rekurzívne spočetné. Z Postovej vety potom vyplynie, že $A$ je rekurzívne v $B$, čo je len iné pomenovanie pre vzťah $A{\le }_{T}B$.

#*Nech $A{\le }_{T}B$. Z (1) vieme, že $A^{\prime }$ je $A$ rekurzívne spočetná. Podľa (4) platí, že $A^{\prime }$ je tiež $B$ rekurzívne spočetná. No a potom podľa (3) je $A^{\prime }$ 1-prevoditeľná na $B^{\prime }$, teda $A^{\prime }{\le }_1{B}^{\prime }$. #Triviálny dôsledok predchádzajúceho.

Uniformnosť skoku

<b>Veta:</b> Existuje $z_0$ také, že pre každé $A$ platí $A^{\prime }=W_{z_0}^A$.

<b>Dôkaz:</b> Vytvoríme $W_{z_0}=\{<\sigma ,x,y>:<\sigma ,x,y>\in W_{\rho (x)}\}$. Táto množina je regulárna, lebo $\rho$ orezáva konflikty a konflikty môžu nastať len pri rovnakom $x$. $W_{\rho (z_0)}=W_{z_0}$. $x\in A^{\prime }$ $⟺$ ${\Phi }_x(A)(x)\downarrow$ $⟺$ $\exists \sigma ,y(<\sigma ,x,y>\in W_{\rho (x)}\&(\sigma \le A))$ $⟺$ $\exists \sigma ,y(<\sigma ,x,y>\in W_{z_0}\&(\sigma \le A))$ $⟺$ $\exists \sigma ,y(<\sigma ,x,y>\in W_{\rho (z_0)}\&(\sigma \le A))$ $⟺$ $({\Phi }_{z_0}(\sigma )(x)=y)\&(\sigma \le A)$ $⟺$ $x\in W_{z_0}^A$.

Limitná vyčísliteľnosť

Definícia: A je limitne vyčísliteľná práve keď existuje ORF $f$ taká, že $\forall x(A(x)={\lim }_{s}f(x,s))$.

Veta: $A{\le }_T{\varnothing }^{\prime }$ $⟺$ $A$ je limitne vyčísliteľná.

Dôkaz: $A{\le }_T{\varnothing }^{\prime }$ znamená, že $\exists z(A(x)={\Phi }_z({\varnothing }^{\prime })(x))$. Vytvoríme si funkciu $f(x,s)$:

$f(x,s) = \begin{cases}

\Phi_{z,s}(\emptyset^\prime_s)(x),&\mbox{ak} \Phi_{z,s}(\emptyset^\prime_s)(x)\downarrow\
s+1&\mbox{inak}\

\end{cases} $

${\varnothing }_s^{\prime }$ je aproximácia ${\varnothing }^{\prime }$ za $s$ krokov. Keďže potrebujeme len konečný úsek na to, aby ${\Phi }_z$ začalo konvergovať (a keďže $A$ je totálna, tak to konvergovať začne), tak existuje $s_1$ krokov, v ktorých už počiatočný úsek ${\varnothing }^{\prime }$ je hotový (všetko, čo patrí do tohto úseku už zastavilo - len nevieme, že to, čo tam nepatrí už nezastane, ale to nás netrápi). Tiež existuje $s_2$, kedy ${\Phi }_z$ zastaví (keďže A je totálna). Pre $s=\max (\{s_1,s_2\})$ bude $f$ vraciať prvú hodnotu a pre väčšie $s$ sa táto hodnota nebude meniť, takže $f$ bude mať správnu limitu (a to $A$).

Ak $A={\lim }_{s}f(x,s)$. Pýtame sa: $\exists j\ge 1(f(x,s)\ne f(x,s+j))?$. To je rekurzívne v ${\varnothing }^{\prime }$, takže aj negácia toho $\forall j\ge 1(f(x,s)=f(x,s+j))$ je rekurzívna. Na tú pustím ${\mu }_s$, čo je síce ${\varnothing }^{\prime }$ ČRF, ale keďže $A$ je totálne, tak je to ${\varnothing }^{\prime }$ ORF, teda rekurzívne v ${\varnothing }^{\prime }$.

Veta:

$f$ je ORF $⟹$ ${\lim }_{s}f(x,s)$ je ${\varnothing }^{\prime }$ ČRF. $\phi$ je ${\varnothing }^{\prime }$ČRF $⟹$ $\exists \mathrm{ORF}f\forall x(\phi (x)\simeq {\lim }_{s}f(x,s))$

Dôkaz {{TODO}}.

Relativizovaná veta (takmer rovnaké znenie):

$f$ je $A$ORF $⟹$ ${\lim }_{s}f(x,s)$ je $A^{\prime }$ ČRF. $\phi$ je $A^{\prime }$ČRF $⟹$ $\exists A\mathrm{ORF}f\forall x(\phi (x)\simeq {\lim }_{s}f(x,s))$

Aritmetická hierarchia

${\Sigma }_n$ a ${\Pi }_n$ sú prefixy kvantifikátorov pred nejakým ORP. V každom je $n$ skupín, každá skupina je homogénna a $\Sigma$ začína $\exists$.

Obmedzené kvantifikátory ignorujeme ($\forall x\le j(Q(x))$ môžeme nahradiť $Q(1)\&Q(2)\&\dots \&Q(j)$).

${\Sigma }_n$ predikát je ORP s ${\Sigma }_n$ prefixom. Podobne pre ${\Pi }_n$. Predikát nám definuje aj množinu. Takže máme ${\Sigma }_n$ aj ${\Pi }_n$ množiny.

Vetička o hierarchii: #$B\in {\Sigma }_n⟺\overline{B}\in {\Pi }_n$

#$B\in {\Sigma }_n⟹B\in {\Sigma }_m\cap {\Pi }_m(\forall m>n)$ #$A{\le }_{1}B\&B\in {\Sigma }_n⟹A\in {\Sigma }_n$

Dôkaz triviálny

Veta: Existuje univerzálny ${\Sigma }_n$ aj ${\Pi }_n$ predikát pre $n\ge 1$ (pozor, nie pre nulu).

Dôkaz: Indukciou. Pre ${\Sigma }_1$ vieme z prvého semestra, že existuje ($\exists s{T}_1(e,x,s)$). Pre ${\Pi }_1$ je to $\forall s\neg T_1(e,x,s)$.

Pre väčšie $n$: Ak $n$ je nepárne, tak ${\Sigma }_n$ vyzerá ako $\exists \forall \dots \exists Q(x,y_1,\dots ,y_1)$. Odrežeme pred posledným kvantifikátorom, dostaneme $\exists y_{n}Q(x,y_1,\dots ,y_n)$, to nahrádime univerzálnym predikátom a vrátime kvantifikátory späť: $\exists y_1\forall y_2\dots \exists y_n{T}_n(e,x,y_1,\dots ,y_n)$. Pre párne $n$ podobne, len po odtrhnutí z $\forall Q()$ vyrobím $\exists \neg Q()$, nahradím univerzálnym $\exists T_n()$, vrátim na $\forall \neg T_n()$ a pridám kvantifikátory späť.

Pre ${\Pi }_n$ rovnako.

Veta: $\forall n\ge 1{\Sigma }_n-{\Pi }_n\ne \varnothing$.

Dôkaz: Nech $Uni{v}^{(n)}(e,x)$ je univerzálny predikát pre ${\Sigma }_n$. Vezmem $P(x)=Uni{v}^{(n)}(x.x)$. To, že je v ${\Sigma }_n$ je vidieť a keby bol v ${\Pi }_n$, tak jeho negácia by musela byť v ${\Sigma }_n$. Tá má svoje číslo $e_0$ a je teda $Uni{v}^{(n)}(e_0,x)$. Teda $\neg Uni{v}^{(n)}(x,x)=Uni{v}^{(n)}(e_0,x)$, čo pre $x=e_0$ dá spor. Takže $P(x)$ je v ${\Sigma }_n$ ale nie v ${\Pi }_n$.

Veta o hierarchii:

#$\forall n\ge 1:{\varnothing }^n$ je ${\Sigma }_n$ úplná.

#A je rekurzívne spočetná v ${\varnothing }^n⟺A\in {\Sigma }_{n+1}\forall n\ge 0$ #$A{\le }_T{\varnothing }^n⟺A\in {\Sigma }_{n+1}\cap {\Pi }_{n+1}$

Dôkaz

Časti 3 a 1 vyplývajú z časti 2.

$2⟹3$: $A$ je rekurzívne v ${\varnothing }^n$ znamená, že $A$ aj $\overline{A}$ sú rekurzívne spočetné v ${\varnothing }^n$, takže sú (podľa 2) v ${\Sigma }_{n+1}$ a podľa vetičky ak $\overline{A}\in {\Sigma }_{n+1}$, tak $A\in {\Pi }_{n+1}$.

$2⟹1$:

${\varnothing }^n$ je rekurzívne spočetná v ${\varnothing }^{n-1}$ a preto z (2) patrí do ${\Sigma }_n$.

Ak $B\in {\Sigma }_n$, tak z (2) je $B$ rekurzívna v ${\varnothing }^{(n-1)}$ a z vlastností skoku $B{\le }_1{\varnothing }^n$

2. Indukciou. Pre nulu je to zrejmé.

Majme množinu $A\in {\Sigma }_{n+1}$. A sa dá teda vyjadriť v tvare $\exists \forall \dots Q(\dots )$. Odrežme to za prvým kvantifikátorom. To, čo dostaneme je v ${\Pi }_n$. Negácia toho je v ${\Sigma }_n$ a podľa indukčného predpokladu je rekurzívne spočetná v ${\varnothing }^{(n-1)}$. z vlastnosti skoku je rekurzívna v ${\varnothing }^{(n)}$. Keď je negácia rekurzívna v ${\varnothing }^{(n)}$, tak aj bez negácie je to rekurzívne v ${\varnothing }^{(n)}$ a po pridaní odtrhnutého kvantifikátoru späť je to rekurzívne spočetné v ${\varnothing }^{(n)}$.

Opačným smerom:

Ak máme

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 3: A=\̲m̲b̲o̲x̲{dom}(\Phi_z(\e…

, tak podľa vety o limitnej vyčísliteľnosti: ${\Phi }_z({\varnothing }^{(n)})={\lim }_{s}h(z,x,s)$, kde $h$ je ${\varnothing }^{(n-1)}$ORF. Takže $x\in A⟺{\Phi }_z({\varnothing }^{(n)})\downarrow$ a to je práve vtedy, keď existuje tá limita. To je práve vtedy, keď $\exists s_0\forall s\ge s_0(h(z,x,s)=h(z,x,s_0))$. Tá vec v poslednej zátvorke je rekurzívna v ${\varnothing }^{(n-1)}$ a podľa (3) je v prieniku ${\Sigma }_n\cap {\Pi }_n$, čiže aj v ${\Pi }_n$. Máme $\exists s_0\forall s\ge s_0({\Pi }_n)$. Všeobecný kvantifikátor necháme pohltiť v ${\Pi }_n$ a existenčný z toho vyrobí ${\Sigma }_{n+1}$.

1-generickosť

Def.: $A$ je 1-generická ak

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 40: …pha_e \leq A) \̲[̲(\Phi_e(\alpha_…

Veta: Existuje 1-generická $A{\le }_T{\varnothing }^{\prime }$

Dôkaz: Indukciou, prvý krok ${\alpha }_0=\varnothing$. Následne budeme generovať ${\alpha }_0\le {\alpha }_1\le {\alpha }_2\le \cdots$, pre ${\Phi }_1,{\Phi }_2,\cdots$

Máme ${\alpha }_e\in 2^{\le \omega }$ konečný retiazok, pre ${\Phi }_e$. Hľadáme pre ${\Phi }_{e+1}$, otázkou

$(\exists \gamma \ge {\alpha }_e)({\Phi }_{e+1}(\gamma )(e+1)\downarrow )$

čo je ekvivalentné s $(\exists \gamma \ge {\alpha }_e)(\exists s)({\Phi }_{e+1,s}(\gamma )(e+1)\downarrow )$, vnútri máme rekurzívny predikát, preto táto otázka je ${\Sigma }_1^0$, čo je ${\le }_T{\varnothing }^{\prime }$

Halting problém nám odpovie. Ak odpovie áno, tak dosadíme prvý taký retiazok ${\alpha }_{e+1}=\gamma$, za ním už všetky budú konvergovať. Ak nie, tak ${\alpha }_{e+1}={\alpha }_e$ a vieme, že forcuje silnú divergenciu.

Takto si vygenerujeme postupne celé $A$, pomocou ${\varnothing }^{\prime }$. $A={\cup }_e{\alpha }_e$.

Rekurzívne stromy

Rekurzívny strom je rekurzívna množina nula-jedničkových retiazkov taká, že ak do nej patrí $\sigma$, tak do nej patrí aj každý prefix $\sigma$.

$f$ je nekonečná vetva v strome, pokiaľ $\forall n(f\upharpoonright n\in T)$, kde $f\upharpoonright n$ je obmedzenie $f$ na prvých $n$ položiek. a $f$ je nekonečný binárny retiazok.

Königová lema: Binárny strom je nekonečný práve vtedy, keď obsahuje nekonečnú vetvu.

Dôkaz: Jedným smerom triviálny. Druhým smerom: buď ľavý alebo pravý podstrom koreňa je nekonečný, tak ideme do toho podstromu. Iterujeme a tým nájdeme nekonečnú vetvu.

Aké ťažké je zistiť, či je strom konečný? Máme otázku $\exists h:\forall \alpha (|\alpha |=h⟹\alpha \notin T)?$ ($h$ je hĺbka). To je existenčný kvantifikátor na rekurzívnu podmienku (všeobecný kvantifikátor je obmedzený), takže je to v ${\Sigma }_1$ a ${\varnothing }^{\prime }$ nám na odpoveď stačí.

Úplnosti

Veta: Tot = $\{x:W_x=\mathbb{N}\}$ je ${\Pi }_2$ úplná.

Dôkaz:

Tot = $\{x:\forall y\exists s{\phi }_{x,s}(y)\downarrow \}$. Tot je v ${\Pi }_2$

Nech B je v ${\Pi }_2$. $x\in B⟺\forall y\exists s(Q(x,y,s))$. $Q$ je rekurzívny. Vyrobme $\alpha (x,y)={\mu }_s(Q(x,y,s)$. Podľa s-m-n vety $\alpha (x,y)={\phi }_{g(x)}(y)$. $x\in B$ $⟺$ $\forall y\exists s(Q(x,y,s))$ $⟺$ $\forall y(\alpha (x,y)\downarrow )$ $⟺$ $\forall y({\phi }_{g(x)}(y)\downarrow )$ $⟺$ $g(x)\in \mathrm{Tot}$.

Veta:

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 16: Inf = \{x: W_x \̲m̲b̲o̲x̲{ je nekonečná}…

je ${\Pi }_2$ úplná.

Dôkaz: Inf = $\{x:\forall s\exists j>s\exists t(j\in W_{x,t})\}$. Inf je v ${\Pi }_2$

Prevedieme Tot na Inf pomocou 1prevoditeľnosti. Vyrobíme si funkciu $\alpha (x,j)$, ktorá robí to, že na čísla od $1$ po $j$ postupne spúšťa ${\phi }_x$ a zastane vtedy, keď všetky zastanú. Podľa s-m-n $\alpha (x,j)={\phi }_{a(x)}(j)$.

$x$ patrí do Tot práve keď ${\phi }_x(j)$ zastaví pre každé $j$, takže $\alpha (x,j)$ zastaví pre každé $j$, takže ${\phi }_{a(x)}$ zastaví pre nekonečne veľa (všetky) $j$, teda $a(x)$ patrí do Inf.

Ak $x$ nepatrí do Tot, tak ${\phi }_x(j)$ pre nejaké $j$ nezastaví, takže $\alpha (x,j)$ nezastaví pre všetky $j^{\prime }$ väčšie ako $j$, takže ${\phi }_{a(x)}$ zastaví len pre konečne veľa $j$, takže $a(x)$ nepatrí do Inf.

$a(x)$ prevádza Tot na Inf. Keby sme potrebovali prevod opačným smerom, stačí povedať, že Tot je ${\Pi }_2$ úplná.

{{TODO}}

Veta: Fin - doplnok Inf - je ${\Sigma }_2$ (pravdepodobne úplný)

Veta: Rek =

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 10: \{x: W_x \̲m̲b̲o̲x̲{ je rekurzívne…

je ${\Sigma }_3$ úplná.