{{TIN065 Prednášky}} Toto je zhrnutie poznatkov potrebných na skúšku. Skúška z 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ž rekurzívna 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 \leq_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 \leq_T C)$, tak A je rekurzívne spočetná v C #$A\leq_T B \iff A' \leq_1 B'$ #$A\equiv_T B \iff A' \equiv_1 B'$ 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\leq_1 A^\prime$ $\iff$ $(\exists \mathrm{ORF} f)(x \in B \iff f(x) \in A^\prime)$ $\iff$ $(\exists \mathrm{ORF} f)(x \in B \iff \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 s-m-n vetu: $(\exists PRF g)(\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 \iff \Phi_{f(x)}(A)(f(x))\downarrow \iff \Phi_{g(a, z_0, x)}(A)(g(a, z_0, x))\downarrow \iff \alpha(z_0, x, g(a, z_0, x))\downarrow \iff \Phi_{z_0}(A)(x)\downarrow \iff x \in B$. Teda dokázali sme ekvivalenciu: $x \in B \iff f(x) \in A^\prime$, čo je presná definícia $B\leq_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' \leq_1 B'$. $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 \leq_T B$. #*Nech $A \leq_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' \leq_1 B'$. #Triviálny dôsledok predchádzajúceho. ### Uniformnosť skoku ### Veta: Existuje $z_0$ také, že pre každé $A$ platí $A^\prime = W_{z_0}^A$. Dôkaz: 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$ $\iff$ $\Phi_x(A)(x)\downarrow$ $\iff$ $\exists \sigma, y (<\sigma, x, y> \in W_{\rho(x)} \And (\sigma \leq A))$ $\iff$ $\exists \sigma, y (<\sigma, x, y> \in W_{z_0} \And (\sigma \leq A))$ $\iff$ $\exists \sigma, y (<\sigma, x, y> \in W_{\rho(z_0)} \And (\sigma \leq A))$ $\iff$ $(\Phi_{z_0}(\sigma)(x) = y) \And (\sigma \leq A)$ $\iff$ $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 \leq_T \emptyset^\prime$ $\iff$ $A$ je limitne vyčísliteľná. Dôkaz: $A \leq_T \emptyset^\prime$ znamená, že $\exists z (A(x) = \Phi_z(\emptyset^\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} $ $\emptyset^\prime_s$ je aproximácia $\emptyset^\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 $\emptyset^\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\geq 1 (f(x,s) \neq f(x, s+j))?$. To je rekurzívne v $\emptyset^\prime$, takže aj negácia toho $\forall j\geq 1 (f(x,s) = f(x, s+j))$ je rekurzívna. Na tú pustím $\mu_s$, čo je síce $\emptyset^\prime$ ČRF, ale keďže $A$ je totálne, tak je to $\emptyset^\prime$ ORF, teda rekurzívne v $\emptyset^\prime$. Veta: $f$ je ORF $\implies$ $\lim_s f(x, s)$ je $\emptyset^\prime$ ČRF. $\varphi$ je $\emptyset^\prime$ČRF $\implies$ $\exists \mathrm{ ORF } f \forall x (\varphi(x) \simeq \lim_s f(x, s))$ Dôkaz {{TODO}}. Relativizovaná veta (takmer rovnaké znenie): $f$ je $A$ORF $\implies$ $\lim_s f(x, s)$ je $A^\prime$ ČRF. $\varphi$ je $A^\prime$ČRF $\implies$ $\exists A\mathrm{ ORF } f \forall x (\varphi(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\leq j (Q(x))$ môžeme nahradiť $Q(1)\And Q(2) \And \ldots \And 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 \iff \overline{B} \in \Pi_n$ #$B \in \Sigma_n \implies B \in \Sigma_m \cap \Pi_m (\forall m > n)$ #$A\leq_1 B \And B\in \Sigma_n \implies A \in \Sigma_n$ Dôkaz triviálny Veta: Existuje univerzálny $\Sigma_n$ aj $\Pi_n$ predikát pre $n \geq 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 \ldots \exists Q(x, y_1, \ldots, y_1)$. Odrežeme pred posledným kvantifikátorom, dostaneme $\exists y_n Q(x, y_1, \ldots, y_n)$, to nahrádime univerzálnym predikátom a vrátime kvantifikátory späť: $\exists y_1 \forall y_2 \ldots \exists y_n T_n(e, x, y_1, \ldots, 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 \geq 1 \Sigma_n - \Pi_n \neq \emptyset$. Dôkaz: Nech $Univ^{(n)}(e, x)$ je univerzálny predikát pre $\Sigma_n$. Vezmem $P(x) = Univ^{(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 $Univ^{(n)}(e_0, x)$. Teda $\neg Univ^{(n)}(x, x) = Univ^{(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 \geq 1: \emptyset^n$ je $\Sigma_n$ úplná. #*A* je rekurzívne spočetná v $\emptyset^n \iff A \in \Sigma_{n+1} \forall n \geq 0$ #$A \leq_T \emptyset^n \iff A\in \Sigma_{n+1} \cap \Pi_{n+1}$ Dôkaz Časti 3 a 1 vyplývajú z časti 2. $2 \implies 3$: $A$ je rekurzívne v $\emptyset^n$ znamená, že $A$ aj $\overline{A}$ sú rekurzívne spočetné v $\emptyset^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 \implies 1$: $\emptyset^n$ je rekurzívne spočetná v $\emptyset^{n-1}$ a preto z (2) patrí do $\Sigma_n$. Ak $B \in \Sigma_n$, tak z (2) je $B$ rekurzívna v $\emptyset^{(n-1)}$ a z vlastností skoku $B \leq_1 \emptyset^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 \ldots Q(\ldots)$. 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 $\emptyset^{(n-1)}$. z vlastnosti skoku je rekurzívna v $\emptyset^{(n)}$. Keď je negácia rekurzívna v $\emptyset^{(n)}$, tak aj bez negácie je to rekurzívne v $\emptyset^{(n)}$ a po pridaní odtrhnutého kvantifikátoru späť je to rekurzívne spočetné v $\emptyset^{(n)}$. Opačným smerom: Ak máme $A=\mbox{dom}(\Phi_z(\emptyset^{(n)})$, tak podľa vety o limitnej vyčísliteľnosti: $\Phi_z(\emptyset^{(n)}) = \lim_s h(z,x,s)$, kde $h$ je $\emptyset^{(n-1)}$ORF. Takže $x \in A \iff \Phi_z(\emptyset^{(n)})\downarrow$ a to je práve vtedy, keď existuje tá limita. To je práve vtedy, keď $\exists s_0 \forall s \geq s_0 (h(z,x,s)=h(z,x,s_0))$. Tá vec v poslednej zátvorke je rekurzívna v $\emptyset^{(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 \geq 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 $(\forall e) (\exists \alpha_e \leq A) \[(\Phi_e(\alpha_e)(e)\!\!\downarrow) \lor ((\forall \gamma \geq \alpha_e) \Phi_e(\gamma)(e)\!\!\uparrow)]$ Veta: Existuje 1-generická $A \leq_T \emptyset'$ Dôkaz: Indukciou, prvý krok $\alpha_0 = \emptyset$. Následne budeme generovať $\alpha_0 \leq \alpha_1 \leq \alpha_2 \leq \cdots $, pre $\Phi_1, \Phi_2, \cdots$ Máme $\alpha_e \in 2^{\leq \omega}$ konečný retiazok, pre $\Phi_e$. Hľadáme pre $\Phi_{e+1}$, otázkou $(\exists \gamma \geq \alpha_e) (\Phi_{e+1}(\gamma)(e+1)\!\!\downarrow)$ čo je ekvivalentné s $(\exists \gamma \geq \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 $\leq_T \emptyset'$ 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 $\emptyset'$. $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 \implies \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 $\emptyset^\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 \varphi_{x, s}(y) \downarrow\}$. Tot je v $\Pi_2$ Nech B je v $\Pi_2$. $x \in B \iff \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) = \varphi_{g(x)}(y)$. $x\in B$ $\iff$ $\forall y \exists s (Q(x, y, s))$ $\iff$ $\forall y (\alpha(x, y)\downarrow)$ $\iff$ $\forall y (\varphi_{g(x)}(y)\downarrow)$ $\iff$ $g(x) \in \mathrm{Tot}$. Veta: $Inf = \{x: W_x \mbox{ 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 $\varphi_x$ a zastane vtedy, keď všetky zastanú. Podľa *s-m-n* $\alpha(x, j) = \varphi_{a(x)}(j)$. $x$ patrí do Tot práve keď $\varphi_x(j)$ zastaví pre každé $j$, takže $\alpha(x, j)$ zastaví pre každé $j$, takže $\varphi_{a(x)}$ zastaví pre nekonečne veľa (všetky) $j$, teda $a(x)$ patrí do Inf. Ak $x$ nepatrí do Tot, tak $\varphi_x(j)$ pre nejaké $j$ nezastaví, takže $\alpha(x, j)$ nezastaví pre všetky $j^\prime$ väčšie ako $j$, takže $\varphi_{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 = $\{x: W_x \mbox{ je rekurzívne}\}$ je $\Sigma_3$ úplná.