TIN065 Zhrnutie

Prednášky z Vyčísliteľnosti II
Obsah
Prehľad Prvá prednáška Druhá prednáška Tretia prednáška Štvrtá prednáška Piata prednáška Šiesta prednáška Siedma prednáška Ôsma prednáška Deviata prednáška Desiata prednáška Jedenásta prednáška Dvanásta prednáška Zhrnutie na skúšku

Toto je zhrnutie poznatkov potrebných na skúšku. Skúška z Vyčísliteľnosti II 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):

1. Operácia skoku a jej vlastnosti
2. Limitná vyčísliteľnosť
3. Aritmetická hierarchia

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

1. 1-generickosť
2. rekurzívne stromy
3. $ \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):

1. A' je A-rekurzívne spočetná
2. A' nie je A rekurzívna
3. B je A-rekurzívne spočetná práve vtedy, keď B je 1-prevoditeľná na A'
4. 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
5. $ A\leq_T B \iff A' \leq_1 B' $
6. $ A\equiv_T B \iff A' \equiv_1 B' $

Dôkaz:

1. Z definície.
2. 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á.
3. 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 $.
4. 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 $.
5. 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' $.
6. 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

Tato část je neúplná a potřebuje rozšířit. {{{1}}}

.

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:

1. $ B \in \Sigma_n \iff \overline{B} \in \Pi_n $
2. $ B \in \Sigma_n \implies B \in \Sigma_m \cap \Pi_m (\forall m > n) $
3. $ 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:

1. $ \forall n \geq 1: \emptyset^n $ je $ \Sigma_n $ úplná.
2. A je rekurzívne spočetná v $ \emptyset^n \iff A \in \Sigma_{n+1} \forall n \geq 0 $
3. $ 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á.

Tato část je neúplná a potřebuje rozšířit. {{{1}}}

Veta: Fin - doplnok Inf - je $ \Sigma_2 $ (pravdepodobne úplný)

Veta: Rek = $ \{x: W_x \mbox{ je rekurzívne}\} $ je $ \Sigma_3 $ úplná.